L53 · Sorting & Custom Comparators

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

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.

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.