Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
A complete visual walkthrough from brute force to the optimal hash map approach — the classic interview warm-up.
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.
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]
Example 3:
Input: nums = [3,3], target = 6 Output: [0,1]
Constraints:
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109O(n2) time complexity?The simplest solution: try every possible pair of elements and check if they sum to the target. Given nums = [2, 7, 11, 15] and target = 9:
We check n(n-1)/2 pairs. For 4 elements that's 6 comparisons. For 10,000 elements? Nearly 50 million.
// Brute force: O(n^2) time, O(1) space for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) return new int[] { i, j }; } }
// Brute force: O(n^2) time, O(1) space for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { if nums[i]+nums[j] == target { return []int{i, j} } } } return nil
# Brute force: O(n^2) time, O(1) space for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j]
// Brute force: O(n^2) time, O(1) space for i in 0..nums.len() { for j in (i + 1)..nums.len() { if nums[i] + nums[j] == target { return vec![i as i32, j as i32]; } } } vec![]
// Brute force: O(n^2) time, O(1) space for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) return [i, j]; } }
This works, but the nested loops give us O(n2) time. Can we do better?
Instead of asking "which two numbers add up to target?" — rephrase: for each number, ask "have I already seen the number that completes this pair?"
For every element nums[i], its complement is target - nums[i]. If the complement already exists in our hash map, we found the pair.
One-pass strategy: As we iterate, we store each number and its index in a hash map. Before storing, we check if the complement is already there. This means we only need a single pass through the array — O(n) time instead of O(n2).
Let's trace through nums = [2, 7, 11, 15] with target = 9, building the hash map one element at a time.
Complement = 9 - 2 = 7. Is 7 in the map? No. Store {2 : 0}.
| Key (value) | Value (index) |
|---|---|
| 2 | 0 |
Complement = 9 - 7 = 2. Is 2 in the map? Yes, at index 0!
Notice we found the answer on the second iteration. The brute force would have found it on the first pair too, but imagine the answer was at indices [0, 9999] in a 10,000-element array. The hash map approach still finds it in at most n lookups, while brute force might need nearly n2/2.
The hash map approach handles all these naturally, but it's good to verify your understanding.
Why "store after checking" matters: We store nums[i] in the map after checking for the complement. This ensures we never match an element with itself. For [3, 3] with target 6, index 0's "3" is stored, then index 1's complement lookup finds index 0 — two different indices.
class Solution { public int[] twoSum(int[] nums, int target) { // Map from value -> index for O(1) complement lookup Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { // What number do we need to reach the target? int complement = target - nums[i]; // Have we already seen that number? if (map.containsKey(complement)) { // Found it! Return both indices return new int[] { map.get(complement), i }; } // Store current value and its index for future lookups map.put(nums[i], i); } // Problem guarantees exactly one solution exists throw new IllegalArgumentException("No two sum solution"); } }
func twoSum(nums []int, target int) []int { // Map from value -> index for O(1) complement lookup seen := make(map[int]int) for i, num := range nums { // What number do we need to reach the target? complement := target - num // Have we already seen that number? if j, ok := seen[complement]; ok { // Found it! Return both indices return []int{j, i} } // Store current value and its index for future lookups seen[num] = i } // Problem guarantees exactly one solution exists return nil }
def two_sum(nums: list[int], target: int) -> list[int]: # Map from value -> index for O(1) complement lookup seen: dict[int, int] = {} for i, num in enumerate(nums): # What number do we need to reach the target? complement = target - num # Have we already seen that number? if complement in seen: # Found it! Return both indices return [seen[complement], i] # Store current value and its index for future lookups seen[num] = i # Problem guarantees exactly one solution exists raise ValueError("No two sum solution")
use std::collections::HashMap; impl Solution { pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> { // Map from value -> index for O(1) complement lookup let mut seen: HashMap<i32, i32> = HashMap::new(); for (i, &num) in nums.iter().enumerate() { // What number do we need to reach the target? let complement = target - num; // Have we already seen that number? if let Some(&j) = seen.get(&complement) { // Found it! Return both indices return vec![j, i as i32]; } // Store current value and its index for future lookups seen.insert(num, i as i32); } // Problem guarantees exactly one solution exists vec![] } }
function twoSum(nums: number[], target: number): number[] { // Map from value -> index for O(1) complement lookup const map = new Map<number, number>(); for (let i = 0; i < nums.length; i++) { // What number do we need to reach the target? const complement = target - nums[i]; // Have we already seen that number? if (map.has(complement)) { // Found it! Return both indices return [map.get(complement)!, i]; } // Store current value and its index for future lookups map.set(nums[i], i); } // Problem guarantees exactly one solution exists throw new Error("No two sum solution"); }
Enter your own array and target, then step through the hash map algorithm one iteration at a time.
We iterate through the array once. Each hash map lookup (containsKey) and insertion (put) is O(1) amortized, so the total time is O(n). In the worst case, we store all n elements in the map before finding the answer, giving O(n) space.
Two nested loops check every pair. The outer loop picks one element, the inner scans the rest -- n*(n-1)/2 comparisons total, which is O(n2). Only two index variables are allocated.
Sorting dominates at O(n log n). After sorting, two pointers converge from both ends in O(n). A copy of the original array is needed to recover the original indices, costing O(n) space.
Single pass through the array with O(1) amortized hash lookups. Each of n elements does one lookup and one insert. In the worst case all n elements are stored in the map before finding the pair.
The classic time-space tradeoff: We spend O(n) extra memory on the hash map to eliminate the inner loop entirely. This is one of the most fundamental patterns in algorithm design — trading space for time.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.