DSA Queue Reconstruction by Height

The problem

Queue Reconstruction rebuilds a line of people from pairs that record a height and one count. Each pair holds a height h and a count k. The count k is the number of taller or equal people standing in front of that person.

The answer in this article is the rebuilt queue as a list of pairs in standing order. The input pairs arrive in no useful order. In a correct queue, every pair's k matches a fresh count over the finished line.

cases = [[[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]], [[6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4]]]
for people in cases:
    print('people:', len(people), people)

Both cases hold six people. Both rebuilt queues appear in the optimal section. A checker at the end of the article recounts every k from the finished queue.

Intuition: place people in the order given, or by rising k

The first idea trusts the input order. It appends each person where the list happens to put them. The k values are then whatever the accident of order produces, and most of them are wrong.

Rising k order fails in the opposite way. A short person with a small k takes a front slot early. A taller person who belongs in front of them then has nowhere to go without shifting counts that were already settled.

people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
wrong = 0
for index, person in enumerate(people):
    height, k = person
    front = 0
    for other in people[:index]:
        if other[0] >= height:
            front += 1
    if front != k:
        wrong += 1
    print(person, 'taller or equal in front:', front, 'matches k:', front == k)
print('wrong k values in input order:', wrong)

Four of the six k values are wrong in input order. An order exists that makes all six right. It starts from the tallest people, whose k counts nobody shorter can disturb.

Brute force: test every ordering of the people

The brute force tries every permutation of the people. It recounts each person's taller-or-equal front count in that order. The first order where every count matches is a valid queue.

import itertools
def brute(people):
    tested = [0]
    for order in itertools.permutations(people):
        tested[0] += 1
        ok = True
        for index, person in enumerate(order):
            height, k = person
            front = 0
            for other in order[:index]:
                if other[0] >= height:
                    front += 1
            if front != k:
                ok = False
        if ok:
            return [list(p) for p in order], tested[0]
    return None, tested[0]
queue, tested = brute([[5, 0], [7, 0], [6, 1]])
print('queue:', queue)
print('permutations tested:', tested)

Three people already need up to six permutations. Six people need up to 720, and each added person multiplies that count. The optimal build makes one insertion per person and never tests an ordering.

The optimal solution: tallest first, insert at index k

People are sorted by height with the tallest first and equal heights in rising k order, and each person is then inserted into the growing queue at index k. That one sentence is the whole method.

Shorter people inserted later do not count toward the k of taller people already placed, because k counts only taller or equal people in front. The insert operation shifts the people behind the new person one place to the right, and those shifts never break a settled k.

def rebuild(people):
    ordered = sorted(people, key=lambda p: (-p[0], p[1]))
    queue = []
    inserts = [0]
    for height, k in ordered:
        queue.insert(k, [height, k])
        inserts[0] += 1
    return queue, inserts[0]
cases = [[[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]], [[6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4]]]
for people in cases:
    queue, inserts = rebuild(people)
    print('people:', len(people), 'inserts:', inserts)
    print('queue:', queue)

Both cases from the start of the article are rebuilt in six inserts each. The first queue starts with the person of height 5 and k 0. That front slot was taken last among the tall placements, by the shortest groups arriving in sorted order.

Walkthrough: inserting the first case step by step

The walk inserts the people in sorted order. The state is the growing queue after each insert. Each new person lands exactly at index k.

ordered = [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]
queue = []
for height, k in ordered:
    queue.insert(k, [height, k])
    print('insert', [height, k], 'at', k, 'queue:', queue)

The final queue matches the optimal section. Each insert landed at its own k. Later, shorter inserts shifted people right without changing any taller person's front count of taller-or-equal people.

Complexity

Sorting costs O(n log n) for n people. Each insert can shift up to n people, so the build costs O(n squared) in the worst case, and its extra space is the queue itself at O(n).

for n in [3, 6, 10]:
    total = 1
    for i in range(2, n + 1):
        total *= i
    print('people', n, '- inserts:', n, ' brute permutations:', total)

At ten people the build makes ten inserts. The brute force would face over three million permutations. One sort plus one insert per person replaces all of them.

Edge cases and pitfalls

Equal heights must be sorted in rising k order before any insert runs. Reversing that tie order puts the larger k first, and the smaller k then inserts in front of a person who should stand behind. The finished queue fails its recount.

An empty input gives an empty queue. A single person always carries k 0, because nobody stands in front of them. Both facts follow from the definition of k, with no special code.

queue = [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
for index, person in enumerate(queue):
    height, k = person
    taller_or_equal = 0
    for other in queue[:index]:
        if other[0] >= height:
            taller_or_equal += 1
    print(person, 'taller or equal in front:', taller_or_equal, 'matches k:', taller_or_equal == k)
print('empty queue:', [])

Every person in the finished queue passes the recount. That recount is the definition of correctness for this problem. A build that passes it needs no further proof for that input.