Coding Interview PatternsTwo Sum
EasyHash Maps
Two Sum
Explanation & Solution
Description
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.
Input:nums = [2,7,11,15], target = 9
0
2
1
7
2
11
3
15
Output:[0,1]
0
0
1
1
Explanation: Because nums[0] + nums[1] == 9, 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
Hash Maps pattern
1. Create a Hash Map
- Initialize an empty
Mapto store each number and its index as we iterate through the array - The map allows O(1) lookups for the complement of each number
2. Iterate Through the Array
- For each element
nums[i], compute the complement:target - nums[i] - Check if the complement already exists in the map
3. Check for a Match
- If the complement is in the map, we found our pair — return
[map.get(complement), i] - If the complement is not in the map, store
nums[i] → iin the map and continue
4. Return the Result
- Since the problem guarantees exactly one solution, the function will always return inside the loop
- The indices are returned in ascending order because we always store earlier indices first
Key Insight
- A brute-force approach checks every pair in O(n²). By using a hash map, we reduce this to a single pass through the array
- For each element, we ask: "Have I already seen the number that would complete the sum?" — this is a classic complement lookup pattern
Time
O(n)one pass through the array with O(1) map operationsSpace
O(n)the map stores at most n entriesVisualization
Input:
[2, 7, 11, 15], target = 9
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps