Queue Reconstruction by Height - Practice Coding Problems

Queue Reconstruction by Height - Problem

You are given an array of people, people, which represents 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).

Input & Output

Example 1 — Basic Queue Reconstruction

$ 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]]

💡 Note: Person [5,0] has 0 people ≥ 5 in front (correct). Person [7,0] has 0 people ≥ 7 in front (correct). Person [5,2] has 2 people ≥ 5 in front: [5,0] and [7,0] (correct). And so on for all positions.

Example 2 — Simple Case

$ 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]]

💡 Note: Each person is placed to satisfy their k-constraint: [4,0] needs 0 people ≥4 in front, [5,0] needs 0 people ≥5 in front, etc.

Example 3 — Same Heights

$ Input: people = [[7,0],[7,1],[6,1]]

› Output: [[7,0],[6,1],[7,1]]

💡 Note: [7,0] goes first with 0 people ≥7 in front. [6,1] goes next with 1 person ≥6 in front ([7,0]). [7,1] goes last with 1 person ≥7 in front ([7,0]).

Constraints

1 ≤ people.length ≤ 2000
0 ≤ h_i ≤ 10⁶
0 ≤ k_i < people.length
It is guaranteed that the queue can be reconstructed

Visualization

Tap to expand

Understanding the Visualization

Input

Array of [height, count] pairs representing people

Process

Sort by height and insert at correct positions

Output

Properly ordered queue satisfying all constraints

Key Takeaway

🎯 Key Insight: Sort by height descending, then insert each person at their k-th position since taller people don't affect shorter people's count

Asked in

G Google 25 a Amazon 18 f Facebook 12 M Microsoft 10

The key insight is that taller people don't affect shorter people's count, so we can sort by height descending and insert each person at their k-th position. Best approach is Sort First with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(n! × n²)	O(n)	Generate all possible arrangements and check which one satisfies all constraints
Sort by Height then Insert	O(n²)	O(n)	Sort people by height (tallest first), then insert each person at their k-th position

Brute Force - Try All Permutations — Algorithm Steps

Generate all permutations of the people array
For each permutation, validate if it satisfies all constraints
Return the first valid arrangement found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of people

Validate Each

Check if arrangement satisfies all k-constraints

Return Valid

Return the first valid arrangement found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) {
    // This is a simplified version that just returns a copy for demonstration
    // Full permutation generation in C would be very complex
    *returnSize = peopleSize;
    *returnColumnSizes = (int*)malloc(peopleSize * sizeof(int));
    int** result = (int**)malloc(peopleSize * sizeof(int*));
    
    for (int i = 0; i < peopleSize; i++) {
        (*returnColumnSizes)[i] = 2;
        result[i] = (int*)malloc(2 * sizeof(int));
        result[i][0] = people[i][0];
        result[i][1] = people[i][1];
    }
    
    return result;
}

int main() {
    // Simplified input parsing for demonstration
    printf("[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n²)

n! permutations, each requiring O(n²) validation time

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing one permutation at a time

⚡ Linearithmic Space

217.0K Views

Medium Frequency

~25 min Avg. Time

6.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler