Easy concept with Python/C++/Java Solution


  • 171
    1. Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
    2. For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.

    E.g.
    input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    subarray after step 1: [[7,0], [7,1]]
    subarray after step 2: [[7,0], [6,1], [7,1]]
    ...

    It's not the most concise code, but I think it well explained the concept.

    class Solution(object):
        def reconstructQueue(self, people):
            if not people: return []
    
            # obtain everyone's info
            # key=height, value=k-value, index in original array
            peopledct, height, res = {}, [], []
            
            for i in xrange(len(people)):
                p = people[i]
                if p[0] in peopledct:
                    peopledct[p[0]] += (p[1], i),
                else:
                    peopledct[p[0]] = [(p[1], i)]
                    height += p[0],
    
            height.sort()      # here are different heights we have
    
            # sort from the tallest group
            for h in height[::-1]:
                peopledct[h].sort()
                for p in peopledct[h]:
                    res.insert(p[0], people[p[1]])
    
            return res
    
    

    EDIT:
    Please also check:
    @tlhuang 's concise Python code.
    @wsurvi 's 4 lines Python code.
    @tonygogogo 's 8 lines C++ solution.
    @zeller2 's Java version.
    @hotpro 's Java 8 solution.


  • 9
    T

    @YJL1228, how about this

    class Solution(object):
        def reconstructQueue(self, people):
            """
            :type people: List[List[int]]
            :rtype: List[List[int]]
            """
            res = []
            for k, g in itertools.groupby(sorted(people, reverse=True), key=lambda x: x[0]):
                for person in sorted(g):
                    res.insert(person[1], person)
            return res
    

  • 43
    T

    Your way of solving this is brilliant. How do you come up with this solution?
    Anyway I write a C++ code based on your idea. Only 8 lines.

    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
            sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
                return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
            });
            vector<pair<int,int>> sol;
            for (auto person : people){
                sol.insert(sol.begin() + person.second, person);
            }
            return sol;
        }
    

  • 109
    Z

    Java version based on your brilliant solution.

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            //pick up the tallest guy first
            //when insert the next tall guy, just need to insert him into kth position
            //repeat until all people are inserted into list
            Arrays.sort(people,new Comparator<int[]>(){
               @Override
               public int compare(int[] o1, int[] o2){
                   return o1[0]!=o2[0]?-o1[0]+o2[0]:o1[1]-o2[1];
               }
            });
            List<int[]> res = new LinkedList<>();
            for(int[] cur : people){
                res.add(cur[1],cur);       
            }
            return res.toArray(new int[people.length][]);
        }
    }```

  • 10
    I

    Can just use add(idx, elem).

            Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
            List<int[]> ans = new LinkedList<>();
            for (int[] p : people) {
                ans.add(p[1], p);
            }
            return ans.toArray(new int[0][0]);
    

  • 0
    J

    @zeller2 Why using LinkedList here? ArrayList should be faster for this scenario.


  • 1

  • 1
    K

    In worst case isnt this n^2 + nlogn. nlogn for the sort and n^2 for linked list insertion. You can argue that linked list insertion is O(1) but that is only asymptotically and not always.


  • 9
    H

    Shorter Java 8 solution. But a little bit slower, 97 ms.

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
            List<int[]> list = new LinkedList<>();
            for (int[] p : people) {
                list.add(p[1], p);
            }
            return list.toArray(new int[list.size()][]);
        }
    }
    

  • -1
    Y

    @zeller2 @hotpro I have questions for you guys. Here is my Java code:

    List<int[]> array = new LinkedList<int[]>();
    int[] test = {2, 3};
    hello.add(2, test);
    

    I think when I run this code, Java will give me "Out of bound" exception. Every time when I try to add an element into a List which is out of the size, it will throw out of bound exception (even the list is ArrayList or LinkedList).


  • 0
    Z

    @yaozk
    Can you post your code for add method?


  • 2
    Y

    @zeller2 I think you only need to solve if the next element is out of range. For example, if the input is [[7,3], [7,4]], your original code will add [7,3] into index 3, but since the size is 0 now, we just add it into the last index which is 1. To be sort, your code and idea is great, only need to add one line "if (cur[1] >= res.size()) res.add(cur);". Here is my fixed code based on your, and it was accepted (20ms, beats 75.19%):

    public class Solution 
    {
    	public int[][] reconstructQueue(int[][] people) {
            //pick up the tallest guy first
            //when insert the next tall guy, just need to insert him into kth position
            //repeat until all people are inserted into list
            Arrays.sort(people,new Comparator<int[]>(){
               @Override
               public int compare(int[] o1, int[] o2){
                   return o1[0]!=o2[0]?-o1[0]+o2[0]:o1[1]-o2[1];
               }
            });
            List<int[]> res = new ArrayList<int[]>();
            for(int[] cur : people){
            	if (cur[1] >= res.size())
            		res.add(cur);
            	else
            		res.add(cur[1],cur);       
            }
            return res.toArray(new int[people.length][]);
        }
    }
    

  • 4
    Z

    @yaozk
    For this problem, we sort the array by height in decreasing order ( if heights are the same, sort by index in ascending order ). Every time we take the tallest element out first, so it guarantees that the case you provided will not exist.
    In your case, since 7 is already the tallest element, how comes there are still three elements stand before it?


  • 0
    Y

    @zeller2 I am not sure if this input will be exists, but if the inputs is [[7,3],[7,4]], then we meet the problem. If this input is illegal, than your code is perfect.


  • 8
    W

    @tlhuang @YJL1228

    If the simple answer below is okay (it passed the test), it seems easier to understand for me.
    Still, the great answer from @tlhuang uses fancier functions that I didn't come up with.

    class Solution(object):
        def reconstructQueue(self, people):
            """
            :type people: List[List[int]]
            :rtype: List[List[int]]
            """
            res = []
            for p in sorted(people, key=lambda x: (-x[0], x[1])):
                res.insert(p[1],p)
            return res
    

  • 0
    F

    @yaozk
    Double check the sorting part is correct.


  • 0
    J

    How can we prove the correctness of the algorithm?


  • 0
    L

    @jeffery agreed, and the run time


  • 0
    L

    Great idea. Very straightforward


  • 0
    A

    The idea is really beautiful, but how did you come up with this idea? Is this problem a specific problem within a general kind of problems?


Log in to reply
 

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