Last updated on January 5th, 2025 at 12:59 am

Here, we see Queue Reconstruction by Height LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Greedy

Companies

Google

Level of Question

Medium

Queue Reconstruction by Height LeetCode Solution

1. Problem Statement

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [h_i, k_i] represents the i^th person of height h_i with exactly k_i other people in front who have a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [h_j, k_j] is the attributes of the j^th person in the queue (queue[0] is the person at the front of the queue).

Example 1:
Input: people = [[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]]

Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1. Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:
Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

2. Coding Pattern Used in Solution

The provided code uses the Greedy Algorithm pattern. The problem is solved by sorting the input based on specific criteria and then greedily reconstructing the queue by inserting elements at the correct positions.

3. Code Implementation in Different Languages

3.1 Queue Reconstruction by Height C++

class Solution {
public:
    static bool comp(vector<int>& a, vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {   
        sort(people.begin(), people.end(), comp);
        vector<vector<int>> ans;
        for(auto man : people){
            ans.insert(ans.begin()+man[1], man);
        }
        return ans;
    }
};

3.2 Queue Reconstruction by Height Java

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[]> ordered = new LinkedList<>();
        for (int[] p: people) ordered.add(p[1], p);
        return ordered.toArray(new int[people.length][2]);        
    }
}

3.3 Queue Reconstruction by Height JavaScript

var reconstructQueue = function(people) {
    let res = []
    people.sort((a, b) => a[0] == b[0] ? a[1] - b[1] : b[0] - a[0])
    people.forEach(val => {
        res.splice(val[1], 0, val)
    })
    return res    
};

3.4 Queue Reconstruction by Height Python

class Solution(object):
    def reconstructQueue(self, people):
        output=[]
        people.sort(key=lambda x: (-x[0], x[1]))                
        for a in people:
            output.insert(a[1], a)
        return output  

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N^2)	O(N)
Java	O(N^2)	O(N)
JavaScript	O(N^2)	O(N)
Python	O(N^2)	O(N)