Arrays & Hashing · LC #1
Two Sum
Classic hash-map problem: find two indices whose values sum to a target. Teaches the one-pass complement-lookup pattern that eliminates O(n²) brute force.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array of integers `nums` and an integer `target`, return the **indices** of the two numbers that add up to `target`. You may assume exactly one solution exists and you may not use the same element twice.
Sample I/O
Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0] + nums[1] = 2 + 7 = 9 Input: nums = [3, 2, 4], target = 6 Output: [1, 2]
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
Instead of checking every pair (O(n²)), we can ask: "have I already seen the number I need?" For each element x, if target − x is already in the map, we immediately have our answer. This transforms a double loop into a single pass.
Core Concept
Maintain a hash map of {value → index} as you scan left to right. For each nums[i] compute complement = target − nums[i]. If complement exists in the map, return [map[complement], i]. Otherwise insert nums[i] → i and continue. Because each number is visited once, total time is O(n) with O(n) space for the map.
When to use
Any time you need to find a pair (or triplet) summing to a fixed value and the array is unsorted - or sorted but you need indices rather than values. Also when constraints forbid sorting.
When NOT to use
If you only need existence (not indices) and the array is sorted, two pointers uses O(1) space. If k > 2 addends are required, a different multi-pointer or DP approach is better.
Key Insights
What to Know Cold
- Store seen[value] = index so you can retrieve the index of the complement in O(1).
- Insert AFTER the lookup check to avoid using the same element twice.
- The problem guarantees exactly one solution - no need to handle the no-answer case.
- Works for negative numbers and zeros because hash maps handle arbitrary keys.
- This exact pattern extends to 3Sum / 4Sum by fixing outer elements and running Two Sum on the remainder.
1 example
Worked Examples
One-Pass Hash Map
Array [2, 7, 11, 15], target 9. Need indices of elements summing to 9.
Iterate once. At index 0, complement = 9−2 = 7; map is empty, store {2:0}. At index 1, complement = 9−7 = 2; 2 is in the map at index 0 → return [0, 1].
seen = {}
for i, num in enumerate([2, 7, 11, 15]):
comp = 9 - num
if comp in seen:
print([seen[comp], i]) # [0, 1]
break
seen[num] = iDemonstrates trading O(n) space for O(n) time - the foundational hash-map trade-off asked in virtually every company's early coding screen.