Two Sum (LeetCode 1)

The problem

You get an array of integers nums and an integer target. Return the indices of the two different elements that add up to target. There is exactly one answer, and you can’t use the same element twice.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

nums[0] + nums[1] = 2 + 7 = 9.

How to think about it

Start with brute force. Try every pair (i, j) with i < j and check whether nums[i] + nums[j] == target. That is O(n²) time. With 10⁴ elements it’s about 50 million checks, which is too slow and is not what the interviewer is looking for.

Rephrase the question. For each number x, you’re really asking one thing: “have I already seen target − x?” That number is its complement. If you can answer that question in O(1), the whole scan is O(n).

The key insight: a hash map turns “have I seen it?” into an O(1) lookup. Walk the array once. For each x at index i, look up target − x in a dictionary of values you’ve already passed. If it’s there, you’re done: return its stored index and i. If not, store x -> i and move on. Checking before storing guarantees you never pair an element with itself.

Sorting is not better here. Sorting plus two pointers is O(n log n) and loses the original indices, so you’d have to carry them along. The hash map is simpler and faster.

Which pattern is this? Hash map lookup. The tell is “find a pair with some relationship, faster than O(n²)“.

Approach

1. Create an empty dictionary seen mapping value to index.
2. For each index i and value x:
   • if target − x is in seen, return [seen[target − x], i];
   • otherwise store seen[x] = i.
3. If the loop finishes, return [] (no pair exists; the problem guarantees this won’t happen).

Solution

def two_sum(nums, target):
    seen = {}                                        # value -> index
    for i, x in enumerate(nums):
        if target - x in seen: return [seen[target-x], i]   # complement seen earlier
        seen[x] = i                                  # store after checking
    return []
# two_sum([2,7,11,15], 9) -> [0,1]

Dry run

On nums = [2, 7, 11, 15], target = 9:

On [3, 2, 4] with target = 6, index 0 stores 3, index 1 stores 2, and index 2 finds 2 and returns [1, 2]. Note it does not return [0, 0], because 3 is checked before it is stored.

Complexity

• Time: O(n). One pass; each dictionary lookup and insert is O(1) on average.
• Space: O(n). In the worst case every value is stored before the pair is found.

Edge cases and pitfalls

• Duplicate values: [3, 3] with target 6 returns [0, 1]. The first 3 is stored, and the second finds it. Storing first and checking second would break this.
• Using an element twice: storing x before checking can match x with itself when x = target / 2.
• Negative numbers and zero work unchanged; the complement can be any integer.
• No answer: the function returns []. The problem guarantees an answer, but say how you’d handle it.
• Returning values instead of indices is a common slip. Read what is asked.

Related problems

• Two Sum II (LeetCode 167): the array is sorted, so two pointers solve it in O(1) space.
• 3Sum (LeetCode 15): fix one number, then solve a two-sum on the rest.
• Subarray Sum Equals K (LeetCode 560): the same “look up the complement” idea, applied to prefix sums.