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

  • 0

    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;
            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++)
        for(int i=0; i<m; i++){
            index = -1;
            for(int j=i; j<m; j++){
                        index = j;
                            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.