Rebuild the Line from Height Records

Medium

A line at a ticket desk broke up. What is left are the records records, one per person, in no particular order: records[i] = [h, k] means the person is h tall and had exactly k people at least h tall standing ahead of them. Rebuild the line: return the same records ordered from the front of the line to the back. A valid line is guaranteed to exist, and it is unique.

Example 1

records=[[3, 0], [6, 0], [3, 1], [5, 1]] → [[3, 0], [3, 1], [6, 0], [5, 1]]

In the line [[3, 0], [3, 1], [6, 0], [5, 1]], the second person of height 3 has one person at least as tall ahead (the first one, also 3), and the person of height 5 has only the person of height 6 ahead who is at least as tall.

Example 2

records=[[4, 2], [4, 0], [4, 1]] → [[4, 0], [4, 1], [4, 2]]

Everyone is the same height, and equal heights count, so they line up by the second number.

Example 3

records=[[7, 0]] → [[7, 0]]

One person makes a line of one.

Constraints

1 ≤ records.length ≤ 2000
0 ≤ h ≤ 10⁶
0 ≤ k < records.length
The records are guaranteed to describe a valid line

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Sorting

Similar problems

Empty Rectangle From Marked Points Medium Deal Out From the Lowest Card Hard Best Pair Above the Bars Hard Clean Rectangle on Pins Hard Counting the Longest Rising Selections Medium

Input

records=[[3, 0], [6, 0], [3, 1], [5, 1]]

Expected

[[3, 0], [3, 1], [6, 0], [5, 1]]

Run checks the first 3 tests in your browser. Submit checks all 67 tests on the server, hidden ones included.