Abstract / Summary

Sort people by height descending and name ascending when heights are equal.

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 85% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Sorting
• String

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 defines a Solution class with a single method sortPeople. The method receives two parallel collections: names, a list of strings, and heights, a list of integers. Its purpose is to produce a new list of names ordered from the tallest person to the shortest. The implementation relies on Python’s built-in sequence utilities to achieve this in a concise, expressive manner.

Key Steps

The core of the algorithm can be broken down into three distinct operations, each expressed by a compact line of code.

The first operation pairs each height with its corresponding name:

zip(heights, names)

By creating tuples of (height, name), the method establishes a direct association that can be leveraged by the sorting routine.

The second operation sorts these tuples in descending order of height:

sorted(zip(heights, names), reverse=True)

The sorted function is invoked with the reverse=True flag, which instructs the underlying Timsort algorithm to arrange the tuples from the largest height to the smallest. Because the tuples are ordered with the height as the first element, the default tuple comparison automatically uses the height as the primary key.

The final operation extracts only the name component from each sorted tuple, preserving the new order:

[n for h, n in sorted(zip(heights, names), reverse=True)]

A list comprehension iterates over the sorted sequence, discarding the height (h) and collecting the name (n). The resulting list is returned as the method’s output.

Edge Cases Handled

When the input lists are empty, the zip call produces an empty iterator, and sorted consequently returns an empty list. The list comprehension then yields an empty list, which matches the expected behavior for a vacuous input.

If the two input lists differ in length, zip truncates to the length of the shorter list. This implicit handling prevents index errors and ensures that every height has a corresponding name. The method therefore gracefully degrades to the longest common prefix of the two sequences.

Duplicate height values are another scenario that the code accommodates naturally. Python’s sorting algorithm is stable, meaning that when two heights are equal, the relative order of their associated names from the original input is retained. Consequently, people with identical heights appear in the output in the same order they were provided.

Performance Optimizations

The implementation makes use of several built-in features that contribute to efficient execution. By employing zip, the code avoids the overhead of manually constructing intermediate data structures; the pairing is performed lazily and in C-level code. The sorted function leverages Timsort, a hybrid sorting algorithm optimized for real-world data patterns, which provides fast performance on partially ordered inputs and minimizes data movement.

The use of a list comprehension for the final extraction is also a performance-friendly choice. List comprehensions are executed in a tight C loop, reducing the interpreter overhead compared to an explicit for loop with append. Moreover, the comprehension directly consumes the sorted iterator, eliminating the need for an additional temporary collection.

Overall, the method achieves its goal with a minimal amount of Python-level code while delegating the heavy lifting to highly optimized standard library components.

Imagine a magical game where you have two separate buckets of cards. In one bucket, there are names of all your friends, and in the other, there are numbers representing how tall each friend is. To make a lineup for a picture, you want to put the tallest friend at the front and the shortest friend at the very end.

The code first picks one name from the name bucket and one height from the height bucket, taping them together into pairs so no one gets lost. After all the pairs are made, it looks at the numbers on the height cards. It moves the pair with the biggest number to the very front of the line and keeps going until the smallest number is at the back. Once everyone is in the right spot, it carefully peels off the height numbers and keeps only the names so you are left with a perfect list of friends arranged from tallest to shortest.

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

Time: loglinear
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	Python		Java	C++					TS
	WalkCCC	Python		Java	C++
	leetcode.ca	Python		Java	C++			Go	Rust	TS
	Progiez	Python		Java	C++
github	chandansgowda	Python
	charles-wangkai			Java
	DimitrisJim						C
	everthis		JS
	fartem					Ruby
	fpdjsns				C++
	fsq				C++
	JoshCrozier		JS
	lkwq007	Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java

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