Java solution using Arrays.sort() and "insert sorting" idea


  • 17
    Y

    We first sort the people to make them stand from the highest to shortest. For people with same height, sort them according to the count of people before them from small to big.

    Then, we use the way similar to insert sorting to reorder the people. For a given person to insert, all the people already sorted are higher, so we just insert him in the "right" place to make the people before him as his "count" indicates. Since he is shorter than all the people in the sorted list, the "count" of the "existing" people does not be broken by the insertion.

        public int[][] reconstructQueue(int[][] people) {
            if (people == null || people.length == 0 || people[0].length == 0)
                return new int[0][0];
                
            Arrays.sort(people, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if (b[0] == a[0]) return a[1] - b[1];
                    return b[0] - a[0];
                }
            });
            
            int n = people.length;
            ArrayList<int[]> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++)
                tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
    
            int[][] res = new int[people.length][2];
            int i = 0;
            for (int[] k : tmp) {
                res[i][0] = k[0];
                res[i++][1] = k[1];
            }
            
            return res;
        }
    

  • 0
    M

    Could you explain what the array.sort mean? What the a and b represent?


  • 0
    G

    @manvswilds learn about Comparator in Java


  • 0
    Z

    OMG very genius idea and clean code! Thank you so much!


  • 2
    P

    I would like to replace if (people == null || people.length == 0 || people[0].length == 0) with if (people == null || people.length == 0 || people[0] ==null ||people[0].length == 0) because theoretically people can be{null} which has length of 1 but people[0] is null, other than that, very smart idea.


  • 0
    J

    Why not use ArrayList.toArray(T[]) to convert the list to array?


  • 0
    W
    This post is deleted!

  • 0
    C

    genius idea, i need some times to take it.


  • 0

    Love this explanation, thanks for sharing.


Log in to reply
 

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