Two Sum
Asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Uber, Atlassian, Walmart
Problem
Two Sum asks you to find two numbers in an array that add up to a target value, then return their indices. It is one of the most frequently asked opening questions in FAANG interviews — used to gauge how you think about time and space tradeoffs before moving to harder problems.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Apple | Easy | View all Apple questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Oracle | Easy | View all Oracle questions → |
| Uber | Easy | View all Uber questions → |
| Atlassian | Easy | View all Atlassian questions → |
| Walmart | Easy | View all Walmart questions → |
How to Think About It
Brute force: try every pair. Use two nested loops — for each element i, check every element j after it. If nums[i] + nums[j] == target, return [i, j]. This works but is O(n²) time because you check n*(n-1)/2 pairs. The interviewer will immediately ask you to optimize.
Key insight: for each number, you already know what its partner must be. If the current number is 7 and the target is 10, the partner must be 3. You don't need to search for it — just check if you've seen 3 before. That's a hash table lookup: O(1).
The pattern: as you walk through the array once, store each number and its index in a hash map. At each step, calculate the complement (target - current). If the complement is already in the map, you found both indices. If not, store the current number and keep going.
Why this works: the brute force checks "for each i, does any j exist?" The hash table flips it to "for each j, did I already see its complement?" Same question, but now each lookup is O(1) instead of O(n).
Edge cases: the problem guarantees exactly one solution, so you will always find a pair. If the interviewer asks "what if there are multiple valid pairs?" — that's a follow-up (return all pairs). Also handle: target = 0 with negative numbers, single element array.
Optimal Approach
Initialize an empty hash map. Iterate through the array with index i and value num. Calculate complement = target - num. Check if complement exists in the hash map. If yes, return [hash_map[complement], i]. If no, store num: i in the hash map and continue.
Walkthrough with example: nums = [2, 7, 11, 15], target = 9.
i=0,num=2,complement=7. Map empty. Store{2: 0}.i=1,num=7,complement=2. Map has 2 at index 0. Return[0, 1].
Time: O(n) — one pass through the array. Space: O(n) — hash map stores up to n elements.
What Trips People Up in Real Interviews
Jumping straight to code without stating the brute-force first. Interviewers want to hear you reason about O(n²) before optimizing to O(n). Say: "My first thought is to check every pair, which is O(n²). I can do better with a hash map."
Confusing "return the indices" with "return the values." The problem asks for indices, not the numbers themselves. Re-read the return type before coding — this is the #1 careless mistake on Two Sum.
Forgetting that the same element cannot be used twice. If nums = [3, 3] and target = 6, you need two different indices. Your hash map must store the index and check it after storing the current element.
Trying two pointers on an unsorted array. Two pointers requires sorted input, and sorting loses the original indices. The hash map one-pass approach is the correct fit here.
Not handling the edge case where complement equals the current number. If target = 6 and current = 3, you need another 3 at a different index. Store the current element first, then check for complement on the next iteration.
Solution Code
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []Frequently Asked Questions
What is the Two Sum problem?
Two Sum asks you to find two numbers in an array that add up to a target value, then return their indices. It is one of the most frequently asked opening questions in FAANG interviews — used to gauge how you think about time and space tradeoffs before moving to harder problems.
How do you solve Two Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Two Sum?
Two Sum is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Uber, Atlassian, Walmart. It is a easy difficulty problem.
What are common mistakes on Two Sum?
- Jumping straight to code without stating the brute-force first. Interviewers want to hear you reason about `O(n²)` before optimizing to `O(n)`. Say: "My first thought is to check every pair, which is `O(n²)`. I can do better with a `hash map`."
- Confusing "return the indices" with "return the values." The problem asks for indices, not the numbers themselves. Re-read the return type before coding — this is the #1 careless mistake on Two Sum.
- Forgetting that the same element cannot be used twice. If `nums = [3, 3]` and `target = 6`, you need two different indices. Your `hash map` must store the index and check it after storing the current element.
- Trying two pointers on an unsorted array. Two pointers requires sorted input, and sorting loses the original indices. The `hash map` one-pass approach is the correct fit here.
- Not handling the edge case where complement equals the current number. If `target = 6` and `current = 3`, you need another 3 at a different index. Store the current element first, then check for complement on the next iteration.