Greedy O (n^2) solution in Java


  • 1
    M

    Probably one of the more verbose solutions. First I sort the array ascendingly by k, and break ties by h. After that, I do an insertion sort so that people[i] have people[i][1] same height or taller entries infront of it. Here's my code

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, new Comparator<int[]>(){
                public int compare(int [] a, int [] b) {
                    int col1 = a[1] - b[1];
                    if (col1 != 0) {
                        return col1;
                    }
                    return a[0] - b[0];
                }
            });
            for (int i = 1; i < people.length; i++) {
                
                int key = people[i][0];
                int count = people[i][1];
                
                int prevTallerOrEqual = 0;
                for (int j = 0; j < i; j++) {
                    if (people[j][0] >= key) {
                        prevTallerOrEqual++;
                    }
                }
                
                int j = i;
                while (j > 0 && prevTallerOrEqual > count) {
                    people[j][0] = people[j-1][0];
                    people[j][1] = people[j-1][1];
                    j--;
                    if (people[j][0] >= key) {
                        prevTallerOrEqual--;
                    }
                }
                people[j][0] = key;
                people[j][1] = count;
            }
            return people;
        }
    }
    

Log in to reply
 

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