Quicksort intuition
Quicksort is the other famous divide-and-conquer sort, and the default in many languages' standard libraries. Rather than splitting by position at the middle, it splits by value.
- Pick a pivot value.
- Partition so that everything smaller than the pivot goes left and everything bigger goes right.
- Quicksort each side.
After partitioning, the pivot is in its final sorted position and the two sides never interact again. That last point is what makes the recursion clean, since neither side can ever need an element from the other.
On average the pivot lands near the middle, which gives the same halving arithmetic as merge sort and O(n log n).
If the pivot is always the smallest or largest value, though, one side gets everything and the cost degrades to O(n²). That is the trade: usually faster in practice than merge sort, with a bad worst case rather than a guaranteed bound.
Quicksort with three buckets
This readable version partitions into smaller, equal, and bigger, then sorts the two outer buckets the same way.
def quicksort(nums): if len(nums) <= 1: return nums pivot = nums[len(nums) // 2] smaller = [n for n in nums if n < pivot] equal = [n for n in nums if n == pivot] bigger = [n for n in nums if n > pivot] return quicksort(smaller) + equal + quicksort(bigger) print(quicksort([9, 4, 7, 1, 4, 8, 2])) print(quicksort([]))
Output
[1, 2, 4, 4, 7, 8, 9] []
The equal bucket is what handles duplicates cleanly. The input has two 4s, and both land in equal and pass through untouched, so neither recursive call ever sees them.
That bucket also guarantees progress. Since the pivot is always in equal, both recursive calls get strictly smaller lists, which is what stops the recursion from looping on a list of identical values.
Picking the middle element rather than the first is a small but real defense. It makes an already-sorted input split evenly instead of triggering the worst case.
The empty list returns immediately through the base case, and len(nums) <= 1 covers both empty and single-element inputs.
The honest caveat is memory. Real quicksort partitions in place with O(log n) stack space, while this version builds three new lists per call, trading its main advantage over merge sort for readability.
The worst case is triggered when every pivot turns out to be the smallest or largest remaining value, so one side of each partition is empty.
Quicksort's speed depends on the pivot splitting the list into two decently sized parts. An extreme pivot removes only itself from the problem, so the remaining size shrinks by 1 per level rather than by half.
That gives n levels instead of log₂ n, and each level still does O(n) partitioning work, so the total is O(n²).
The classic way to hit it is picking the first element of an already-sorted list, which is exactly the input a naive implementation is most likely to meet in practice.
Real implementations avoid it by choosing random pivots or the median of a few samples. That makes the bad case astronomically unlikely rather than impossible, which is why quicksort is fast in practice while merge sort keeps the stronger guarantee.
The sort-then-solve pattern
In interviews you will rarely implement a sort. You will call sorted(), which is Python's Timsort at O(n log n), as step one of a bigger solution.
What sorting buys is structure, and three consequences come up repeatedly.
- Closest values become neighbors. Finding the minimum gap between any two numbers drops from O(n²) pair-checking to a sort plus one scan of adjacent pairs.
- Overlaps line up. Sorting meetings by start time means conflicts can only occur between neighbors, so an all-pairs check becomes a single pass.
- Binary search and two pointers unlock, which is lesson 2-2 and the whole of unit 4.
The common thread is locality. Sorting converts a global question, about any two elements anywhere, into a local one about adjacent elements.
So when a problem feels like it needs all-pairs comparisons, ask whether sorting would make the answer local. Spending O(n log n) to avoid O(n²) is almost always a win, since the sort is cheaper than the scan it replaces.
min_gap
The smallest difference between any two numbers, found by sorting first.
def min_gap(nums): nums = sorted(nums) return min(nums[i + 1] - nums[i] for i in range(len(nums) - 1)) print(min_gap([8, 1, 4, 13])) print(min_gap([10, 100, 7]))
Output
3 3
After sorting, the two closest values in the whole list must sit next to each other, and the argument for that is worth having ready. If two values were closest but not adjacent, some third value would sit between them, and that value would be closer to each of them than they are to each other.
So the scan only compares neighbors, and range(len(nums) - 1) is what keeps i + 1 in bounds.
For [8, 1, 4, 13] the sorted list is [1, 4, 8, 13], with gaps of 3, 4, and 5, so the answer is 3.
The second case is the one that shows the value of sorting. In the original order [10, 100, 7] the closest pair is 10 and 7, which are not adjacent, and sorting to [7, 10, 100] brings them together.
The total cost is O(n log n) for the sort plus O(n) for the scan, against O(n²) for comparing every pair.
Yes, one person can attend all three.
After sorting by start time, only neighbors need checking. The second meeting starts at 10 exactly as the first ends at 10, which the problem allows, and the third starts at 13, comfortably after the second ends at 11.
The reason neighbors suffice is the sort. Once meetings are ordered by start time, a conflict can only happen between a meeting and the one immediately after it, since any later meeting starts even later.
So the test is start[i + 1] >= end[i] across the list, which is a single O(n) pass.
That is the classic sort-then-solve win. The naive version compares every pair of meetings at O(n²), and sorting converts it into a scan of adjacent pairs.
The boundary case is worth being explicit about in an interview. Whether a meeting may start exactly when another ends changes the comparison from >= to >, and it is the kind of detail worth asking about rather than assuming.