Two Sum

Given an array of integers and a target, return indices of two numbers that add up to the target.

Language Selection

Choose your preferred programming language

Showing: Python

Two Sum

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Examples

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 6, we return [0, 1].

Constraints

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Approach 1: Brute Force

Algorithm

Check every pair of numbers to see if they add up to the target.

Steps:

  1. Use two nested loops to iterate over all pairs
  2. For each pair (i, j) where i < j, check if nums[i] + nums[j] == target
  3. If a match is found, return [i, j]

Implementation

Python:

def twoSum(nums, target):
    """
    Find two numbers that add up to target using brute force
    Time: O(n^2)
    Space: O(1)
    """
    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 []  # No solution found

Java:

class Solution {
    /**
     * Find two numbers that add up to target using brute force
     * Time: O(n^2)
     * Space: O(1)
     */
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{}; // No solution found
    }
}

Go:

// twoSum - Find two numbers that add up to target using brute force
// Time: O(n^2)
// Space: O(1)
func twoSum(nums []int, target int) []int {
    n := len(nums)

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }

    return []int{} // No solution found
}

JavaScript:

/**
 * Find two numbers that add up to target using brute force
 * Time: O(n^2)
 * Space: O(1)
 */
function twoSum(nums, target) {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }

    return []; // No solution found
}

C#:

public class Solution {
    /// <summary>
    /// Find two numbers that add up to target using brute force
    /// Time: O(n^2)
    /// Space: O(1)
    /// </summary>
    public int[] TwoSum(int[] nums, int target) {
        int n = nums.Length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }

        return new int[] {}; // No solution found
    }
}

Complexity Analysis

  • Time Complexity: O(n^2) - Two nested loops over the array
  • Space Complexity: O(1) - No extra data structures used

Approach 2: Hash Map (Optimal)

Algorithm

Use a hash map to store numbers and their indices for O(1) lookup of the complement.

Steps:

  1. Create a hash map to store number -> index mapping
  2. For each number in the array:
    • Calculate complement = target - current number
    • If complement exists in hash map, return indices
    • Otherwise, store current number and its index in hash map

Implementation

Python:

def twoSum(nums, target):
    """
    Find two numbers that add up to target using hash map
    Time: O(n)
    Space: O(n)
    """
    num_map = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in num_map:
            return [num_map[complement], i]

        num_map[num] = i

    return []  # No solution found

Java:

import java.util.*;

class Solution {
    /**
     * Find two numbers that add up to target using hash map
     * Time: O(n)
     * Space: O(n)
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }

            numMap.put(nums[i], i);
        }

        return new int[]{}; // No solution found
    }
}

Go:

// twoSum - Find two numbers that add up to target using hash map
// Time: O(n)
// Space: O(n)
func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)

    for i, num := range nums {
        complement := target - num

        if idx, exists := numMap[complement]; exists {
            return []int{idx, i}
        }

        numMap[num] = i
    }

    return []int{} // No solution found
}

JavaScript:

/**
 * Find two numbers that add up to target using hash map
 * Time: O(n)
 * Space: O(n)
 */
function twoSum(nums, target) {
    const numMap = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }

        numMap.set(nums[i], i);
    }

    return []; // No solution found
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find two numbers that add up to target using hash map
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int[] TwoSum(int[] nums, int target) {
        var numMap = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];

            if (numMap.ContainsKey(complement)) {
                return new int[] { numMap[complement], i };
            }

            numMap[nums[i]] = i;
        }

        return new int[] {}; // No solution found
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Single pass through the array
  • Space Complexity: O(n) - Hash map stores at most n elements

Key Insights

  1. Complement Strategy: Instead of searching for two numbers, compute complement = target - num and look it up in the hash map for O(1) access
  2. Single Pass: We can check and insert in the same loop, which means we never compare an element with itself
  3. Hash Map Trade-off: We trade O(n) space for O(n) time, improving from the O(n^2) brute force
  4. Uniqueness Guarantee: The problem guarantees exactly one solution, so we do not need to handle duplicates or multiple answers
  5. Index Preservation: Storing indices in the hash map lets us return positions rather than values

Edge Cases

  1. Duplicate Values: nums = [3, 3], target = 6 – two identical values that sum to target
  2. Negative Numbers: nums = [-1, -2, -3, -4], target = -6 – negative values require correct complement computation
  3. Zero in Array: nums = [0, 4, 3, 0], target = 0 – zeroes paired together
  4. Large Values: nums with values near 10^9 – ensure no integer overflow in complement calculation
  5. Two Elements: Minimum array size of 2, where the answer must be [0, 1]

Test Cases

def test_twoSum():
    # Test case 1: Normal case
    assert twoSum([2, 7, 11, 15], 9) == [0, 1]

    # Test case 2: Answer not at the start
    assert twoSum([3, 2, 4], 6) == [1, 2]

    # Test case 3: Duplicate values
    assert twoSum([3, 3], 6) == [0, 1]

    # Test case 4: Negative numbers
    assert twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]

    # Test case 5: Zero target with zeroes
    assert twoSum([0, 4, 3, 0], 0) == [0, 3]

    # Test case 6: Negative and positive
    assert twoSum([-3, 4, 3, 90], 0) == [0, 2]

    # Test case 7: Large array single pair
    assert twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 19) == [8, 9]

    print("All tests passed!")

test_twoSum()

Follow-up Questions

  1. Two Sum II - Sorted Array: What if the input array is sorted? Use two pointers for O(1) space.
  2. Two Sum III - Data Structure: Design a class that supports add and find operations.
  3. Two Sum IV - BST: Find two elements in a BST that sum to a target.
  4. Three Sum: Extend to finding three numbers that sum to zero.
  5. Two Sum - Multiple Pairs: What if there are multiple valid pairs?

Common Mistakes

  1. Using Same Element Twice: Returning [i, i] when nums[i] * 2 == target but there is only one occurrence
  2. Inserting Before Checking: Adding the current number to the map before checking the complement can cause self-pairing
  3. Wrong Index Order: Returning indices in incorrect order when the problem expects a specific ordering
  4. Forgetting Negative Numbers: Not considering that complements can be negative
  5. Overwriting Duplicate Keys: Storing a duplicate value in the map before checking if the previous index forms a valid pair

Interview Tips

  1. Start with Brute Force: Demonstrate understanding by describing the O(n^2) approach first
  2. Explain the Optimization: Walk through how the hash map eliminates the inner loop
  3. Trace Through an Example: Pick nums = [2, 7, 11, 15], target = 9 and show the hash map state at each step
  4. Discuss Trade-offs: O(n) time vs O(n) space, and why this trade-off is worthwhile
  5. Mention Edge Cases: Bring up duplicates, negatives, and zeroes before the interviewer asks

Concept Explanations

Complement Lookup: The core idea is that for each number x, we need target - x to exist somewhere else in the array. A hash map makes this lookup O(1) instead of O(n).

One-Pass vs Two-Pass: A two-pass approach builds the entire map first, then scans again. The one-pass approach is simpler and equally efficient because by the time we reach the second element of a valid pair, the first element is already in the map.

Why Hash Map Works: Hash maps provide average O(1) insertion and lookup. This converts the nested-loop search into a single-loop search with constant-time complement checks.

Space-Time Trade-off: The brute force uses O(1) space but O(n^2) time. The hash map uses O(n) space but O(n) time. In most interview and production scenarios, the faster solution is preferred.