Sort as Preprocessing

Concepts covered: Sorting

Many problems that look hard on raw input become a single pass once the input is sorted. Sorting puts equal values next to each other, places the closest values side by side, lines up overlapping intervals, and gives 2 pointers the order their proof needs. A sort costs more than one pass, but far less than checking every pair.

Closest pair: compare only neighbours

Which 2 play timestamps, in seconds, sit closest together? In sorted order the closest pair must be neighbours: a value between them would be closer to each of them than they're to each other. One pass over neighbouring pairs, keeping the smallest gap so far, replaces the check of every pair.

timestamps = [905, 140, 612, 150, 880, 600]
ordered = sorted(timestamps)
best_gap = None
for a, b in zip(ordered, ordered[1:]):
    gap = b - a
    if best_gap is None or gap < best_gap:
        best_gap = gap
        pair = (a, b)
print(ordered)
print(pair, best_gap)

Output:

[140, 150, 600, 612, 880, 905]
(140, 150) 10

Merging overlapping sessions

Listening sessions arrive as (start, end) hours in any order, and overlapping ones should become one block. After sorting by start, a session can only overlap the block built just before it, so each session either extends the last block or opens a new one.

sessions = [(9, 12), (1, 4), (3, 6), (14, 15), (11, 13)]
sessions.sort()
merged = [list(sessions[0])]
for start, end in sessions[1:]:
    last = merged[-1]
    if start <= last[1]:
        last[1] = max(last[1], end)
    else:
        merged.append([start, end])
print(merged)
[[1, 6], [9, 13], [14, 15]]

(3, 6) starts at 3, inside [1, 4], so the block grows to [1, 6]. (9, 12) starts after 6 and opens a new block, which (11, 13) then stretches to 13. The max(last[1], end) matters for a session lying fully inside a block, such as (2, 3) inside [1, 6], which must not shrink it.

Sorting without losing positions

Sorting rearranges values, so the positions from the original list are lost. When the answer must be original positions, sort the positions themselves, using each position's value as the sort key. The pair walk from the first section then returns indexes into the unsorted list:

def two_sum_sorted(nums, target):
    order = sorted(range(len(nums)), key=lambda i: nums[i])
    left, right = 0, len(order) - 1
    while left < right:
        total = nums[order[left]] + nums[order[right]]
        if total == target:
            return sorted([order[left], order[right]])
        if total < target:
            left += 1
        else:
            right -= 1
    return None

print(two_sum_sorted([11, 2, 15, 7], 9))

Output:

[1, 3]
Dict lookup in one pass
  • Works on unsorted input as it arrives
  • Stores one entry per value seen
  • Answers exact matches only
Sort, then walk or search
  • Pays for one sort up front
  • Can run in place with 2 indexes
  • Answers ordering questions, such as which values are closest or fall in a range

Sort once, answer many questions

A sorted list also supports binary search. bisect_right(lengths, x) returns how many values are at most x, so the program below finds 3 sessions of 10 minutes or less and 2 longer than 20. One sort pays for any number of these questions.

from bisect import bisect_right

lengths = sorted([12, 3, 45, 7, 30, 3, 18])
print(lengths)
print(bisect_right(lengths, 10))
print(len(lengths) - bisect_right(lengths, 20))

Output:

[3, 3, 7, 12, 18, 30, 45]
3
2

Every pass in this section trusts the order the sort produced. The closest-pair loop assumes the nearest values are neighbours, the merge assumes a session can only overlap the last block, and bisect_right assumes no larger value sits before a smaller one. Remove the sort and each loop still runs to the end with no exception. The assumption is false, though, so the output is a wrong answer that looks like a real one.

This version of the merge leaves out the sort. What does it print?

sessions = [(9, 12), (1, 4), (3, 6)]
merged = [list(sessions[0])]
for start, end in sessions[1:]:
    last = merged[-1]
    if start <= last[1]:
        last[1] = max(last[1], end)
    else:
        merged.append([start, end])
print(merged)

A missing sort sometimes leaves a visible trace. In the closest-pair loop run on arrival order, b - a goes negative whenever a later timestamp is smaller, as 140 - 905 = -765 is. A negative gap is smaller than every real gap, so it wins. Any gap below 0 means the order the loop relies on is missing.

Capstone: the fullest gap

This one combines 3 patterns: sort the input, walk 2 pointers inward, and keep the best total so far. A total that fits the gap is a candidate, and moving left up tries a larger one; a total that overflows moves right down to a shorter track.

About this lesson

This section is part of the Problem Solving: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.