29. Two Sum: Handle-Time Budget

Problem

QA reviewers batch pairs of resolved Fin conversations into a single review slot with a fixed time budget. Given the handle-time (in seconds) of each conversation in a queue and the review slot's target budget, find the indices of the two conversations whose combined handle-time exactly equals the target, so they can be paired into one slot.

Return the pair of indices as a tuple, or None if no such pair exists.

Source: src/29_two_sum_handle_time_budget.py

def two_sum(handle_times: list[int], target: int) -> tuple[int, int] | None: ...

two_sum([2, 7, 11, 15], 9)
# -> (0, 1)   (handle_times[0] + handle_times[1] == 2 + 7 == 9)

two_sum([1, 2, 3], 100)
# -> None

Step-by-Step Approach

1. Create an empty dictionary seen mapping a handle-time value already scanned to the index it appeared at.
2. Walk the list once with enumerate, tracking the current index i and value handle_time.
3. At each step, compute complement = target - handle_time — the value that would need to have already appeared earlier in the list to complete a valid pair.
4. If complement is already a key in seen, the pair is found: return (seen[complement], i) immediately.
5. Otherwise, record the current value's index: seen[handle_time] = i, and continue to the next element.
6. If the loop finishes without finding a match, return None — no valid pair exists.

The key insight is that instead of checking every pair of elements (O(n^2)), you only need to ask "have I already seen the value that would complete a pair with the current element?" — a hashmap answers that in O(1), giving a single O(n) pass.

Reference solution

def two_sum(handle_times: list[int], target: int) -> tuple[int, int] | None:
    # single pass with a hashmap of value -> index, O(n) time, O(n) space
    seen: dict[int, int] = {}
    # yields (index, value) pairs
    for i, handle_time in enumerate(handle_times):
        # value needed to complete the pair
        complement = target - handle_time
        # check before insert: avoids self-pairing
        if complement in seen:
            return (seen[complement], i)
        seen[handle_time] = i
    return None

Key Functions & Tricks

• seen: dict[int, int] = {} — hashmap of value to index, O(1) average lookup.
• enumerate(handle_times) — yields (index, value) pairs while iterating.
• complement = target - handle_time — rearranges x + y == target to look up y.
• if complement in seen: — checked before inserting, so an element can't pair with itself.
• return (seen[complement], i) — tuple of the earlier index and current index.

How to Recognize This Pattern