Two Sum
Find the two positions in an array whose values add up to a target. The classic warm-up for trading a nested loop for a hash map. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an array of integers nums and an integer target. Return the indices of the two different elements whose values add up to target.
Every input has exactly one valid pair, and you can't use the same element twice. Return the two indices in increasing order.
Example 1
- Input
- nums = [3, 8, 12, 5], target = 17
- Output
- [2, 3]
nums[2] + nums[3] = 12 + 5 = 17.
Example 2
- Input
- nums = [4, 4, 1], target = 8
- Output
- [0, 1]
The two 4s are different elements, so they can pair with each other.
Example 3
- Input
- nums = [-2, 9, 6], target = 4
- Output
- [0, 2]
Constraints
- 2 ≤ nums.length ≤ 10⁴
- -10⁹ ≤ nums[i], target ≤ 10⁹
- Exactly one pair of indices adds up to target.
Practice
Runs 10 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Two Sum in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Two Sum
Pattern: Hash map of complements
For any number x, the only partner that works is target - x, its complement. So the real question at each position is "have I already seen my complement?"
A hash map from value to index answers that in constant time. Walk the array once: before storing the current number, check whether its complement is already in the map. Because you check before you insert, an element can never pair with itself, and duplicates like [4, 4] still work.
Approach 1: Brute force: check every pair
Two nested loops try every i < j and return the first pair that sums to target. Correct and easy to explain, but it re-scans the array for every element.
Time O(n²) · Space O(1)
Approach 2: Sort with two pointers
Sort (value, index) pairs, then move a left and right pointer inward: if the sum is too small move left up, if too big move right down. Faster than brute force, but sorting costs O(n log n) and you have to carry original indices through the sort.
Time O(n log n) · Space O(n)
Approach 3: One pass with a hash map
Keep a map of value → index for everything seen so far. For each nums[i]:
- Compute
need = target - nums[i]. - If
needis in the map, you're done: return[seen[need], i]. The stored index is always smaller, so the answer is already in order. - Otherwise store
nums[i] → iand keep going.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Brute force: check every pair | O(n²) | O(1) |
| Sort with two pointers | O(n log n) | O(n) |
| One pass with a hash map | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Two Sum solution in Python
def two_sum(nums: list[int], target: int) -> list[int]:
seen = {} # value -> index
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []Two Sum solution in JavaScript
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return [];
}Common mistakes
- Inserting the current number before checking for its complement, which lets an element pair with itself (target 8 with a single 4).
- Returning values instead of indices.
- Sorting the array in place and then returning indices into the sorted copy.
- Assuming the inputs are positive. The complement can be negative or zero.
What interviewers look for
Start by saying the brute force out loud and naming its cost. Interviewers want to see that you know where the O(n²) comes from: each element searches for its partner linearly. Then point out that the search is the bottleneck, and a hash map turns "search" into "lookup". That framing carries over to dozens of other problems.
Mention the check-then-insert order explicitly, and test it on a duplicate case like [4, 4] before you say you're done.
Follow-up questions
What if the array is already sorted?
Use two pointers from both ends. It runs in O(n) time with O(1) extra space, which beats the hash map on memory.
What if you need every pair that sums to the target?
Keep a count of each value instead of a single index, and either collect index pairs or, if only distinct value pairs matter, de-duplicate as you go. The pattern generalizes to 3Sum by fixing one element and running Two Sum on the rest.
What if the input is a stream too large to hold in memory?
You still need to remember the values you have seen to find a partner later, so memory grows with the number of distinct values. If the stream is sorted or can be bucketed by value, you can process it in chunks.
Companies that ask Two Sum
Two Sum is tagged by 196 companies in our interview dataset. The score shows how often it comes up at each company.
- Google100%
- Amazon100%
- Microsoft100%
- Bloomberg100%
- Infosys100%
- Adobe100%
- Accenture100%
- Epam Systems100%
- SAP100%
- Capgemini100%
- Yahoo100%
- Bloomreach100%
- Intel100%
- Tinkoff100%
- Wipro100%
- Nasdaq100%
- Hcl Technologies100%
- Jb Hunt100%
- Mastercard100%
- Netapp100%
- Citigroup100%
- Comcast100%
- Garmin100%
- Delhivery100%
and 172 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required