{ }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: Understanding the Problem

    • You are given an array of integers and a target sum.
    • The task is to find two distinct numbers in the array that add up to the target.
    • You should return their indices as a result.

  2. Step 2: Brute Force Approach (Inefficient)

    • Start by considering a brute force approach where you check every possible pair.
    • For each number, iterate through the remaining numbers and check if they add up to the target.
    • This approach has O(n²) time complexity.
    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

  3. Step 3: Identifying the Core Operation

    • The core operation is checking whether two numbers in the array add up to the target.
    • For each number num, check if there’s another number complement such that: num + complement = target
    • The complement can be calculated as complement = target - num.

  4. Step 4: Using a Hash Map for Efficient Lookup

    • Searching through the array takes O(n) time if done linearly. To make this faster, you can use a hash map (dictionary).
    • A hash map allows for constant-time lookups (O(1)), so you can check if the complement exists as you iterate through the array.

  5. Step 5: Initializing the Hash Map

    • Create an empty hash map to store numbers and their indices as you iterate through the array.
    def two_sum(nums, target):
    hash_map = {}  # Initialize an empty dictionary
    return hash_map

  6. Step 6: Iterate Through the Array and Calculate Complement

    • Loop through the array.
    • For each number, calculate its complement (the difference between the target and the current number).
    • The complement is calculated as target - num.
    def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num  # Calculate the complement
    return None

  7. Step 7: 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

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

    • If the complement is not found in the hash map, store the current number and its index in the hash map.
    • This ensures that it can be checked as a complement for future numbers.
    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

  9. Step 9: 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.

  10. Step 10: 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.

  11. Step 11: 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
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?