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


  • 0
    K

    The idea:

    1. Find the person with 0 people in front of them. If you have 2 such people choose the shorter person
    2. For all the remaining people, subtract 1 from the number of people in front of them if the person chosen in step 1 is of greater or equal height. ([5,0] is the first person so for all people with height upto 5 we reduce people in front by 1)
    3. Go to step 1 (in every step we will have some one with zero people in front of them as we are subtracting)

    Extra 1d array used to store number of people in front a person. This is decremented every time someone with height >= person's height is chosen in step 1

    Can we reduce time with this approach?

    import java.util.*;
    
    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
        
        int m = people.length;
        if(m<2)
            return people;
        int n = people[0].length;
        
        int A[] = new int[m];
        int index=0;
        int temp1, temp2;
        
        for(int i=0; i<m; i++)
            A[i]=people[i][1];
        
        for(int i=0; i<m; i++){
            index = -1;
            for(int j=i; j<m; j++){
                
                if(i>0){
                    if(people[j][0]<=people[i-1][0])
                        A[j]--;
                }
                
                if(A[j]==0){
                    if(index==-1)
                        index = j;
                    else{
                        if(people[j][0]<people[index][0])
                            index = j;
                    }
                }
            }
            
            //Swap i and index
            temp1 = people[index][0];
            temp2 = people[index][1];
            people[index][0] = people[i][0];
            people[index][1] = people[i][1];
            people[i][0] = temp1;
            people[i][1] = temp2;
            
            //Swap i and indes in A
            temp1 = A[index];
            A[index] = A[i];
            A[i] = temp1;
        }
        
        return people;
    }
    }
    

Log in to reply
 

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