Java O(n^2) solution with O(n) extra space


  • 1
    Z

    The key point of the problem is the, fact that position of any person in the queue, equals to the sum of numbers of taller and shorter people than the current person and standing before it in the queue. Thus the problem reduces to the problem of finding numbers of taller and shorter people standing before each people.

    1. Sort the array in ascending order of their heights O(nlog(n))
    2. For each element, find its proper position. To do so, use greedy algorithm. First assume that the position is k = people[i][1], where k is the number of taller people than i th person, standing before it in the queue. Then, if you meet in range [0,k] anybody shorter than current person, then increment its position (i.e k++). O(n^2)
    3. Insert current person to k th position of the resultant array O(1)
    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Comparator <int []> comp = new Comparator<int[]>(){
                @Override
                public int compare(int [] a , int [] b){
                    if(a[0] > b[0]){
                        return 1;
                    }
                    if(b[0] > a[0]){
                        return -1;
                    }
                    if(a[1]>b[1]){
                        return 1;
                    }
                    if(a[1]<b[1]){
                        return -1;
                    }
                    return 0;
                }
            };
            Arrays.sort(people, comp);
            int ans[][] = new int[people.length][2];
            for(int i =  0;i<people.length;i++){
                Arrays.fill(ans[i],-1);
            }
            for(int i = 0;i<people.length;i++){
                int k = people[i][1];
                while(k>people.length-1){  //this line of code is just for avoiding not logical inputs
                    k--;
                }
             
                for(int j = 0;j<=k && k<people.length-1;j++){
                    if(ans[j][0] == -1 || ans[j][0]>=people[i][0]) continue;
                    k++;
                }
                ans[k] = people[i];
            }
            return ans;
        }
    }

  • 0
    P

    Nice solution.
    Everybody is considering taller one first but this different idea.


Log in to reply
 

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