Reconstruct a queue by height in Python

Why this matters

A queue is a line of people. This problem gives you clues instead of the line itself. Each person says how many people in front of them are at least as tall as they are. Your job is to rebuild the whole line so that every clue is true.

The problem is a good first lesson in a greedy habit that you will use again. Greedy means you make one choice at a time and never take it back. The hard part is choosing the order in which to make the choices. Here the order is what makes the greedy rule work. If you pick the wrong order, the code either fails or builds a line that breaks some clues, and in Python it often does so without any error.

The lesson also teaches a second habit. Passing one sample is not proof that a rule is right. This lesson shows a short argument that the rule keeps every earlier clue true, for any valid input.

Words you will need

• Queue: a line of people, one behind another. In this lesson it means the physical line, not the queue module from the standard library.
• Height: a whole number. A taller person has a bigger number.
• Clue: a pair of numbers for one person. This lesson writes a clue as [h, k], where h is the height and k is the count.
• Count k: the number of people standing in front of this person whose height is at least h. Shorter people do not count.
• Index: a position in a list. The first position is index 0, the second is index 1, and so on.
• Insert: put an item at a chosen index. The item already at that index, and every item after it, moves one place back. In Python this is the insert method of a list.
• Dataclass: a class that only holds data. Python writes the setup code for you. The decorator @dataclass(frozen=True) above a class with two fields declares one, and frozen=True means its fields cannot be changed after the object is made.
• Sort key: a function that gives the value to compare for each item. sorted orders the items by those values.
• Valid input: an input for which at least one correct line exists. The problem promises that every input you get is valid.
• Invariant: a fact that stays true after every step. The proof below shows one.

The problem in plain words

You get a list of clues, one per person. Each clue is [h, k]. Output a line of people, in front-to-back order, so that every person's k matches the line.

Take this list of six clues:

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

Look at the clue [7, 0]. Zero people in front of this person are 7 or taller, so this person must stand before every other person who is 7 or taller. The clue [4, 4] says that four people in front are at least 4 tall. That is almost everyone in front. The clue [7, 1] says exactly one person in front is at least 7 tall, which is the [7, 0] person.

To check a finished line, go through it person by person. For each person, count the people in front of them whose height is at least theirs. The count must equal k. This check is the test you will use for every version of the code in this lesson.

A small example first

Start with two people, [5, 0] and [5, 1]. The second clue says one person in front is at least 5 tall. The first clue says nobody in front is at least 5 tall. The only line that works is the [5, 0] person first, then the [5, 1] person.

This example shows the core idea. A clue can be read as a position. The person with k taller-or-equal people in front goes to position k, if the people who are already placed are the ones that count.

The tricky part is that a position depends on who else is already in the line. You cannot place every person at their k in a random order. You must choose the order so that the position is correct at the moment you place each person.

The rule: tallest first, then smallest count

Here is the rule that works.

1. Sort the clues by height, tallest first.
2. When two clues have the same height, put the one with the smaller k first.
3. Start with an empty list. Take the clues in that order. For each clue [h, k], insert the person at index k.

When the loop ends, the list is the answer.

Hand-run the rule on the six clues from before. After sorting, the order is:

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

The table shows what happens at each insertion. The line is written front to back.

Check the step 3 insert. The [6, 1] person goes to index 1, so one person stands in front, the [7, 0] person. That person is 7 tall, which is at least 6, so the count is 1. The rule is satisfied.

Check the last step. The [4, 4] person goes to index 4, so four people stand in front: [5, 0], [7, 0], [5, 2] and [6, 1]. All four are at least 4 tall, so the count is 4. The rule is satisfied.

Why the order matters

It is worth seeing what goes wrong with the other orders. Each case below changes only the sort key and keeps the insert loop the same.

Python's list.insert does not raise an error when the index is bigger than the list. It adds the item at the end instead. So a wrong order does not crash the way it would in some other languages. It builds a line that breaks the clues. Run the check to find out.

Sorting by k alone, with sorted(sample, key=lambda p: p.ahead), gives this line. The lambda p: ... part is a short unnamed function that returns the value to compare:

wrong key ahead first: [[5, 0], [6, 1], [5, 2], [7, 1], [4, 4], [7, 0]] valid=False

The [7, 0] person is at the back of this line, but the clue says nobody in front is 7 or taller. One person in front of them, [7, 1], is 7 tall, so the count is 1 and the clue is broken.

Sorting shortest first, with sorted(sample, key=lambda p: (p.height, p.ahead)), also finishes without an error:

shortest first: [[7, 0], [7, 1], [5, 0], [6, 1], [4, 4], [5, 2]] valid=False

The first person placed is [4, 4]. The list is empty, so insert(4, ...) adds the person at the end, which is index 0. Every later insert is then placed at the wrong count. The check catches the broken line.

Why tallest first works: the proof

The proof has three parts. Each part explains one reason the rule is safe. The argument uses one fact about valid inputs, which the next paragraph explains.

In a valid input, two people with the same height cannot have the same k. Suppose [5, 2] and [5, 2] both appear. Whichever of the two stands second has the other one in front. The second person's count includes the first person and everyone counted for the first person, so it is at least one more than the first person's count. Two clues that both say 2 cannot both be true. No valid line can have this pair. The problem promises a valid input, so the pair never appears.

Part 1: the list only holds taller people during a group

Group the clues by height. Process the tallest group first. When you process a group of people with height h, the list holds only people whose height is h or more. Every person in the list was placed earlier, and they all came from taller groups or from the same group.

That means the position of a person in the list equals the number of taller-or-equal people in front of them. Nobody shorter is in the list to mess up the count. So inserting at index k gives the new person exactly k taller-or-equal people in front.

Part 2: the index is always in range

Inserting at index k only puts the person in the right place if the list has at least k people in it. Take a clue [h, k] from a valid input. In the final valid line, exactly k people stand in front of this person with height at least h. Each of those people is either taller than h, or has height h with a smaller k than this person. Both kinds are processed before this person. So when this person is inserted, at least k people are already in the list, and index k is in range.

The second kind needs one more step. Suppose a person q with height h stands in front of p in the final line. Everyone counted for q also stands in front of q, so they are also in front of p, and they are at least h tall. Those people are all counted for p too. Person p also counts q. So p has at least one more counted person than q does, which means q has a smaller k.

Part 3: later insertions never break an earlier clue

Take a person p that has just been inserted with count k_p. Look at every insertion after this one.

• A shorter person is inserted later. Shorter people are not counted in p's clue, so their presence does not change p's count. They may move p to a higher index, but the count stays the same.
• A person of the same height is inserted later. Because of the sort, this person has a bigger k. So their index is bigger than the index p had when p was inserted, which is k_p. Inserting at a bigger index puts the new person behind p, and p's place does not change. Nobody in front of p changes.
• A taller person is never inserted later, because of the sort.

So after every insertion, every person already in the list still has the right count. When the loop ends, every person has been checked and kept. The line is valid.

This is the whole argument. The sort order does the work. Tallest first keeps the list at the right size for the index. Smaller k first, within a height, keeps later people behind earlier ones.

The Python code

The code below uses a dataclass for each person. The reconstruct function uses sorted, which returns a new list, so the caller's list is not changed. It then inserts each person at index k. The valid function is the check from earlier, and the bottom part runs the sample.

Save the code as reconstruct_queue.py and run it with:

python3 reconstruct_queue.py

The output on Python 3.14 is:

sample: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]] valid=True
second: [[1, 0], [2, 0], [1, 2], [3, 0], [2, 2], [4, 0]] valid=True
third: [[4, 0], [5, 0], [2, 2], [3, 2], [1, 4], [6, 0]] valid=True
sample as dataclass: Person(height=5, ahead=0)
wrong key ahead first: [[5, 0], [6, 1], [5, 2], [7, 1], [4, 4], [7, 0]] valid=False
shortest first: [[7, 0], [7, 1], [5, 0], [6, 1], [4, 4], [5, 2]] valid=False
input unchanged: True

The first line matches the table from the hand run. The valid check confirms it.

The sort key (-p.height, p.ahead) is a tuple. Python compares tuples one item at a time, from left to right. The first item is the negative height, so a bigger height gives a smaller key and comes first. When the heights are equal, the second item, ahead, decides, and the smaller count comes first. Negating the height is a common trick for "largest first" with a normal ascending sort.

The insert is queue.insert(p.ahead, p). The insert method of a list takes an index and an item. Python moves the items at and after the index one place back, which is exactly what the rule needs.

The valid function uses enumerate, which gives each position and the person there. queue[:i] is a slice, a new list with the people in front of position i. The part sum(1 for q in queue[:i] if q.height >= p.height) is a generator expression. It counts the people in front who are at least as tall, without building a second list.

More worked examples

The sample has a mix of heights. The next two examples are harder in different ways. Each one is run with the same report function, so you can run them yourself.

The second example has several people with the same height. Heights 1 and 2 each appear twice, and the counts differ inside each group.

second = [Person(2, 0), Person(3, 0), Person(1, 2),
          Person(4, 0), Person(2, 2), Person(1, 0)]
report("second", second)

second: [[1, 0], [2, 0], [1, 2], [3, 0], [2, 2], [4, 0]] valid=True

Sorted, the order is [4, 0], [3, 0], [2, 0], [2, 2], [1, 0], [1, 2]. Trace the first four inserts. [4, 0] goes to index 0. [3, 0] goes to index 0, in front of it. [2, 0] goes to index 0. Now the list is [2, 0] [3, 0] [4, 0], three people long, so index 2 is in range for [2, 2]. Insert [2, 2] at index 2, which gives [2, 0] [3, 0] [2, 2] [4, 0]. The people in front of [2, 2] are [2, 0] and [3, 0], both at least 2 tall, so the count is 2 and the clue holds.

The shorter people come next. Insert [1, 0] at index 0, which gives [1, 0] [2, 0] [3, 0] [2, 2] [4, 0]. Then insert [1, 2] at index 2, which gives the final line [1, 0] [2, 0] [1, 2] [3, 0] [2, 2] [4, 0]. The [1, 2] person has [1, 0] and [2, 0] in front, both at least 1 tall, so the count is 2 and the clue holds.

The shorter people did move the height-2 people to higher indexes, but they were not counted for those people. This is the point of the proof. While the height-2 group was built, the list held only people at least 2 tall, so the index was the count. The shorter people came after the whole group.

The third example has a clue with a large k for a short person.

third = [Person(6, 0), Person(5, 0), Person(4, 0),
         Person(3, 2), Person(2, 2), Person(1, 4)]
report("third", third)

third: [[4, 0], [5, 0], [2, 2], [3, 2], [1, 4], [6, 0]] valid=True

Here the person [1, 4] has four people in front who are at least 1 tall. Everyone is at least 1 tall, so the count is simply the number of people in front. The [1, 4] person is the fifth in line, and four people stand in front of them. The clue for the shortest person is easy to satisfy once the line is long enough. The hard part is to place the taller people correctly first, because they never count the shorter ones.

Common mistakes

Sorting by k first. This is the most common wrong key. The program runs to the end and prints a line that breaks clues. In the real run above the output was valid=False. Python gives no error, so a program without a check would give a wrong answer and no warning. Always run the check on your output when you test.

Sorting shortest first. This also gives no error in Python, because insert adds the person at the end when the index is too large. The result is the valid=False line shown earlier. The check is the only thing that reports the problem. Sort tallest first, and check the output.

Forgetting the tie-break. Sorting by height alone keeps people with the same height in input order, because Python's sort is stable. Take these three people. The sort by height alone gives a broken line:

people = [Person(5, 1), Person(5, 0), Person(6, 0)]
ordered = sorted(people, key=lambda p: -p.height)
line = []
for p in ordered:
    line.insert(p.ahead, p)
print(show(line), valid(line))
print(show(reconstruct(people)), valid(reconstruct(people)))

Output:

[[5, 0], [6, 0], [5, 1]] False
[[5, 0], [5, 1], [6, 0]] True

The first line is wrong. [5, 1] is placed before [5, 0], so when [5, 0] is inserted at the front, it lands in front of [5, 1], which then has two people in front instead of one. The fix is the second key item, p.ahead, which the reconstruct function already uses.

Sorting a tuple. A tuple cannot be changed, so it has no sort method. If you call sort on one, as in (3, 1, 2).sort(), Python raises an error:

AttributeError: 'tuple' object has no attribute 'sort'

Use sorted(...), which returns a new list and works on any iterable. The reconstruct function does the same, so the caller's list is not changed.

Using assignment where you mean insert. queue[p.ahead] = p replaces the person already at that index. It does not push them back. If the index is past the end of the list, Python raises an error:

queue = [Person(7, 0), Person(6, 0), Person(5, 0)]
queue[5] = Person(4, 5)

Output:

IndexError: list assignment index out of range

The rule needs insert, because the people already in the list must move back to make room.

Treating a bad input as a program bug. If you give the code a clue that cannot be satisfied, such as one person with k equal to 3 when no one is in front, insert does not raise an error. The person goes to the front of the list, and the check reports the problem:

print(show(reconstruct([Person(5, 3)])), valid(reconstruct([Person(5, 3)])))

Output:

[[5, 3]] False

The problem promises that inputs are valid, so a False here means the input is wrong, not that the rule is wrong.

Changing a dataclass field. The frozen=True option stops you from editing a person after it is made. Writing to a field raises an error:

p = Person(5, 0)
p.height = 6

Output:

dataclasses.FrozenInstanceError: cannot assign to field 'height'

Build a new Person instead of changing one.

Practice

Exercise 1

Trace the rule by hand for these three clues: [6, 0], [5, 1] and [5, 0]. Give the final line.

Show the answer

Sort by height, tallest first, then by k. The order is [6, 0], then [5, 0], then [5, 1]. Insert [6, 0] at index 0, giving [6, 0]. Insert [5, 0] at index 0, giving [5, 0] [6, 0]. Insert [5, 1] at index 1, giving [5, 0] [5, 1] [6, 0]. Check [5, 1]: one person in front, [5, 0], is 5 tall, so the count is 1. Check [6, 0]: nobody in front is at least 6 tall, so the count is 0. The final line is [5, 0] [5, 1] [6, 0].

Exercise 2

Is the line [3, 0] [4, 0] valid? Use the check from this lesson.

Show the answer

Yes. For [3, 0], nobody is in front, so the count is 0, which matches. For [4, 0], the one person in front is [3, 0], who is 3 tall. Three is less than 4, so the person does not count. The count is 0, which matches. Both clues hold, so the line is valid.

Exercise 3

Why can the valid input [5, 0] and [5, 0] never appear? Explain in two or three sentences.

Show the answer

Both people need zero people in front who are at least 5 tall. Whichever one stands second has the other person in front, and that person is 5 tall, so the second person's count is at least 1. That breaks the clue. No line can satisfy both clues, so the problem never gives this input.

Exercise 4

Suppose the list queue holds 3 people, and the code runs queue.insert(5, p) for a person with k equal to 5. What happens? Then predict what queue[5] = p does on the same list.

Show the answer

queue.insert(5, p) does not raise an error. The person is added at the end of the list, which is position 3. The check will then report the line as invalid, because a k of 5 needs at least 5 people in front. queue[5] = p raises IndexError: list assignment index out of range, because assignment needs the index to exist already.

Exercise 5

Predict the output of reconstruct for the input [5, 1], [5, 0] and [6, 0]. Then say what the line would be if the second item of the sort key were removed, so that the key is only -p.height.

Show the answer

With the full key, the sort gives [6, 0], [5, 0], [5, 1], and the line is [5, 0] [5, 1] [6, 0], which is valid. Without the second item, the sort keeps the input order for the two people of height 5, so [5, 1] comes first. Inserting it at index 1 into a list that holds only [6, 0] gives [6, 0] [5, 1]. Inserting [5, 0] at index 0 gives [5, 0] [6, 0] [5, 1], and the check says the line is not valid. The fix is the tie-break, which keeps the smaller k first.

Summary

• Sort the clues tallest first, and break ties by the smaller count first. A tuple key does both in one line.
• Insert each person at index k into a list. The index equals the number of taller-or-equal people in front.
• During one height group the list holds only people at least that tall, so the index and the count are the same thing.
• A shorter person never changes a taller person's count, so later insertions cannot break earlier clues.
• Python's insert does not raise an error for a bad index. Always run the check on the output.