L53 · Sorting & Custom Comparators

Series: LeetCode — From Basics to Interview-Ready · Session 53 / 65 · Phase 3 · Advanced & specialised

Watch first

Why this session exists

Everyone knows how to call sorted(). Nobody gets asked to call sorted(). What interviews probe is the layer just underneath: can you partition an array in place, can you select the Kth element without paying for a full sort, and can you define an ordering when no single key expresses it.

Quickselect is the headline. Finding the Kth largest element with a heap is O(n log k) and is the answer most candidates give. Quickselect gives O(n) average time and is roughly fifteen lines. Producing it unprompted signals that you understand partitioning as a primitive rather than sorting as a black box — and that difference is exactly what a senior loop is listening for.

The comparator half matters for a different reason. "Largest Number" — arrange integers so the concatenation is maximal — has no sort key. There is no function f(x) such that sorting by f gives the right answer. You need a pairwise rule: a comes before b if a+b > b+a. Recognising that a problem needs a comparator rather than a key is a small, sharp skill and it appears more often than you would think.

Blank-file warm-up

Five minutes, empty file, no notes. Write both of these from memory:

1. Dutch national flag — partition an array of three values (0, 1, 2) in a single pass, in place, using three pointers.
2. Partition-based select — the quickselect skeleton: pick a pivot, partition, recurse into exactly one side.

If the three-pointer loop comes out wrong, that is today's finding. The DNF loop is the single most commonly mis-remembered short algorithm in the entire interview canon, because the mid pointer advances in two of the three branches and not the third, and that asymmetry does not feel natural.

Pattern anatomy

Both halves of this session share one primitive: partition. You choose a value, sweep the array once, and rearrange so elements land on the correct side of that value. Everything else here is a variation on where the boundaries are and what you do afterwards.

The invariant for Dutch national flag, at every point in the loop, is a four-region split of the array:

• [0, low) — all strictly less than the pivot value
• [low, mid) — all equal to the pivot value
• [mid, high] — unclassified, still to be examined
• (high, n) — all strictly greater than the pivot value

The loop runs while mid <= high, and each iteration shrinks the unclassified region by one. That is the whole proof of termination.

def dutch_flag(nums, pivot=1):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] < pivot:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] > pivot:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1          # do NOT advance mid: the swapped-in value is unseen
        else:
            mid += 1
    return nums

The one line that carries all the difficulty is the high -= 1 branch. When you swap with high, the element that arrives at mid came from the unclassified region and has never been examined. Advancing mid there skips it, and the bug is silent on small inputs.

Quickselect uses the same partition idea with a Lomuto-style sweep, then recurses into a single side:

import random
 
def quickselect(nums, k):
    """Return the k-th SMALLEST element (0-indexed k). O(n) average."""
    lo, hi = 0, len(nums) - 1
    while True:
        if lo == hi:
            return nums[lo]
        p = random.randint(lo, hi)                 # randomise: kills adversarial input
        nums[p], nums[hi] = nums[hi], nums[p]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        if store == k:
            return nums[store]
        elif store < k:
            lo = store + 1
        else:
            hi = store - 1

Note the loop instead of recursion — the recursion is tail-position, so converting it to a while True costs nothing and removes any stack-depth concern.

And the comparator skeleton, for orderings that are not expressible as a key:

from functools import cmp_to_key
 
def compare(a, b):
    # return negative if a should come FIRST, positive if b should come first
    if a + b > b + a:
        return -1
    if a + b < b + a:
        return 1
    return 0
 
def largest_number(nums):
    strs = [str(n) for n in nums]
    strs.sort(key=cmp_to_key(compare))
    out = "".join(strs)
    return "0" if out[0] == "0" else out

The cue

You are looking at a sorting-and-selection problem when the statement contains one of these tells:

1. "Kth largest / Kth smallest / median" and the constraints allow mutating the input. That is quickselect. If the input is a stream or must not be mutated, it is a heap instead.
2. "Sort in place with O(1) extra space" and a tiny value domain — three colours, two categories, even/odd. Small domain plus in-place plus one pass equals partition, not a comparison sort.
3. "Arrange / order these so that the resulting X is maximal" where X is a concatenation, a ratio, or a pairing. If you cannot write down a single number per element that produces the ordering, you need a pairwise comparator.
4. "Sort by A, then by B descending, then by C" — that is a key tuple with a negation, not a comparator. Reach for key=lambda x: (x.a, -x.b, x.c) and only escalate to cmp_to_key when negation is impossible (strings, non-numeric).
5. Counting-style constraints — values bounded by a small constant while n is large. That is counting sort territory: O(n + range) beats O(n log n).

The distinction in tell 3 versus tell 4 is the whole point. A key is a function of one element. A comparator is a function of two. If the correct order of a and b depends on both of them jointly and cannot be decomposed, you have no key.

Guided solve

Sort Colors — an array of 0s, 1s and 2s. Sort it in one pass, in place, with constant extra space.

Start with what the naive answers are, because articulating why you are rejecting them is worth real points.

The two-pass counting approach is legitimate: count how many 0s, 1s and 2s there are, then overwrite the array. O(n) time, O(1) space, dead simple, and it works. The reason it is not the intended answer is the "one pass" clause. Say this out loud in an interview — you show you have a correct baseline before you reach for the clever thing.

The one-pass answer is Dutch national flag with pivot 1. Maintain three pointers as described above. Walk mid forward:

• nums[mid] == 0 → it belongs in the left region. Swap it with nums[low]. The value arriving at mid came from [low, mid), which is the all-ones region, so it is a 1 and is already correctly classified. Safe to advance both low and mid.
• nums[mid] == 2 → it belongs at the right end. Swap with nums[high], decrement high. The arriving value came from the unclassified region. Do not advance mid.
• nums[mid] == 1 → already in the correct middle region. Advance mid only.

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        v = nums[mid]
        if v == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif v == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1

Trace it once on [2, 0, 1] by hand before you trust it. mid=0 sees a 2, swaps to the end giving [1, 0, 2] with high=1, mid unchanged. mid=0 now sees a 1, advances. mid=1 sees a 0, swaps with low=0 giving [0, 1, 2], both advance. mid=2 > high=1, loop ends. Correct, and the trace takes twenty seconds — do it in the interview, it demonstrates the invariant better than any explanation.

Termination: mid increases or high decreases on every iteration, so the gap high - mid strictly shrinks. One pass, O(n) time, O(1) space.

Solo timed

Fifteen minutes each, timer visible, no editorial until the timer fires.

• Kth Largest via quickselect — remember that the Kth largest in a zero-indexed array is the len(nums) - k-th smallest. Get that conversion right before you write the partition.
• Largest Number — the ordering is pairwise, not a key. And there is one edge case that fails every naive submission; think about what the answer should be when the input is all zeros.

If you finish both early, implement Sort an Array (merge sort from scratch, no built-in sort) — it is the cleanest place to practise the merge step you will need again if a linked-list sort shows up.

Common failure modes

Advancing mid after the high swap. Covered above and worth repeating, because it produces correct output on many small inputs and fails only when the swapped-in element was a 0. Test with [2, 0, 1] and [2, 2, 0].

Off-by-one in the Kth-largest conversion. k=1 means the largest, which is index n - 1 in sorted order. So the target index is n - k, not n - k - 1 and not k - 1. Write the mapping down before writing the loop.

Non-random pivot on sorted input. Always taking hi as the pivot degrades quickselect to O(n²) on an already-sorted array — which is exactly what a hostile test suite feeds you. One random.randint line fixes it. Mention this even if you skip the line; the awareness is what is being measured.

Returning cmp_to_key(compare)(x) semantics backwards. The convention is: negative means a sorts before b. Getting the sign inverted produces a perfectly reversed output and no error, so it looks like a logic bug rather than a convention bug. State the convention aloud as you write the function.

Forgetting that largest_number can produce leading zeros. Input [0, 0] sorts to "00", and the expected answer is "0". One line, always forgotten.

Worked variant — Largest Number, the comparator that has no key

This is the problem that proves comparators are not a stylistic alternative to keys. Arrange a list of non-negative integers so their concatenation is the largest possible number.

from functools import cmp_to_key
 
def largest_number(nums: list[int]) -> str:
    strs = [str(x) for x in nums]
 
    def compare(a: str, b: str) -> int:
        # The pairwise rule: a should come first iff a+b > b+a.
        # cmp contract: negative -> a first, positive -> b first, 0 -> tie.
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0
 
    strs.sort(key=cmp_to_key(compare))
 
    # Edge case: all zeros concatenate to "000...", which must be "0".
    # Checking the FIRST element suffices — it is the largest, so if it
    # is "0" then every element is.
    if strs[0] == "0":
        return "0"
    return "".join(strs)
 
assert largest_number([3, 30, 34, 5, 9]) == "9534330"
assert largest_number([0, 0]) == "0"

Why no key exists. A key function maps each element to a value independently of the others, and sorting by that value must reproduce the desired order. Here the correct position of 3 relative to 30 depends on comparing "330" against "303" — a fact about the pair, not about either element alone. No independent map can encode it. That is the definition of a genuinely pairwise ordering, and recognising it is the skill.

Why the comparator is a valid ordering. This is the follow-up question, and it is not obvious. The relation must be transitive, or sort may produce nonsense rather than an error. It is transitive: a + b > b + a is equivalent to comparing the two numbers as rationals scaled by their lengths, which induces a total order. You do not need the full proof at the whiteboard, but you must know the question is real — an inconsistent comparator is a genuine bug class, not a theoretical worry.

Cost. cmp_to_key wraps every element in an object whose comparison calls back into Python, so it is meaningfully slower than a native key. Use a key whenever one exists; reach for cmp_to_key only when, as here, one provably does not.

Memory hook — "key if you can, cmp if you must"

The decision procedure, in one line: key if you can, cmp if you must.

• Key — ask whether you can score each element on its own, without looking at any other element, such that sorting by the score gives the answer. Usually yes. Tuples cover multi-level sorts, and for mixed directions on numbers, negate one component: key=lambda p: (p[0], -p[1]).
• Cmp — only when the correct order of a and b depends on both together. Then write a function returning negative, zero, or positive and wrap it in cmp_to_key. Test transitivity mentally before trusting it.

For partitioning the peg is "low, mid, high — mid does the walking." In Dutch national flag only mid scans. On a small value swap with low and advance both; on a large value swap with high and advance only high, because the element you just pulled in from the right end has not been examined yet. Advancing mid there is the single most common bug in the routine.

For quickselect the peg is "partition, then pick a side." Quicksort recurses into both halves; quickselect recurses into one and throws the other away. That discarded half is why the geometric series collapses from n log n to 2n.

What interviewers actually ask

Sorting questions are rarely about sorting. They are about whether you can operate one level below the library call.

• 215 · Kth Largest Element in an Array (Medium) — Amazon, Meta, Google, Bloomberg. Probing quickselect. Follow-up: "what is the worst case and how do you avoid it?" — O(n²) on adversarial pivots; randomise the pivot choice.
• 75 · Sort Colors (Medium) — Amazon, Microsoft, Meta. Probing Dutch national flag. Follow-up: "one pass, constant space" — which rules out counting sort and forces the three-pointer version.
• 179 · Largest Number (Medium) — Amazon, Google, Apple. Probing comparator recognition. Follow-up: "prove your comparator is a valid total order."
• 937 · Reorder Data in Log Files (Medium) — Amazon. Probing tuple keys with mixed criteria and stability — an Amazon staple specifically.
• 56 · Merge Intervals (Medium) — Amazon, Meta, Google, Bloomberg. Probing that sorting by start is the enabling move, not the answer.
• 148 · Sort List (Medium) — Amazon, Meta, Microsoft. Probing merge sort on a linked list, where the array-oriented routines do not apply.
• 973 · K Closest Points to Origin (Medium) — Amazon, Meta. Probing the heap-versus-quickselect tradeoff explicitly; both are accepted, and naming both is the strong answer.

The escalation to watch: "can you do better than sorting?" Whenever you have reached for a full sort, be ready to say whether partial ordering suffices — quickselect, a size-K heap, or counting sort when the value range is bounded.

Complexity

Dutch national flag: O(n) time — each iteration either advances mid or retreats high, and they can only meet once. O(1) space, all swaps in place.

Quickselect: O(n) expected time. Each partition costs work linear in the current segment length, and with a random pivot the expected segment shrinkage is a constant factor, so the total is a geometric series bounded by about 2n. Worst case O(n²) when every pivot is the extreme value — probability of this happening repeatedly with random pivots is vanishingly small. O(1) extra space with the iterative form.

Comparator sort: O(n log n) comparisons, but each comparison in the largest_number case costs O(d) where d is the digit length, giving O(n·d·log n). Space is O(n) for the string conversion. Note that cmp_to_key wraps every element in a Python object, so it is measurably slower than a plain key sort — use a key whenever a key exists.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Sort Colors goes into the queue at whatever status today's blank-file attempt earned. If the Dutch flag loop came out wrong from memory, it is failed regardless of whether you eventually solved it — the queue tracks retrieval, not eventual success.