{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Two Sum – Solution & Complexity

Interview solutions
/
Two Sum
Quick practice for Two Sum: 3 reasoning beats, no typing

Watch: Two Sum with a hash map

Walk the array once. For each number, compute the complement it needs (target − num) and check whether that complement is already in the map. If it is, return both indices; if not, store the current number and its index for later. Checking before storing is what stops a number from pairing with itself.

Solution Walkthrough

  1. Step 1: Key Idea: Check Before You Store

    Return the indices of two different positions whose values add up to target.

    • For each nums[i], the partner it needs is complement = target - nums[i].
    • Invariant: while processing index i, the map holds value → index only for earlier positions 0..i-1.
    • Check before insert: look up complement first, and store nums[i] → i only if it is missing. Any hit is therefore an earlier, different index, so an element is never paired with itself.
    • Average O(1) lookups and inserts give one O(n) pass, using O(n) extra space for the map.

    The complete solution is the code next to this step (switch languages with the tabs above). The trace below runs it; the later steps rebuild it line by line from the brute-force baseline.

    def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return None

  2. Step 2: Dry run / state trace

    Trace nums = [3, 2, 4], target = 6. Store only numbers that appear before the current index.

    inumneeded complementmap before checkaction
    033{}3 is not present; store {3: 0}
    124{3: 0}4 is not present; store {3: 0, 2: 1}
    242{3: 0, 2: 1}2 is present at index 1; return [1, 2]

    The invariant prevents using the same element twice because the current 4 is checked before it is inserted.

    Duplicate values: nums = [3, 3], target = 6.

    inumneeded complementmap before checkaction
    033{}3 is not present (index 0 is not stored yet); store {3: 0}
    133{3: 0}3 is present at index 0; return [0, 1]

    Equal values at different indices are a valid pair; reusing one index is not. Storing 3 → 0 before the check at i = 0 would match index 0 with itself and return [0, 0].

  3. Step 3: Brute Force Baseline

    • Check every pair (i, j) with j > i and return the first one that sums to target. Starting j at i + 1 is what keeps an element from pairing with itself.
    • This is O(n²) time and O(1) extra space.
    • The inner loop is just searching for target - nums[i]. A hash map replaces that linear search with an average O(1) lookup, trading O(n) memory for O(n) time.
    def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

  4. Step 4: Create the Map and Compute Each Complement

    • Create an empty hash map from value to index.
    • Loop once over nums; for each num, compute complement = target - num.
    def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num  # Calculate the complement
    return None

  5. Step 5: Check if the Complement Exists in the Hash Map

    • For each number, check if the complement exists in the hash map.
    • If the complement is already in the hash map, it means you’ve found two numbers that add up to the target.
    • Return the indices of the current number and its complement.
    def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:  # Check if complement exists
            return [hash_map[complement], i]  # Return the indices
    return None

  6. Step 6: Store the Current Number in the Hash Map

    • If the complement is not found, store the current number and its index after the check.
    • This keeps the invariant: later numbers can use it as their complement, but it can never match itself.
    def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i  # Store current number
    return None

  7. Step 7: Common mistakes & interviewer follow-ups

    • Returning the two values instead of their indices; the judge expects positions.
    • Inserting the current value before checking its complement, which can reuse the same element when target = 2 * num.
    • Assuming the input is sorted and using two pointers without preserving original indices.
    • Overwriting duplicate values too early in a two-pass map; the one-pass version avoids this by checking first.
    • Follow-ups: how would you return all pairs, handle no guaranteed solution, or reduce memory if the array were sorted?

    Recommended next problem in this pattern: Valid Anagram, which uses a hash map for frequency balance instead of complement lookup.

  8. Step 8: Handle Edge Cases

    • Ensure that the input array has at least two numbers.
    • Return None if no solution is found.
    def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return None  # Return None if no solution is found
Learn the Arrays & Hashing pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Two Sum online (run code in the browser)Valid Anagram solution (easy)Contains Duplicate solution (easy)3Sum solution (medium)Group Anagrams solution (medium)All coding interview problems