Sorting Pattern: Template + 401 LeetCode Problems

What the sorting pattern is

Sorting is rarely the answer on its own; it is the setup that makes the answer obvious, and the skill being tested is choosing the key. Sorting intervals by start time puts every overlap next to its partner, so merging becomes one linear pass. Sorting by finishing time is what makes the greedy interval choice correct. Sorting an array before a two-pointer scan is what lets a comparison decide which pointer to move. Once the input is ordered, duplicates are adjacent, the median is at a known index, and binary search becomes available — three capabilities that between them dissolve a lot of problems. The cost is worth watching: O(n log n) is usually the cheap part next to whatever follows, but when the values are small integers, counting or bucket sort does it in linear time, and when only the kth element is wanted, quickselect gets it in expected linear time without sorting the rest. In Python the `key` argument, and tuples as keys for multi-level ordering, express nearly all of this without a comparator.

When to use it

• —Adjacency in sorted order is what makes the answer visible: overlaps, duplicates, closest pairs.
• —A greedy choice depends on processing items in a specific order.
• —Grouping is by a canonical form that sorting produces, such as sorted letters for anagrams.
• —Only the kth largest is needed and n is large — that is quickselect, not a full sort.
• —Values are bounded small integers, where counting sort beats the comparison lower bound.

The sorting template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 401 problems listed below.

def merge_intervals(intervals):
    intervals.sort(key=lambda pair: pair[0])   # sorting makes overlaps adjacent
    merged = []

    for start, finish in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], finish)   # extend the open interval
        else:
            merged.append([start, finish])

    return merged

Complexity characteristics

Time

O(n log n)

Auxiliary space

O(n) for Python's Timsort

Comparison sorts cannot beat n log n, and that bound is usually the cheap part next to whatever the sorted order then enables. Two escapes exist when the input allows them: counting, bucket and radix sort run in linear time when the values are bounded small integers, and quickselect finds the kth element in expected O(n) without ordering the rest. Python's sort is stable and allocates a temporary buffer, so it costs O(n) space rather than the O(log n) an in-place quicksort would suggest.

All 401 sorting LeetCode problems

Every problem in the library the sorting pattern applies to, grouped by LeetCode's own difficulty rating. 346 of the 401 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Sorting pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.