Two Sum
Problem
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.
- 2 ≤ nums.length ≤ 10⁴
- −10⁹ ≤ nums[i] ≤ 10⁹
- −10⁹ ≤ target ≤ 10⁹
- Only one valid answer exists
Example
nums = [2,7,11,15], target = 9[0, 1]A brute-force approach would check every pair of numbers, resulting in O(n²) time complexity, which is inefficient for large inputs. The optimal approach uses a hash map to store numbers seen so far and their indices, enabling O(1) average-time lookups for complements. Iterating through nums, at index 0 the number 2 is stored in the map. At index 1, the number 7 is checked for its complement 9 - 7 = 2, which exists in the map at index 0. This immediately yields the solution [0, 1]. The key insight is that the hash map acts as a memory of previously seen numbers, transforming the problem from nested searches to constant-time lookups.
Approach
Straightforward Solution
A brute-force solution checks all pairs with nested loops, resulting in O(n²) time complexity, which is too slow for large inputs.
Core Observation
For any two numbers a and b that sum to target, b = target - a. This means for each number, the problem reduces to checking if its complement exists among previously seen numbers.
Path to Optimal
Recognizing the complement relationship allows the use of a hash map to store numbers as keys and their indices as values. This enables constant-time lookups for complements during a single pass through the array, reducing time complexity to O(n).
Optimal Approach
Iterate through nums once, for each number compute its complement (target - current number), check if complement exists in the hash map. If yes, return the pair of indices. Otherwise, add the current number and its index to the map. This guarantees a single-pass O(n) time solution with O(n) space.
Time
O(n)
Each element is processed once, and hash map lookups and insertions are O(1) on average, resulting in linear time.
Space
O(n)
In the worst case, all elements are stored in the hash map before finding the solution, requiring linear auxiliary space.
Pattern Spotlight
Hash Maps (Complement Lookup)
Transform pair-sum problems by storing seen elements in a hash map to enable O(1) complement checks, converting nested searches into a single linear pass.
Solution
| 1 | class Solution:
|
| 2 | def twoSum(self, nums: List[int], target: int) -> List[int]:
|
| 3 | prev_map = {}
|
| 4 | for i, n in enumerate(nums):
|
| 5 | complement = target - n
|
| 6 | if complement in prev_map:
|
| 7 | return [prev_map[complement], i]
|
| 8 | prev_map[n] = i |
Step-by-Step Solution
Build Hash Map of Previously Seen Numbers
| 3 | prev_map = {}
|
Objective
To create a hash map that stores each number and its index as the array is traversed.
Key Insight
Storing numbers as keys with their indices as values allows constant-time lookup for complements. This data structure is the foundation that transforms the problem from quadratic to linear time.
Interview Quick-Check
Core Logic
The hash map stores numbers as keys and their indices as values, enabling O(1) average-time complement lookups.
Common Pitfalls & Bugs
Populating the hash map before checking for complements requires two passes and is less efficient than the single-pass approach.
Iterate Through Array and Find Complement Matches
| 4 | for i, n in enumerate(nums):
|
| 5 | complement = target - n
|
| 6 | if complement in prev_map:
|
| 7 | return [prev_map[complement], i]
|
| 8 | prev_map[n] = i |
Objective
To scan the array once, checking if the complement of the current number exists in the hash map and returning the indices if found.
Key Insight
Checking for the complement before adding the current number prevents self-matching and ensures the earliest valid pair is returned immediately, achieving optimal time complexity.
Interview Quick-Check
Core Logic
Check if the complement exists in the hash map before adding the current number to avoid matching the number with itself.
State & Boundaries
Return immediately upon finding a valid pair to avoid unnecessary iterations.
Common Pitfalls & Bugs
Adding the current number before checking for its complement can cause incorrect self-matches.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if complement in prev_map:Check if the complement exists in the hash map.
This condition identifies the moment when a valid pair is found, enabling immediate return of the solution.
prev_map[n] = iAdd the current number and its index to the hash map.
Adding after the complement check prevents the current number from matching with itself, preserving the problem constraint of distinct elements.
prev_map = {}Initialize an empty hash map to store numbers and their indices.
This data structure enables constant-time lookups for complements, which is essential for reducing the problem from O(n²) to O(n) time complexity.
return [prev_map[complement], i]Return the indices of the complement and current number.
Returning immediately upon finding the pair ensures the algorithm stops at the first valid solution, maintaining correctness and efficiency.
complement = target - nCalculate the complement needed to reach the target.
This defines the value to search for in the hash map to find a valid pair.
for i, n in enumerate(nums):Iterate through the array with index and value.
Enumerating both index and value is necessary to track positions for the final answer and to check complements efficiently.
Test Your Understanding
Why must the algorithm check for the complement before adding the current number to the hash map?
To avoid matching a number with itself, which would violate the problem constraint of using distinct elements. Checking first ensures the complement is from a previously seen different element.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Two Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Start drilling Two Sum for free