The brute-force way to solve this is to check every pair. The key insight that gets us to the optimal solution: for each number, we already know what its partner needs to be (target - num) — so instead of searching for that partner, we can remember every number we’ve already seen and look it up in O(1).
Brute Force
Time O(n²)Space O(1)Try every pair (i, j) with i < j and check if nums[i] + nums[j] == target. It’s guaranteed to find the answer because it exhausts every possible pair — but it does redundant work: after checking index 0 against everything, it starts over from index 1 with no memory of what it already computed.
class Solution: def twoSum(self, nums: list[int], target: int) -> list[int]: n = len(nums) for i in range(n): for j in range(i + 1, n): if nums[i] + nums[j] == target: return [i, j] return []Tracing nums = [3, 2, 4, 7], target = 9:
i=0, j=1 → 3 + 2 = 5, not 9. Advance j.
Why it’s slow: for each of the n starting indices we may scan almost the whole rest of the array, giving n + (n-1) + ... + 1 ≈ n²/2 comparisons — quadratic time, and it throws away every sum it computes.
Hash Map (One Pass)
OptimalTime O(n)Space O(n)Walk the array once. Before inserting the current number, check whether its complement (target - num) was already seen. If it was, we’ve found our pair immediately — no nested loop required. This works because addition is commutative: if nums[i] + nums[j] == target, then whichever of i, j we reach second will find the other already sitting in the map.
class Solution: def twoSum(self, nums: list[int], target: int) -> list[int]: seen = {} # value -> index for i, num in enumerate(nums): complement = target - num if complement in seen: return [seen[complement], i] seen[num] = i return []Take the second example, nums = [3, 2, 4], target = 6. Watch the order of operations each iteration: compute the complement, look it up, and only then store the number.
Array
This step
seen (value → index)
complement = 6 - 3 = 3. Index 0 needs a 3 elsewhere in the array to complete the pair.
Correctness: every number is checked against all numbers before it in a single pass, so any valid pair (i, j) with i < j is caught the moment we reach j, since nums[i] is already stored.
Complexity: one pass over n elements, each doing an O(1) average-case hash map lookup and insert → O(n) time. The map holds up to n entries → O(n) space. This is optimal: you can’t find the answer without at least looking at every element once.