Two Sum
Problem statement
You are given a list of integers nums and a target number target. Find the
two different positions in the list whose values add up to target, and
return those two positions (their indices) as a pair.
You can assume there is exactly one correct pair for the given input, and you
cannot use the same element twice (so if the list has one 7 and the target
needs two 7s, that does not count — you'd need two separate 7s at two
different positions).
A simple way to picture this: imagine nums is a list of memory sizes (in MB)
requested by different jobs, and target is the total memory available on a
box. You want to know which two jobs, packed together, exactly fill the box.
Examples
Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9, so the answer is the pair of indices [0, 1].
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: nums[1] + nums[2] = 2 + 4 = 6. Note that nums[0] + nums[1] = 3 + 2 = 5, which is not the target, so index 0 is not part of the answer.
Example 3
Input: nums = [3, 3], target = 6
Output: [0, 1]
Explanation: nums[0] + nums[1] = 3 + 3 = 6. Both values are equal, but they sit at two different positions, so they still form a valid pair.
Hints
Approach
Optimal: Hash map
Intuition
Sorting works, but it does more than you actually need — you don't care about the numbers in order, you only care whether a specific value exists somewhere in the list. A hash map answers "have I seen this value, and where?" in roughly constant time, so you can check that question as you walk through the list just once, with no sorting at all.
For each number x, the value you're looking for is target - x (its
"complement"). If you've already seen that complement earlier in the list,
you're done — you found the pair. If not, remember x and its position, and
keep going. Because you check before adding the current number, you never
accidentally pair a number with itself.
This is the fastest approach here: a single pass, O(n) time, and it's usually what interviewers are looking for as the final answer.
Steps
- Create an empty hash map called
seen(it will map a value to the index where it was found). - Walk through
numswith its indexi, looking at valuex = nums[i]. - Compute
complement = target - x. - If
complementis already a key inseen, return[seen[complement], i]— you found the pair. - Otherwise, store
seen[x] = iand move to the next number.
Edge cases: a list with fewer than two numbers can never find a pair (the loop finishes with nothing to return). Two equal values that sum to the target (e.g. nums = [3, 3], target = 6) still work correctly, because the first 3 is stored in seen before the second 3 is checked against it — they are never the same position.
Complexity
Time O(n) - a single pass over the list, and each hash map lookup or insert takes constant time on average
Space O(n) - in the worst case (no match until the very last element) the map ends up holding almost every value
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
if len(nums) < 2:
return [] # a pair needs two different positions
seen = {}
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
if __name__ == "__main__":
print(Solution().twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(Solution().twoSum([3, 2, 4], 6)) # [1, 2]
print(Solution().twoSum([3, 3], 6)) # [0, 1]RecapThe whole problem in a few lines, for the night before
- Spot it: "find two numbers that add up to a target" in an unsorted list
- Idea: for each number, its partner is
target - number— use a hash map to check instantly if you've already seen that partner - Cost: O(n) time, O(n) space (brute force: O(n²) time, O(1) space; sort + two pointers: O(n log n) time, O(n) space)
- Trap: don't pair a number with itself — check the map *before* adding the current number to it
- Remember: if the array is already sorted, two pointers solve it in O(n) time and O(1) space
Interview follow-ups
What if
numsis already sorted — can you solve it using only O(1) extra space?Yes. When the array is already sorted, you don't need the "better" approach's sorting step or its extra array of indices — you can run the two-pointer scan directly on
nums. Start one pointer at the first element and one at the last, and move them exactly as in the "Better" approach above. Because no extra map or index array is needed, this uses O(1) extra space instead of O(n), while staying at O(n) time.What if you need to find every pair that adds up to the target, not just one?
Keep the same hash map idea, but instead of returning immediately on the first match, keep collecting every matching pair into a results list and continue the loop to the end. Watch out for duplicate values — if the same number appears more than once, you'll want to make sure you're not reporting the same pair of positions twice or pairing a position with itself. The overall time stays O(n), just with a bit more bookkeeping.
Frequently asked questions
Both eventually find the answer, but sorting costs O(n log n) just to put the numbers in order, and it also complicates keeping track of the original positions. The hash map checks each number once, in the order it already appears, and never needs to reorder anything — that's what brings the total time down to O(n).
The problem guarantees exactly one valid answer for the given input, so none of these approaches worry about multiple matches. If a variant of this problem asked for all pairs that sum to the target, you would need to keep collecting matches instead of returning on the first one — see the follow-up below.
All three approaches return an empty list in that case. In practice, LeetCode only tests inputs that do have exactly one answer, but it's worth handling the "no answer" case gracefully in real code rather than assuming a valid pair always exists.
Yes, as long as they sit at two different positions — see Example 3
(nums = [3, 3], target = 6). The rule is about positions, not values: you
can never reuse the same index twice, but two different indices holding the
same value are perfectly fine.
This is usually an opening warm-up question, used to see how quickly you spot that a hash map turns a "check every pair" problem into a single pass. The same idea — "have I already seen this key?" — shows up constantly in infra work: matching a response to a pending request by ID, checking whether a metric name has already been counted, or pairing start and end log lines for the same request.
