41. Two Sum: Latency Budget

Problem

A real-time voice pipeline strings together several stages end to end (ASR, NLU, retrieval, LLM generation, TTS) and is over its end-to-end latency SLA by a known number of milliseconds.

An eng team has profiled a list of candidate optimizations, each with an estimated latency savings in ms if adopted, but only has budget to ship two of them this sprint. Find the indices of the two optimizations whose combined savings exactly close the latency gap.

Source: src/41_latency_budget_two_sum.py

def two_sum_latency_budget(savings_ms: list[int], target_ms: int) -> tuple[int, int] | None:
    ...

Examples:
>>> two_sum_latency_budget([40, 15, 25, 10], 50)
(0, 3)

>>> two_sum_latency_budget([5, 10, 15], 100)
# None

Step-by-Step Approach

1. Recognize this as classic Two Sum: find two elements summing to a target, which has an O(n) hashmap solution beating the naive O(n²) all-pairs check.
2. Walk the list once, keeping a map from a savings value already seen to its index.
3. At each new value, compute its complement (target_ms - savings) and check whether that complement is already in the map.
4. If it is, the current index paired with the stored index is the answer — return immediately, which naturally returns the first valid pair found in scan order.
5. If it isn't, record the current value's index in the map and continue to the next element.
6. If the loop finishes with no match, no pair sums to the target — return None.

The key insight is that you never need to look ahead: by the time you're standing on index i, every earlier value is already in the map, so checking for target - savings_ms[i] is enough to find any valid pair without ever comparing all O(n²) pairs explicitly.

Reference solution

def two_sum_latency_budget(savings_ms: list[int], target_ms: int) -> tuple[int, int] | None:
    # single pass with a value->index map, O(n) time, O(n) space
    seen: dict[int, int] = {}
    for i, savings in enumerate(savings_ms):
        complement = target_ms - savings
        if complement in seen:
            # first pair found wins, in scan order
            return (seen[complement], i)
        seen[savings] = i
    return None


TEST_CASES = [
    {"input": {"savings_ms": [40, 15, 25, 10], "target_ms": 50}, "expected": (0, 3)},
    {"input": {"savings_ms": [5, 10, 15], "target_ms": 100}, "expected": None},
    {"input": {"savings_ms": [20, 20], "target_ms": 40}, "expected": (0, 1)},
    {"input": {"savings_ms": [12, 18, 7, 23], "target_ms": 30}, "expected": (0, 1)},
    {"input": {"savings_ms": [8], "target_ms": 8}, "expected": None},
]


def main():
    for i, case in enumerate(TEST_CASES):
        savings_ms = case["input"]["savings_ms"]
        target_ms = case["input"]["target_ms"]
        expected = case["expected"]
        print(f"Test {i}: two_sum_latency_budget(savings_ms={savings_ms}, target_ms={target_ms})")
        seen: dict[int, int] = {}
        for idx, savings in enumerate(savings_ms):
            complement = target_ms - savings
            if complement in seen:
                print(f"  idx {idx} savings={savings}: complement {complement} seen at idx {seen[complement]} -> match")
                break
            seen[savings] = idx
            print(f"  idx {idx} savings={savings}: no complement yet, remember it")
        result = two_sum_latency_budget(savings_ms=savings_ms, target_ms=target_ms)
        assert result == expected
        print(f"PASSED: {result}")
    print(f"All {len(TEST_CASES)} test cases passed.")


if __name__ == "__main__":
    main()

Key Functions & Tricks

• seen: dict[int, int] — maps a savings value already scanned to its index
• complement = target_ms - savings — the value that would complete a match with the current element
• if complement in seen — O(1) average lookup that replaces an inner O(n) scan
• return (seen[complement], i) — returns the earlier index first, then the current one

How to Recognize This Pattern