Repository navigation
033 — Two Sum
LeetCode 1 · Easy. Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.
You're at a vending machine that takes exact change, and you have a pocket full of coins. You need two coins that add up to exactly 75 cents. The slow way: pull out every pair of coins, one by one, add them up, check. The fast way: as you pull coins out of your pocket one at a time, ask a single question for each — "do I already have a coin worth 75 - this coin's value in my other hand?" If you're holding a 25-cent coin and you just pulled out a 50-cent coin, you instantly know they pair up — because you remember what's already in your hand instead of re-checking your whole pocket every time.
"Find two numbers that sum/add up to a target" on an unsorted array, where you need to return indices (not just whether a pair exists), is the canonical hash-map complement-lookup signal. The moment you see "find a pair matching some target value," ask: "for the current element, what value would I need to have already seen?" That value is the complement (target - current), and checking "have I seen the complement?" is exactly what a hash map answers in O(1). (Note: if the array were already sorted and you didn't need original indices, Two Pointers — see Two Pointers — would also be a strong fit; the unsorted-with-indices requirement here is what tips it toward hashing instead.)
Check every pair of indices and see if their values sum to the target.
func twoSumBruteForce(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
if nums[i] + nums[j] == target {
return [i, j]
}
}
}
return [] // problem guarantees a solution exists, so this shouldn't happen
}Big-O: O(n²) time — a nested loop over every pair. O(1) extra space.
Walk the array once. For each number, compute its complement (target - num) and check whether that complement is already in a hash map of values-we've-seen-mapped-to-their-index. If it is, we've found our pair. Otherwise, record the current number's index and keep going.
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var seenIndices = [Int: Int]() // value -> index
for (i, num) in nums.enumerated() {
let complement = target - num
if let complementIndex = seenIndices[complement] {
return [complementIndex, i]
}
seenIndices[num] = i
}
return [] // problem guarantees a solution exists
}Big-O: O(n) time — a single pass, O(1) average per hash-map lookup/insert. O(n) space for the hash map in the worst case.
The brute force answers "does some earlier or later element complete this pair?" by re-scanning the whole array for every element. But by the time we reach index i, we've already walked past every index < i — so if a valid partner exists at one of those earlier indices, we've already seen it. Storing "value → index" as we go means the question "is my complement among the elements I've already passed?" becomes a single O(1) hash-map lookup instead of an O(n) re-scan, collapsing O(n²) into O(n) in one pass.
- Hash Maps & Hash Sets — the complement-lookup dictionary that powers the optimal solution.
- Arrays & Strings — the array being traversed.
- Two Pointers — the alternative approach if the array were pre-sorted and indices didn't need to be original positions.
Two Sum is a vending machine and a pocket of coins — for each new coin, just ask "do I already have its exact match in hand?" instead of re-checking every pair.
The optimal solution inserts nums[i] into seenIndices after checking for the complement, not before. Suppose the target were 2 * nums[i] for some i (e.g., nums = [3, 3], target = 6) — walk through what would go wrong if we inserted the current number into the map before checking for its complement instead.