Level

Medium

Description

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:

The number of people is less than 1,100.

Example

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] ```

Solution

First sort the array people in the following order. Suppose person1 and person2 are two elements of people, then person1 is before person2 if and only if person1[0] > person2[0] or person1[0] == person2[0] and person1[1] < person2[1]. That is, sort the people according to height in descending order. If two people have the same height, sort them according to count in ascending order.

Next use the idea of insertion sort to reconstruct the array. For index i from 1 to people.length - 1, people[i]’s height must be less than or equal to all the people in the index range from 0 to i - 1. Suppose count = people[i][1]. If count < i, then insert people[i] at index count.

Take the example in the problem. The array is reconstructed in the following way.

The input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]].

After sorting: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]].

First insertion: [7,1] is at the correct index, so do not change.

Second insertion: Insert [6,1] at index 1. The array becomes [[7,0], [6,1], [7,1], [5,0], [5,2], [4,4]].

Third insertion: Insert [5,0] at index 0. The array becomes [[5,0], [7,0], [6,1], [7,1], [5,2], [4,4]].

Fourth insertion: Insert [5,2] at index 2. The array becomes [[5,0], [7,0], [5,2], [6,1], [7,1], [4,4]].

Fifth insertion: Insert [4,4] at index 4. The array becomes [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].

And the reconstructed array is [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]].

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0])
                    return person2[0] - person1[0];
                else
                    return person1[1] - person2[1];
            }
        });
        int length = people.length;
        for (int i = 1; i < length; i++) {
            int[] person = people[i];
            int height = person[0], count = person[1];
            if (count < i) {
                for (int j = i - 1; j >= count; j--) {
                    for (int k = 0; k < 2; k++)
                        people[j + 1][k] = people[j][k];
                }
                people[count][0] = height;
                people[count][1] = count;
            }
        }
        return people;
    }
}

public class Queue_Reconstruction_by_Height {

    /*
    Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
    For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.

    E.g.

    input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    subarray after step 1: [[7,0], [7,1]]
    subarray after step 2: [[7,0], [6,1], [7,1]]

     */
    class Solution {
        public int[][] reconstructQueue(int[][] people) {

            // maxheap to hold list of people in comparison with height and then use k to order the same height people
            PriorityQueue<int[]> pq = new PriorityQueue<>(
                (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]
            );

            for (int[] each: people) {
                pq.offer(each);
            }

            // now pq is: [[7,0], [7,1], [6,1], [5,0], [5,2]], [4,4]

            List<int[]> result = new ArrayList<>();

            // [[7,0],
            // [[7,0], [7,1],
            // [[7,0], [6,1], [7,1]]
            while (!pq.isEmpty()) {
                int[] each = pq.poll();
                result.add(each[1], each);
            }

            return result.toArray(people);

        }
    }
}

############

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        List<int[]> ans = new ArrayList<>(people.length);
        for (int[] p : people) {
            ans.add(p[1], p);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

// OJ: https://leetcode.com/problems/queue-reconstruction-by-height
// Time: O(N^2)
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/60470/6-lines-concise-c
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](vector<int> &a, vector<int> &b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        vector<vector<int>> ans;
        for (auto &p : people) ans.insert(ans.begin() + p[1], p);
        return ans;
    }
};

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []
        for p in people:
            ans.insert(p[1], p)
        return ans

############

class Solution(object):
  def reconstructQueue(self, people):
    """
    :type people: List[List[int]]
    :rtype: List[List[int]]
    """
    queue = []
    for p in sorted(people, key=lambda (h, k): (-h, k)):
      queue.insert(p[1], p)
    return queue

func reconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(i, j int) bool {
		a, b := people[i], people[j]
		return a[0] > b[0] || a[0] == b[0] && a[1] < b[1]
	})
	var ans [][]int
	for _, p := range people {
		i := p[1]
		ans = append(ans[:i], append([][]int{p}, ans[i:]...)...)
	}
	return ans
}

406 - Queue Reconstruction by Height

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

Level

Description

Solution

All Problems

All Solutions