Two Sum
On this page
Problem statement
Given a list of integers and a target value, return the positions of the two numbers that add up to the target. Exactly one pair works, you may not use the same element twice, and the positions can be returned in either order. The list is not sorted.
This is often the first question of a phone screen, and the idea behind it (remember what you've seen so you can look up a partner in O(1)) comes back in dozens of harder problems. Original problem: LeetCode 1.
Example
![2 at index 0 and 7 at index 2 add up to the target 9, so the answer is [0, 2].](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-0cf68e17.png)
Input: nums = [2, 11, 7, 15, 4], target = 9
Output: [0, 2] # 2 + 7 = 9
Input: nums = [3, 3], target = 6
Output: [0, 1] # equal values are fine; they are different positions
Constraints (assumed)
- 2 ≤ n ≤ 100,000.
- −10⁹ ≤ nums[i], target ≤ 10⁹.
- Exactly one valid pair exists.
What this question tests
- Spotting that the inner loop of the brute force is a search, and that a hash map turns that search into O(1).
- Handling duplicates and the "same element twice" rule correctly.
- Discussing the time–space trade-off, and the sorted-input variant.
Questions to ask first
- Is there always exactly one answer? If not, what do I return when there is none? (Here: one answer; return an empty list otherwise.)
- Can the same value appear twice? Can I use one element twice? (Here: values can repeat; an element can't be reused.)
- Is the input sorted? (Here: no. If it were, two pointers would need only O(1) extra space.)
- Do you want positions or values? Positions change everything if you plan to sort.
Try it first
Before reading on, try it yourself: the brute force checks every pair. What exactly is the inner loop searching for, and how could you find it without a loop? Sketch the idea and its complexity, then open the solution.
Approach ladder
Weakcheck every pair
Two nested loops: for each i, check every j > i and return when nums[i] + nums[j] == target. Correct and O(1) space, but O(n²) time: with 10⁵ numbers that's about 5 × 10⁹ pairs. Say it in one sentence as your starting point, then improve it.
Goodsort, then two pointers
Sort pairs of (value, original index), put one pointer at each end, and move the left pointer right when the sum is too small and the right pointer left when it's too big. O(n log n) time. It's a good answer when memory is tight, but you must carry original indices through the sort, and it's slower than it needs to be.
Strongone pass with a hash map
The inner loop of the brute force is looking for one specific value: target − x. Keep every number you've seen in a hash map from value to index, and that search becomes a single O(1) lookup. One pass, O(n) time, O(n) space, and indices come for free.
Solution
One pass: look up the partner, then remember the current number

For each index i with value x:
- compute
need = target − x; - if
needis in the map, return[seen[need], i]; - otherwise store
seen[x] = i.
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
Integer j = seen.get(need);
if (j != null) return new int[] { j, i };
seen.put(nums[i], i);
}
return new int[0];
}
vector<int> twoSum(const vector<int>& nums, int target) {
unordered_map<int, int> seen; // value -> index
for (int i = 0; i < (int)nums.size(); i++) {
int need = target - nums[i];
auto it = seen.find(need);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {};
}
func twoSum(nums []int, target int) []int {
seen := make(map[int]int) // value -> index
for i, x := range nums {
if j, ok := seen[target-x]; ok {
return []int{j, i}
}
seen[x] = i
}
return nil
}
Time: O(n), one pass with O(1) average lookups. Space: O(n) for the map in the worst case (the pair is at the very end).
Why duplicates work: for [3, 3] with target 6, the first 3 doesn't find a partner and is stored at index 0; the second 3 finds it and returns [0, 1]. If a value repeats and isn't part of the answer, overwriting its index is harmless.
The common bug

Storing seen[x] = i before the lookup lets an element pair with itself. With [3, 5] and target 6, the buggy version stores 3, then looks for 3, finds index 0, and returns [0, 0]. Always look up first, then store.
A second, quieter bug: building the whole map first and then scanning again. It works only if you check that the partner's index differs from i, and it costs two passes; the one-pass version avoids both.
Edge cases
- Equal values:
[3, 3], target 6 →[0, 1]. - Negative numbers and zero:
[-1, -2, -3, -4], target −6 →[1, 3]. Nothing in the method assumes positives. - Half the target alone:
[3, 5], target 6 → no answer; make sure you don't return[0, 0]. - Pair at the very end: the map grows to n − 1 entries; that's the O(n) space bound.
- Overflow: in Java, C++ and Go,
target − xcan overflow 32-bit ints at the extremes; use 64-bit if values can reach ±2³¹.
Variants seen in interviews
- Sorted input: two pointers from both ends, O(n) time and O(1) space. Often asked as the follow-up.
- Return all unique pairs (values, not positions): sort and use two pointers, skipping duplicates; or a hash map of counts.
- Count pairs that sum to the target: add
count[need]at each step instead of returning. - 3Sum: fix one number and run a two-pointer Two Sum on the rest, O(n²). See 3Sum.
- Two Sum on a stream / as a class with
add(x)andfind(target): trade off which operation is O(1). - Pair with a given difference (
a − b = k): look up bothx − kandx + k.
Follow-up questions
- The array is sorted. Can you do it in O(1) extra space?
- What if there can be several pairs and you must return all of them without duplicates?
- The numbers arrive as a stream and you must answer "does any pair sum to t?" at any time. Which operation do you make fast, and why?
- What is the worst case of your hash map, and when could it matter?
- The list has a billion numbers and doesn't fit in memory. How would you find a pair?
- How does the solution change if you must find a pair whose sum is closest to the target?
Related
- Patterns: Hash Maps and Prefix Sums, Two Pointers
- Similar problems: 3Sum, Subarray Sum Equals K, Longest Consecutive Sequence, Group Anagrams
- Data structures: Hash Maps, Arrays and Strings