23. Two-Pointer Latency Pair to Hit a Budget

Problem

A benchmarking run produces a sorted list of per-request latency readings (in milliseconds). Given a target combined budget, find two distinct readings whose sum exactly equals the budget — for example, pairing a fast and a slow request so a batch's total latency lands on a specific target.

Return their indices (i, j) with i < j, or None if no such pair exists. Because the input is already sorted, this must run in O(n) time using two pointers, without a nested loop or an extra hash set.

Source: src/23_two_pointer_latency_pair.py

def find_pair_with_budget(latencies: list[int], budget: int) -> tuple[int, int] | None:
    ...

Examples:
>>> find_pair_with_budget([2, 7, 11, 15], 9)
(0, 1)

>>> find_pair_with_budget([1, 2, 3, 4, 6], 10)
(3, 4)

Step-by-Step Approach

1. Recognize that "sorted array, find a pair summing to a target" is the signature two-pointer setup — a nested loop would be O(n²), and a hash set would use extra space that isn't needed once the array is already sorted.
2. Place one pointer at the start (smallest value) and one at the end (largest value) of the array.
3. Compute the sum of the two pointed-to values. If it equals the budget, that pair is the answer.
4. If the sum is too small, the only way to increase it is to move the left pointer inward (the array is sorted, so this strictly increases the smaller value). If the sum is too large, move the right pointer inward instead.
5. Repeat until the pointers meet or cross. If no exact match was found by then, no valid pair exists.
6. Handle the trivial cases directly: fewer than two elements can never produce a pair, so the loop naturally never executes and the function returns None.

The key insight is that sortedness turns "which pointer should move" into a deterministic decision — because moving the left pointer can only increase the sum and moving the right pointer can only decrease it, each step provably eliminates at least one candidate pair from consideration, guaranteeing O(n) total work.

Reference solution

def find_pair_with_budget(latencies: list[int], budget: int) -> tuple[int, int] | None:
    left, right = 0, len(latencies) - 1
    while left < right:
        total = latencies[left] + latencies[right]
        if total == budget:
            return (left, right)
        elif total < budget:
            left += 1  # sum too small: only increasing the smaller value can help
        else:
            right -= 1  # sum too large: only decreasing the larger value can help
    return None

Key Functions & Tricks

• left, right = 0, len(latencies) - 1 — start pointers at the two extremes of the sorted range
• while left < right — the pointers meeting or crossing is the natural termination condition
• Monotonic pointer movement — sortedness guarantees moving left only increases the sum and moving right only decreases it, so no candidate pair is ever skipped
• O(n) time, O(1) extra space — strictly better than the O(n) time / O(n) space hash-set approach once the input is sorted

How to Recognize This Pattern