Pattern Choice Example: The Closest Departures on Two Timetables

Two sorted lists and one item wanted from each: two pointers walk both lists once, and searching one list from the other sometimes wins.

Two sorted inputs and a question about one item from each point to two pointers, one in each list, and the choice is justified by weighing it against the other patterns that could answer the same question. A passenger changing between two bus lines wants the shortest wait, so the question is which departure on line A is closest in time to a departure on line B. In minutes past the hour, line A leaves at 3, 9, 14 and 22, and line B at 6, 11, 19, 27 and 30.

Which two departures are closest, and how far apart are they?

9 on line A and 11 on line B, 2 minutes apart. No other pair is that close; the next smallest gap is 3 minutes.

Reading the decision in order, the input is not a list of nodes, a tree, a grid or a set of intervals, and the question is about pairs drawn from sorted data, which is the two pointers branch. One pointer, i, starts at line A's first departure and the other, j, at line B's. Each step records the gap between the two departures and moves the pointer at the earlier one, because moving the later one could only widen the gap. The trace shows both lists in one row, line A before the dot and line B after it.

Two pointers over both timetables

Inputline A 3 9 14 22, line B 6 11 19 27 30

3 and 6: gap 3
1. 3i
2. 9
3. 14
4. 22
5. ·
6. 6j
7. 11
8. 19
9. 27
10. 30
3 is earlier, so i moves on
9 and 6: gap 3
1. 3
2. 9i
3. 14
4. 22
5. ·
6. 6j
7. 11
8. 19
9. 27
10. 30
6 is earlier, so j moves on
9 and 11: gap 2
1. 3
2. 9i
3. 14
4. 22
5. ·
6. 6
7. 11j
8. 19
9. 27
10. 30
The best gap, 2 minutes; 9 is earlier, so i moves on
14 and 11: gap 3
1. 3
2. 9
3. 14i
4. 22
5. ·
6. 6
7. 11j
8. 19
9. 27
10. 30
11 is earlier, so j moves on
14 and 19: gap 5
1. 3
2. 9
3. 14i
4. 22
5. ·
6. 6
7. 11
8. 19j
9. 27
10. 30
14 is earlier, so i moves on
22 and 19: gap 3
1. 3
2. 9
3. 14
4. 22i
5. ·
6. 6
7. 11
8. 19j
9. 27
10. 30
19 is earlier, so j moves on
22 and 27: gap 5
1. 3
2. 9
3. 14
4. 22i
5. ·
6. 6
7. 11
8. 19
9. 27j
10. 30
22 is earlier, so i moves off line A and the walk ends

ResultThe closest departures are 9 and 11, 2 minutes apart, after 7 comparisons.

Three other approaches could answer the question, and the listing runs two of them beside the pointers.

departures.pypy

from bisect import bisect_left

line_a = [3, 9, 14, 22]
line_b = [6, 11, 19, 27, 30]


def closest_two_pointers(a: list[int], b: list[int]) -> tuple[int, int, int]:
    i = j = compared = 0
    best = (abs(a[0] - b[0]), a[0], b[0])
    while i < len(a) and j < len(b):
        compared += 1
        best = min(best, (abs(a[i] - b[j]), a[i], b[j]))
        if a[i] < b[j]:
            i += 1
        else:
            j += 1
    return best[1], best[2], compared


def closest_by_search(short: list[int], long: list[int]) -> tuple[int, int, int]:
    best, searches = None, 0
    for value in short:
        searches += 1
        at = bisect_left(long, value)
        for k in (at - 1, at):
            if 0 <= k < len(long):
                candidate = (abs(value - long[k]), value, long[k])
                best = candidate if best is None else min(best, candidate)
    return best[1], best[2], searches


a, b, compared = closest_two_pointers(line_a, line_b)
print(f"two pointers: {a} and {b}, {abs(a - b)} minutes apart, after {compared} comparisons")
a, b, searches = closest_by_search(line_a, line_b)
print(f"binary search of line B: {a} and {b}, after {searches} searches")
pairs = sorted((abs(x - y), x, y) for x in line_a for y in line_b)
print(f"every pair: {len(pairs)} pairs, closest {pairs[0][1]} and {pairs[0][2]}, next gap {pairs[1][0]}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

two pointers: 9 and 11, 2 minutes apart, after 7 comparisons
binary search of line B: 9 and 11, after 4 searches
every pair: 20 pairs, closest 9 and 11, next gap 3

All three agree on 9 and 11. Each approach wins in a different situation, which is the justification the choice needs.

Ways to find the closest pair across two sorted lists of n and m items
Approach	Cost	When it wins
Two pointers	O(n + m)	Both lists sorted and of similar length
Binary search of the longer list for each item of the shorter	O(n log m)	One list far shorter than the other, such as 10 departures against a million
A hash map of one list	O(n + m) on average	Never here: it finds equal values, not the closest
Every pair	O(n · m)	Only when the lists are tiny or unsorted and cannot be sorted

Two pointers is the choice for these timetables, at 7 comparisons against 20 pairs. With 10 departures on one line and a million on the other, the binary search would make 10 searches of about 20 steps each, where the pointers could walk most of the million.

Algorithms

← → move through sections and cards