Two Sum

Find two distinct indices in an integer array whose values sum to a given target.

Problem Statement

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

You may assume that each input has exactly one valid solution, and you may not use the same element twice. You can return the answer in any order.

Constraints

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

Core Intuition

The naive approach checks every possible pair using two nested loops. For each index i, an inner loop scans all subsequent indices j to test if nums[i] + nums[j] == target. Because testing every pair of an array of size $n$ requires approximately $n^2 / 2$ checks, this brute-force method runs in $O(n^2)$ time.

Instead of scanning the array repeatedly to find the matching number, rewrite the equation:

$$\text{complement} = \text{target} - \text{nums}[i]$$

For any number $\text{nums}[i]$, there is only one exact value that pairs with it to reach target. By storing each number we visit in a hash map as a key, paired with its index as the value, we can verify whether the needed complement was already seen in $O(1)$ average time.

A single pass through the array suffices. At each element, compute its complement. If the complement is already in the hash map, return the complement's index along with the current index. If not, record the current element and its index in the map, then move forward.

Step-by-Step Walkthrough

Consider nums = [3, 2, 4, 8] with target = 6.

Initial State

• Array: [3, 2, 4, 8]
• Hash Map: {}

---

Step 1: Index 0

• Current element: nums[0] = 3
• Needed complement: 6 - 3 = 3
• Check map: Is 3 in {}? No.
• Store nums[0] in map: { 3: 0 }

Indices:     0    1    2    3
Nums:      [ 3,   2,   4,   8 ]
             ↑
             i = 0 (val = 3, complement = 3)
Map:       { 3: 0 }

---

Step 2: Index 1

• Current element: nums[1] = 2
• Needed complement: 6 - 2 = 4
• Check map: Is 4 in { 3: 0 }? No.
• Store nums[1] in map: { 3: 0, 2: 1 }

Indices:     0    1    2    3
Nums:      [ 3,   2,   4,   8 ]
                  ↑
                  i = 1 (val = 2, complement = 4)
Map:       { 3: 0, 2: 1 }

---

Step 3: Index 2

• Current element: nums[2] = 4
• Needed complement: 6 - 4 = 2
• Check map: Is 2 in { 3: 0, 2: 1 }? Yes!
• Complement 2 was stored at index 1.
• Return [1, 2].

Indices:     0    1    2    3
Nums:      [ 3,   2,   4,   8 ]
                       ↑
                       i = 2 (val = 4, complement = 2)
Map:       { 3: 0, 2: 1 } -> Found key 2 at index 1!
Result:    [1, 2]

Algorithm Steps

1. Initialize an empty hash map seen to store array values as keys and their corresponding indices as values.
2. Iterate through nums using an index i from 0 to n - 1.
3. For each element nums[i], calculate complement = target - nums[i].
4. If complement exists in seen, return [seen[complement], i].
5. If complement does not exist in seen, insert seen[nums[i]] = i.
6. Continue to the next element. The problem guarantees exactly one solution exists.

Complexity Analysis

• Time Complexity: $O(n)$ — The array is traversed once. Each lookup and insertion into the hash map takes $O(1)$ time on average.
• Space Complexity: $O(n)$ — In the worst case, the matching pair is at the very end of the array, requiring the hash map to store up to $n - 1$ entries.

123456789101112class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        # Maps value -> index
        seen = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        
        return []

Python 3

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        # Maps value -> index
        seen = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        
        return []

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  // Map value -> index
  const seen = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);
  }

  return [];
}

TypeScript

function twoSum(nums: number[], target: number): number[] {
  // Map value -> index
  const seen = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    const complementIndex = seen.get(complement);
    
    if (complementIndex !== undefined) {
      return [complementIndex, i];
    }
    seen.set(nums[i], i);
  }

  return [];
}

Java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Map value -> index
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[] { seen.get(complement), i };
            }
            seen.put(nums[i], i);
        }

        return new int[0];
    }
}

C++

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        // Map value -> index
        std::unordered_map<int, int> seen;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            int complement = target - nums[i];
            auto it = seen.find(complement);
            if (it != seen.end()) {
                return { it->second, i };
            }
            seen[nums[i]] = i;
        }

        return {};
    }
};

Common Pitfalls & Edge Cases

1. Using the Same Element Twice: If nums = [3, 2, 4] and target = 6, looking for complement 6 - 3 = 3 must not match nums[0] with itself. The one-pass hash map avoids this because the current element is added to the map after checking for its complement.
2. Duplicate Values in the Input: If nums = [3, 3] and target = 6, pre-populating the entire hash map in advance can overwrite the first index with the second index. The one-pass approach processes the first 3, stores index 0, and on encountering the second 3, successfully matches with index 0.
3. Negative Numbers and Zeroes: Complements work identical mathematically with negative integers (e.g., target = -8, nums[i] = -2, complement = -8 - (-2) = -6). Standard hash map lookups handle negative keys without special modifications.