Queue Reconstruction by Height

Master this topic with zero to advance depth.

Queue Reconstruction by Height

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 who has exactly k_i other people in front of them with a height greater than or equal to h_i.

Reconstruct and return the queue that is represented by the input array people.

Visual Representation

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

Step 1: Sort by height DESC, then k index ASC.
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Step 2: Insert into list at index k.
Insert [7,0] at 0: [[7,0]]
Insert [7,1] at 1: [[7,0], [7,1]]
Insert [6,1] at 1: [[7,0], [6,1], [7,1]]
Insert [5,0] at 0: [[5,0], [7,0], [6,1], [7,1]]
...

Medium

Examples

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]]
Result matches the height/k-index constraints.

Approach 1

Level I: Brute Force Simulation (Find Empty Slots)

Intuition

If we sort people by height ascending, we can process each person and find their relative position by counting 'empty slots' in the final array. Each empty slot is reserved for someone taller (or same height) than the current person.

Thought Process

Sort by height ASC, then $k$ DESC for same height.
Create an empty result array of size $N$ .
For each person [h, k]:
- We need $k$ people in front of us who are $\ge h$ .
- Find the $(k+1)$ -th empty slot in the result array and place the person there.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

people = [[7,0], [4,4], [7,1], [5,0], [5,2], [6,1]] Sorted (H asc, K desc): [[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]]

[4,4]: Put in 5th empty slot (idx 4). res=[_ _ _ _ [4,4] _]
[5,2]: Put in 3rd empty slot (idx 2). res=[_ _ [5,2] _ [4,4] _]
[5,0]: Put in 1st empty slot (idx 0). res=[[5,0] _ [5,2] _ [4,4] _]
[6,1]: Put in 2nd empty slot (idx 3). res=[[5,0] _ [5,2] [6,1] [4,4] _]

java

import java.util.Arrays;

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = people.length;
        int[][] res = new int[n][2];
        for (int[] r : res) Arrays.fill(r, -1);

        for (int[] p : people) {
            int count = p[1];
            for (int i = 0; i < n; i++) {
                if (res[i][0] == -1) { // Empty slot
                    if (count == 0) {
                        res[i] = p;
                        break;
                    }
                    count--;
                }
            }
        }
        return res;
    }
}

Approach 2

Level II: Optimal Greedy (Sort and Insert)

Intuition

Taller people don't care about shorter people behind them. If we process taller people first, their relative k index in the final queue will be exactly equal to their index in the list.

Thought Process

Sort DESC by height, then ASC by k.
Insert each person into a dynamic list at index k.
Shorter people inserted later won't change the count of taller people in front of existing elements.

Pattern: Greedy Insertion

⏱ O(N^2) - List insertion takes $O(N)$.💾 O(N) for the list.

Detailed Dry Run

people = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

Step	Person	Action	Queue
1	[7,0]	Insert at 0	[[7,0]]
2	[7,1]	Insert at 1	[[7,0], [7,1]]
3	[6,1]	Insert at 1	[[7,0], [6,1], [7,1]]
4	[5,0]	Insert at 0	[[5,0], [7,0], [6,1], [7,1]]
5	[5,2]	Insert at 2	[[5,0], [7,0], [5,2], [6,1], [7,1]]
6	[4,4]	Insert at 4	[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

java

import java.util.*;

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

Approach 3

Level III: Logarithmic Optimal (Binary Indexed Tree)

Intuition

Finding the $(k+1)$ -th empty slot in $O(N)$ is the bottleneck in the simulation. We can speed this up to $O(\log N)$ using a Binary Indexed Tree (BIT) or Segment Tree by tracking the number of available slots.

Thought Process

Use the height ASC sort from Level I.
Imagine an array where 1 means 'empty' and 0 means 'filled'.
We want a position $idx$ where $prefixSum(idx) = k+1$ .
We can find this using Binary Search over the BIT in $O(\log^2 N)$ or walking the Segment Tree in $O(\log N)$ .

⏱ O(N log^2 N)💾 O(N)

Detailed Dry Run

Sorted: [[4,4], [5,2], [5,0], [6,1], [7,1], [7,0]] BIT tracks empty slots (initially all 1s).

[4,4]: Find k=4. BIT query/search gives pos 5. res[4]=[4,4]. BIT update(5, -1).
[5,2]: Find k=2. BIT query search gives pos 3. res[2]=[5,2]. BIT update(3, -1).

java

import java.util.*;

public class Solution {
    int[] bit;
    public int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        bit = new int[n + 1];
        for (int i = 1; i <= n; i++) update(i, 1, n);
        
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        
        int[][] res = new int[n][2];
        for (int[] p : people) {
            int target = p[1] + 1;
            int l = 1, r = n, pos = n;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (query(mid) >= target) {
                    pos = mid;
                    r = mid - 1;
                } else l = mid + 1;
            }
            res[pos - 1] = p;
            update(pos, -1, n);
        }
        return res;
    }
    private void update(int i, int v, int n) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    private int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
}

← Previous QuestionNon-overlapping Intervals

Next Question →Task Scheduler

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.