Two Sum — 5 Solutions from Brute Force to O(n) HashMap [MAANG Favorite]

Problem Statement

Given an array of integers nums and a target integer target, return indices of the two numbers such that they add up to target. You may assume exactly one solution exists.

Example:

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

Intuition
Approach 1 — Brute Force O(n²)
Approach 2 — HashMap O(n) ✅ Optimal
Solutions in All 5 Languages
C
C++
Java
JavaScript
Python
Complexity Analysis
Edge Cases
Follow-up Questions (asked at FAANG)
Key Takeaway

Intuition

The brute force is obvious: check every pair. But we want O(n).

Key insight: For each element x, we need to find target - x. If we store previously seen elements in a HashMap, we can look up the complement in O(1).

Mental model: Walk through the array. At each step ask: "Have I seen the number that, added to the current number, gives the target?"

Approach 1 — Brute Force O(n²)

Check every pair (i, j) where i < j.

For i = 0 to n-1:
  For j = i+1 to n-1:
    if nums[i] + nums[j] == target: return [i, j]

❌ Too slow for large inputs (10⁴ elements → 10⁸ operations).

Approach 2 — HashMap O(n) ✅ Optimal

Walk the array once. For each element nums[i]:

Compute complement = target - nums[i]
Check if complement is already in the map
If yes → found the pair. Return stored index + current index
If no → store nums[i] → i in the map

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

Solutions in All 5 Languages

C

#include <stdlib.h>
#include <string.h>

// Simple hash: use direct addressing for small value ranges
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    // Use a hash map: key = num+10000, value = index+1 (0 means not found)
    int* map = (int*)calloc(20001, sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int key = complement + 10000;
        
        if (key >= 0 && key <= 20000 && map[key] != 0) {
            result[0] = map[key] - 1;
            result[1] = i;
            free(map);
            return result;
        }
        map[nums[i] + 10000] = i + 1;
    }
    
    free(map);
    return result;
}

C++

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;  // value → index
        
        for (int i = 0; i < (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 {}; // guaranteed to have a solution
    }
};

Java

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        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[]{}; // never reached
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
    const seen = new Map(); // value → index
    
    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);
    }
}

Python

from typing import List

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

Complexity Analysis

Approach	Time	Space
Brute Force	O(n²)	O(1)
HashMap	O(n)	O(n)

Why O(n)? We traverse the array once. HashMap lookup and insert are O(1) amortized.

Why O(n) space? In the worst case (no pair found until last element), we store n-1 elements in the map.

Edge Cases

# 1. Same index used twice — NOT allowed
# nums = [3, 3], target = 6 → [0, 1] ✓ (two different indices)

# 2. Negative numbers
# nums = [-1, -2, -3, -4, -5], target = -8 → [2, 4]

# 3. Large values
# nums = [1000000000, -1000000000], target = 0 → [0, 1]

Follow-up Questions (asked at FAANG)

Q: What if there can be multiple pairs? Return all pairs. Use a set of sorted tuples to deduplicate.

Q: What if the array is sorted? Use two pointers — O(n) time, O(1) space (no HashMap needed).

Q: What if nums is a stream (infinite)? Store all seen elements in a set. For each new element check if target - x is in the set.

Key Takeaway

The HashMap pattern — "store what you've seen, look up what you need" — is the foundation for:

3Sum (extend to three elements)
4Sum
Subarray Sum Equals K (prefix sum + map)
Group Anagrams
Longest Consecutive Sequence

Next: Problem 2 — Best Time to Buy & Sell Stock →