Line reconstruction by height


  • 10
    G

    Suppose you have a line of n people in which the k-th person is described by a pair (h,t) , where h is the height of the k-th person and t is the number of people in front of k who have a height greater or equal than h . Write an algorithm to reconstruct the line.

    For example, if the line is composed by the following people:

    [(7, 0),(4, 4),(7,1), (5, 0), (6,1), (5, 2)]
    

    The original line should be:

    [(5,0), (7,0), (5,2), (6,1), (4,4),(7,1)]

  • 0
    S
    I have thinking a simple solution, the solution have n step.
    each step i:
     1. find some tuple maybe the ith number (for example, (5,0) (7,0) maybe the 1st number, if the
     first number is (5,0), then (4, 1) (6,0) can be the 2nd number), the method is for (h, t), decide
     whether already determined number have t greater or equal than h.
    2. choose the least one from alternatives, because only the least have no effect on others,
     look at this if we have determined (3, 0) (7, 0), and now we have (4, 1) and (5, 1),if we
     choose (5, 1) the (4, 1) will`have no chance to get in the line.
    
    as for how to choose qulified alternatives, i suggests Binary Indexed Tree

  • 4

    We can use Rope (data structure) to solve this problem, basically we have to build a binary tree and do an in-order traversal in the end to get the final result. If the binary tree is balanced, time complexity will be O(nlog(n)), worst case will be O(n^2) for linear tree.

    Before we call reconstructLine function, make sure the input line is sorted by first descending the height then ascending the count, for example:

    [{7, 0}, {7, 1}, {6, 1}, {5, 0}, {5, 2}, {4, 4}]

    The insert logic is like so: the initial weight of each person is the count, compare to each node in the tree, if the weight is less than the node's weight, node's weight + 1, insert the person to the node's left; If the weight is larger than or equal to the node's weight, decrease the person's weight by node's weight, then insert to node's right. When the person is inserted as a leaf, set its weight to 1.

    Finally perform an in-order traversal to get the result.

    The following code focus on the logic of building the binary tree, sorting the input data should be fairly straightforward, time complexity should be O(nlog(n))

    public static class Solution {
      
      class TreeNode {
        int height;
        int count;
        int weight;
        
        TreeNode left;
        TreeNode right;
        
        TreeNode(int h, int c) {
          height = h;
          count = c;
          weight = 1;
        }
      }
      
      List<int[]> reconstructLine(List<int[]> line) {
        // step 1. insert the person to the tree
        TreeNode root = null;
        for (int[] person : line) {
          root = insert(root, person, person[1]);
        }
        
        // step 2. do in-order traversal
        List<int[]> res = new ArrayList<>();
        inorder(root, res);
        
        return res;
      }
      
      TreeNode insert(TreeNode root, int[] person, int w) {
        if (root == null) {
          return new TreeNode(person[0], person[1]);
        }
        
        if (person[1] < root.weight) {
          // person's count less than current node's weight
          // increase current node's weight and insert to the left
          root.weight++;
          root.left = insert(root.left, person, w);
        } else {
          // otherwise insert to the right
          // and decrease the weight by root.weight
          root.right = insert(root.right, person, w - root.weight);
        }
        
        return root;
      }
      
      void inorder(TreeNode root, List<int[]> res) {
        if (root == null) {
          return;
        }
        
        inorder(root.left, res);
        res.add(new int[]{root.height, root.count});
        inorder(root.right, res);
      }
      
    }
    

  • 0
    P

    doesn't work on the given example, got (5, 0), (6, 1), (5, 2) ,(7, 0), (4, 4), (7, 1).


  • 0

    Hi, sorry I forgot to mention that the input data needs to be sorted first by height then by count, also I fixed some logic in the code, now it should return the correct result. Hope it works for you now.


  • 0
    H

    Here is my runnable code. I know it's not the most efficient approach but I coded it. I basically generated any possible permutation from those pairs and check it on the fly. As soon as it passes the test, it returns and prints the correct permutation:

    class Person{
        public int height;
        public int count;
        public Person (int h, int c){
            height = h;
            count = c;
        }
    }
        
    
    public static int[][] lineReconstruction(int[][] ppl){
            int [][] res = new int[ppl.length][2];
            int[] permutation = new int[ppl.length];
            Map<Integer, Person> lookupTable = new HashMap<>();
    
            for(int i=0 ; i < ppl.length; i++)
                permutation[i] = i;
    
            for(int i=0 ; i < ppl.length; i++)
                lookupTable.put(i, new Person(ppl[i][0], ppl[i][1]));
    
    
            generateAndCheckPerm(lookupTable, permutation, res, 0);
    
            return res;
        }
    
        public static boolean generateAndCheckPerm(Map<Integer, Person> lookupTable, int [] permutation, int[][]res, int index) {
            if (permutation.length == index)
                return checkPerm(lookupTable, permutation, res);
    
            int core = permutation[index], swap;
            for (int i = index; i < permutation.length; i++) {
                permutation[index] = permutation[i];
                permutation[i] = core;
    
                if (generateAndCheckPerm(lookupTable, permutation, res, index + 1))
                    return true;
    
                permutation[i] = permutation[index];
                permutation[index] = core;
            }
            return false;
        }
    
        public static boolean checkPerm(Map<Integer, Person> lookupTable, int[] permutation, int[][] res){
    
            int count = 0;
            for(int k = 0; k < permutation.length; k++){
                count = 0;
                for(int j = k - 1; j >= 0; j--)
                    if(lookupTable.get(permutation[j]).height >= lookupTable.get(permutation[k]).height) count++;
    
                if (count != lookupTable.get(permutation[k]).count) return false;
            }
    
    
            for(int item : permutation)
                System.out.print(item + " ");
    
            System.out.println("");
    
            for(int item : permutation)
                System.out.print("[" + lookupTable.get(item).height + ", " + lookupTable.get(item).count + "] ");
    
            System.out.println("");
    
            return true;
        }
    

  • 2
    S

    Hi,
    There is one mistake in your insertion code.
    for comparison if (person[1] < root.weight)
    It should be if( w < root.weight)
    it is weight which is going to change for every right traversal


  • 12
    B

    I cannot find the website where I find this brilliant solution. But I am sure it is from careercup.

    1. Sort by number of tall people from small to big.
    2. Sort by height from tall to short.
    3. Insert people to the position according to the number of tall people they can see.

    And, that is it! Simple, right?

    My runnable code.

    def liningPeople(data):
    	data.sort(key=lambda x:x[1])
    	data.sort(key=lambda x:x[0], reverse=True)
    	result = []
    	for h, t in data:
    		result.insert(t, (h, t))
    	return result
    
    print(liningPeople([(7, 0),(4, 4),(7,1), (5, 0), (6,1), (5, 2)]))
    print(liningPeople([(7, 0),(4, 4),(7,1), (5, 2), (6,1), (5, 0)]))
    

  • 1

  • 5
    B
    • step-1: sort pairs according to h and t in ascend order.
      before sort: [(7, 0),(4, 4),(7,1), (5, 0), (6,1), (5, 2)]
      after sort: [(4, 4), (5, 0), (5, 2), (6,1), (7, 0), (7,1)]

    • step-2: insert each pair into correct position from last to first.
      [(7,1)] // (7, 0) is in front of (7,1), so (7,1) is in correct position.
      [(7,0), (7,1)] // there is no people taller than (7,0), so (7,0) is in correct position
      [(7,0), (6,1), (7,1)]// (7,0) is taller than (6,1)
      [(7,0), (5,2), (6,1), (7,1)] //(5, 0) and (7,0) should be in front of (5,2)
      [(5, 0),(7,0), (5,2), (6,1), (7,1)] //there is no people taller than (5,0), so (5,0) is in correct position
      [(5, 0),(7,0), (5,2), (6,1), (4, 4), (7,1)] //four people taller than (4, 4), so (4, 4) should go after (6,1)


  • 0
    S

    @biwuxia Nice logic! Here is the implementation:

    public List<int[]> reconstructLine(List<int[]> line){
            Collections.sort(line, new Comparator<int[]>(){
                public int compare(int[] i1, int[] i2){
                    if(i1[0]!=i2[0] ) return i1[0]-i2[0];
                    return i1[1]-i2[1];
                }
            } );
            List<Integer> equalBefore = new ArrayList<>(); // number of elements before with the same height
            for(int i=0;i<line.size();i++){
                if(i==0 || line.get(i-1)[0]<line.get(i)[0] ) equalBefore.add(0);
                else equalBefore.add(1+equalBefore.get(i-1));
            }
            ArrayList<int[]> res = new ArrayList<>();
            for(int i=line.size()-1;i>=0;i--){
                int[] cur = line.get(i);
                res.add(cur[1]-equalBefore.get(i),cur );
            }
            return res;
        }
    

  • 0
    C
    This post is deleted!

  • 1

    @code_ape Could you translate in english? Thanks


  • 1
    C

    @elmirap OK~
    If we have reconstructed the highest k people(suppose they are correctly reconstructed) Q, for a person ((h,t)) , he must be insert into the queue Q by t-th position. As we know, all higher or equal than (h,t) have been reconstructed before, therefore remain people insert into queue won't effect him.

    details:

    • sort the people p by height(h major key descend) and rank(t minor key ascend)
    • build a empty queue(Q). Insert person in p into Q by t-th position
    vector<pair<int, int>>& reconstruct(vector<pair<int, int>>& people){
    	int	nums = people.size();
    	vector<pair<int, int>>	&ret = *new vector<pair<int, int>>(); ret.reserve(nums);
    	class cmp{
    		typedef pair<int, int> _datatype;
    	public:
    		bool operator ()(_datatype const&a, _datatype const&b){
    			if (a.first != b.first)
    				return a.first > b.first;
    			else//比较次关键字
    				return a.second < b.second;
    		}
    	};
    	sort(people.begin(), people.end(),cmp());
    	for (vector<pair<int,int>>::iterator it = people.begin(); it != people.end() ; it++){
    		ret.insert(ret.begin() + it->second, *it);
    	}
    	return ret;
    }
    

  • 2

    For items with similar height sort by ascending count. For dissimilar heights sort by descending height. Add results to an ArrayList

    public class Data
    {
    	int height;
    	int count;
    }
    
    public class DataComparator implements Comparator{
    
    
    public int compare(Data d, Data b){
    
    if(d.height == b.height){
    	(d.count - b.count);
    }else{
    	return -1*(d.height - b.height);
    }
    
    }
    public List<Data> makeLine(Data[] a){
    
    Arrays.sort(a,new DataComparator());
    ArrayList<Data> results = new ArrayList<Data>();
    results.add(a[0]);
    for(int i = 1; i < a.length; i++){
    
    	int idx = a[i].count - 1;
    	results.add(idx.a[i]);
    }
    return results;
    
    }

  • 0
    P
    This post is deleted!

  • 0
    R

    I did not get the question, could you please explain more? I wonder why the reconstructed line is:
    [(5,0), (7,0), (5,2), (6,1), (4,4),(7,1)]
    since it is 7,5,6,7 in front of the first 5, then it should be (5,4). Isn't it? thanks


  • 0

    I hope this will work.

    public List<int[]> _getOrder (int[][] items) {
    	List<int[]> answer = new ArrayList<>();
    		
    	Arrays.sort(items, new Comparator<int[]> () {
    		public int compare(int[] o1, int[] o2) {
    			if (o1 [0] == o2 [0]) return o1 [1] - o2 [1]; 
    			return o2 [0] - o1 [0];
    		}
    	});
    		
    	Stack<int []> stack = new Stack<>();
    
    	for (int idx = 0; idx < items.length; idx ++) {
    		if (idx > 0) {
    			int lowRequirement = items [idx][1];
    			if (lowRequirement < answer.size())
    				while (lowRequirement < answer.size()) stack.push(answer.remove(answer.size() - 1));
    			else if (lowRequirement > answer.size())
    				if (!stack.isEmpty()) answer.add(stack.pop());
    		}
    		answer.add(items [idx]);
    	}
    		
    	return answer;
    }
    	
    

  • 0
    A

    Sort the input array by height and choose the lower number of t in case of similar height.
    Then iterate through list and compare each element with size of array to see if that element can be added to the correct position.
    Here is the code.

    
    public static List<int[]> reconstructLine(List<int[]> list){
    		//sort by height
    		List<int[]> result = new ArrayList<int[]>();
    		Collections.sort(list, new Comparator<int[]>(){
    			public int compare(int[] nums1, int[] nums2){
    				if(nums1[0] == nums2[0]){
    					return nums1[1] - nums2[1];
    				} else {
    					return nums1[0] - nums2[0];
    				}
    			}
    		});
    
    		while(!list.isEmpty()){
    			int index=-1;
    			for(int i=0;i<list.size();i++){
    				if(list.get(i)[1] <= result.size()){
    					// System.out.println("size: " + result.size());
    					result.add(list.get(i));
    					index = i;
    					break;
    				}
    			}
    			list.remove(index);
    		}
    		return result;

  • 0
    R

    My simple code is as follows:
    1.Sort the queue in ascending order according to people's height.
    2.If two people have same height the use number of people in front (again in ascending order)
    3.One by one use Insertion sort like approach to place the people from end to their right place.

    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            sort(people.begin(),people.end());
            
            int n=people.size();
            //for(int i=0;i<n;i++)
            //cout<<people[i].first<<" "<<people[i].second<<endl;
            vector<pair<int,int> > res(n);
            vector<int> aux(n,0);
            for(int i=1;i<n;i++)
            if(people[i-1].first==people[i].first)
            aux[i]=aux[i-1]+1;
            int k=-1;
            for(int i=n-1;i>=0;i--)
            {
                int shift=people[i].second-aux[i];
                //cout<<"shift="<<shift<<endl;
                for(int j=k+1;j>shift;j--)
                res[j]=res[j-1];
                res[shift]=people[i];
                k++;
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.