Queue Reconstruction by Height

Problem

Queue Reconstruction by Height

Description

1. the first solution is to check every element is appropriate and its’ time complexity is O(N^2) that resulted TLE.

2. So, if there is a re-sorted array, which is sorted by the height and if height is same, sorted by the K, we can get the last answer by modifying the re-sorted array. As for some elements that don’t meet the requirement about K, they can be moved forward than now and by this way, the answer will be there.

Code

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        int N = people.length;
        List<int[]> orderedPeople = new ArrayList<>();
        Arrays.sort(people, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b){
                if(a[0] != b[0]){
                    return b[0] - a[0];
                } else {
                    return a[1] - b[1];
                }
            }
        });
        for(int i = 0; i < N; i ++){
            /*
            Here, the feature of the add function of array list fits this case very well. 
            This method inserts the specified element E at the specified position in this list. It shifts the element currently at that position (if any) and any subsequent elements to the right (will add one to their indices).
            */
            orderedPeople.add(people[i][1], people[i]);
        }
        int[][] ans = new int[N][2];
        for(int i = 0; i < N; i ++){
            ans[i] = orderedPeople.get(i);
        }
        return ans;
    }
}