Abstract / Summary

Arrange people in a queue by sorting them shorter to taller and inserting each at the index matching their required count.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 75% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Indexed Tree
• Segment Tree
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “queue reconstruction by height” problem. It receives a list of people, each represented by a pair [height, k] where height is the person's stature and k denotes the number of people in front of this person who have a height greater than or equal to height. The algorithm builds the final queue in a deterministic order that satisfies all k constraints.

Key Steps

Sorting the Input

The first major operation orders the people list so that taller individuals are processed before shorter ones, and for equal heights the original k values are respected in ascending order. This is achieved with a single sort call that uses a composite key:

people.sort(key = lambda x : -x[0]*10**7 + x[1])

The lambda expression creates an integer key by scaling the negative height (-x[0]) with a large factor (10**7) and then adding the k value (x[1]). Because the factor is sufficiently large to dominate the addition, the sort effectively orders by descending height first and by ascending k second. This compact representation avoids constructing a tuple for each element, reducing the overhead of the comparison function.

Incremental Insertion

After sorting, the algorithm iterates over the ordered list and inserts each person into the result list at the index specified by their k value:

result = []
for p in people:
    result.insert(p[1], p)

The insert operation places the current person at the exact position where exactly p[1] taller or equal-height people already exist in front of them. Since taller people have already been placed, the insertion respects the required count for each subsequent, shorter person.

Returning the Constructed Queue

Finally, the fully built list is returned as the answer:

return result

Edge Cases Handled

When the input list is empty, the initial sort call operates on an empty collection, and the subsequent loop does not execute. The function returns an empty list, correctly representing an empty queue.

If multiple people share the same height, the sorting key ensures they are ordered by their k values in ascending order. Consequently, during insertion, a person with a smaller k is placed before a person with a larger k, guaranteeing that the count of taller-or-equal people in front matches each individual's requirement.

When a person's k value equals the current length of the result list, the insert method appends the person at the end. This situation occurs for the tallest person who expects no taller individuals ahead, as well as for any later person whose required count matches the number of already placed taller individuals.

If a k value is zero, the insertion occurs at the front of the list, positioning the person before any previously placed individuals. This correctly models a scenario where no taller or equal-height people should precede the person.

Performance Optimizations

The algorithm consolidates the dual-criteria sort into a single integer key, which eliminates the need for tuple creation and multiple comparison steps per element. By scaling the height with a large constant, the sort leverages the native integer comparison path, which is typically faster than tuple comparison in high-level languages.

Processing the people in descending height order means that each insertion only needs to consider already placed taller individuals. This ordering eliminates the need for additional scans or adjustments after insertion, keeping the work localized to the insert call.

The use of Python’s built-in list.insert method provides an in-place operation that avoids the overhead of constructing intermediate data structures. While each insertion may shift elements, the overall approach benefits from the simplicity of a single pass over the sorted list, avoiding nested loops or auxiliary containers.

By combining sorting and insertion in this manner, the implementation achieves a concise and efficient solution that directly maps the problem constraints to language primitives.

Imagine you are helping a big group of people stand in a line. Each person has a secret number about how tall they are and another number that says how many people taller than them must stand in front of them.

First, the code lines everyone up by looking at the tallest people first. It puts the tallest person at the front because they are the easiest to place. If two people are the same height, it looks at their other number to see who goes first.

Next, it walks through the list of people one by one. It picks up each person and finds the exact spot in the line where they belong. The second number for each person tells the code exactly which position to use. It pushes everyone else over to make room for that person. By the time it finishes, everyone is standing in the perfect spot where all the rules are followed.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python					Go
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis					JS
	FelixFan1122				C#
	fpdjsns	C++
	fsq			Python
	gouthampradhan		Java
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	lzl124631x	C++
	MacJim	C++
	ruoru						Rust
	suxrobGM				C#
	trung-hn			Python
	varunu28		Java
	vli02							C
	vthwang		Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	C#
fpdjsns	C++
fsq	Python
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality