How to Think About a Problem

What we're doing: Turn "find two prices that add up to a budget" into a precise, checkable contract.

def two_sum_indices_precise(prices: list[int], target: int) -> tuple[int, int] | None:
    """Return the (i, j) indices, i < j, of the first pair of prices summing to target; None if no pair exists."""


print(two_sum_indices_precise.__doc__)

1

The type hints alone answer two questions the vague prompt left open: prices is a list of numbers, and the answer is a pair of indices, not a pair of prices.

2

The docstring answers the remaining two: which pair, if several match (the first found, by index order), and what "no pair" means (None, not an exception).

Return the (i, j) indices, i < j, of the first pair of prices summing to target; None if no pair exists.

Why this works: Every word in the docstring closes a gap the original prompt left open. Writing the contract down, before any implementation exists, means the first time you discover 'what if there are two valid pairs?' is now — a five-second decision — instead of mid-debugging, when it looks like a bug in code that is actually behaving exactly as (accidentally) written.

What we're doing: Map three different stated input sizes to the complexity class each one permits.

def choose_approach(n: int) -> str:
    if n <= 20:
        return "any correct approach is fine, even O(2^n)"
    if n <= 10_000:
        return "O(n^2) is safe"
    return "need O(n log n) or better"


print(choose_approach(15))
print(choose_approach(5_000))
print(choose_approach(200_000))

9

n = 200,000 rules out O(n^2) — 200,000^2 is 4 * 10^10 operations, far past what runs in a few seconds — so the constraint alone tells you a hash map, two pointers, or sorting-based approach is expected before you write anything.

any correct approach is fine, even O(2^n)
O(n^2) is safe
need O(n log n) or better

Why this works: The same problem statement can have three very different intended solutions depending only on the stated n — reading the constraint first tells you which one to look for, instead of designing an approach and discovering it times out.

What we're doing: Hand-trace a brute-force search for two prices summing to a target, printing every pair checked.

def two_sum_brute_force_traced(prices, target):
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            print(f"   check prices[{i}]={prices[i]} + prices[{j}]={prices[j]} -> {prices[i] + prices[j]}")
            if prices[i] + prices[j] == target:
                return (i, j)
    return None


small = [7, 2, 9, 3]
result = two_sum_brute_force_traced(small, 10)
print("result:", result)

4

Printing every pair checked is the hand-trace made literal in code — this is exactly the table you would draw on paper before writing any of this function.

5

The trace stops the moment a pair sums to target — walking through it by hand first is what tells you the loop needs an early return, rather than checking every remaining pair for no reason.

   check prices[0]=7 + prices[1]=2 -> 9
   check prices[0]=7 + prices[2]=9 -> 16
   check prices[0]=7 + prices[3]=3 -> 10
result: (0, 3)

Why this works: Four elements is small enough to check by hand in seconds — (7,2)=9, (7,9)=16, (7,3)=10 — matches, stop. Walking through it this way, before writing the function, is what tells you the algorithm needs two nested positions and an early exit; the code above is just that same trace, typed out.

What we're doing: Write the brute-force two-sum-indices solution, note its cost, and see why a faster rewrite needs it as a reference.

def two_sum_brute_force(prices, target):
    comparisons = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            comparisons += 1
            if prices[i] + prices[j] == target:
                return (i, j), comparisons
    return None, comparisons


print(two_sum_brute_force([7, 2, 9, 3, 1], 10))

1

Checking every pair is the brute force — O(n^2) comparisons in the worst case, but it is obviously correct: it never skips a pair that could match.

10

Every faster rewrite of this function (a hash-map one-pass, §5) can now be checked against this exact call and expected to return the same pair.

((0, 3), 3)

Why this works: Three comparisons were needed to find that prices[0]=7 and prices[3]=3 sum to 10 — checking every pair in order guarantees the first valid pair by index is found, which becomes the exact behavior a faster rewrite must match to be considered correct, not just fast.

What we're doing: Run a brute-force pair search against an empty list and a single-element list, without changing the function.

def two_sum_brute_force(prices, target):
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            if prices[i] + prices[j] == target:
                return (i, j)
    return None


print(two_sum_brute_force([], 10))
print(two_sum_brute_force([5], 10))

10

range(1) never reaches a j (there is no second element to pair with), so the inner loop body never runs for a single-element list — the same code path as an empty list, verified rather than assumed.

None
None

Why this works: Both edge cases fall through to the same `return None` without a crash, but that is worth confirming, not assuming — a version indexing prices[0] before checking length would raise on the empty case instead.

What we're doing: Trace a two-sum-indices solution that looks reasonable, and catch a self-pairing bug a single run would miss if the test case were different.

def two_sum_buggy(nums, target):
    for i in range(len(nums)):
        for j in range(len(nums)):
            if nums[i] + nums[j] == target:
                return (i, j)
    return None


print(two_sum_buggy([4, 5, 6], 8))

3

Tracing i=0, j=0 first: nums[0] + nums[0] == 4 + 4 == 8 == target — the function returns (0, 0) on its very first comparison, before ever comparing two DIFFERENT indices.

(0, 0)

Why this works: A single run just sees "it returned something" and might not notice the (0, 0) is suspicious. Tracing forces you to state, out loud, what i and j hold at each step — and stating "we are pairing index 0 with itself" immediately reads as wrong for a two-DIFFERENT-prices problem.