Short Java solution without using Extra Space


  • 0
    L
    public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if (a[1] != b[1]) { return a[1] - b[1];} // sort the array by people's k
                    else { return b[0] - a[0]; }            // if they have same k, sort it according to h
                }    
            });
            
            for (int i=1 ; i<people.length ; ++i) {
                int counter = 0;
                for (int j=0 ; j<i ; ++j) {
                    if ((counter == people[i][1])){ 
                        int[] tmp = { people[i][0], people[i][1] };
                        for (int k=i-1 ; k>=j ; --k) { // move each element to the right one step (from i-1 to j)
                            people[k+1] = people[k];   
                        }
                        people[j] = tmp;            // insert people i to the position j
                        break;
                    }
                    if (people[j][0] >= people[i][0]) { // count how many people's height >= people i's height
                        ++counter;
                    }
                }
            }
            return people;
        }
    
    

Log in to reply
 

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