Queue Reconstruction by Height

MediumGreedygreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

People once stood in a line, but the order was lost. For each person you know people[i] = [h, k]: their height h, and k, the number of people standing in front of them whose height is greater than or equal to h. Return the original line as an array of [h, k] pairs from front to back. The input is guaranteed to describe at least one valid line, and a valid line determined by these counts is unique. An O(n^2) solution is expected.

Examples

Input: people = [[6,0],[4,3],[5,0],[4,1]]
Output: [[5,0],[4,1],[6,0],[4,3]]
In that line the first 4 has only 5 in front of it that is at least as tall, and the second 4 has 5, 4 and 6.
Input: people = [[1,1],[2,0]]
Output: [[2,0],[1,1]]
The shorter person needs one taller person in front.

Constraints

  • 1 <= people.length <= 2000
  • 0 <= h <= 10^6
  • 0 <= k < people.length
  • The input describes a valid line

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems