Two Sum

Free walkthrough Updated Nov 19, 2026 · 5 min read
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].
    2 at index 0 and 7 at index 2 add up to the target 9, so the answer is [0, 2].
    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

    1. Is there always exactly one answer? If not, what do I return when there is none? (Here: one answer; return an empty list otherwise.)
    2. Can the same value appear twice? Can I use one element twice? (Here: values can repeat; an element can't be reused.)
    3. Is the input sorted? (Here: no. If it were, two pointers would need only O(1) extra space.)
    4. 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

    At each step compute need = target − x and look it up; only after the lookup store x with its index.
    At each step compute need = target − x and look it up; only after the lookup store x with its index.

    For each index i with value x:

    • compute need = target − x;
    • if need is 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

    If you store the current number before looking up its partner, a number equal to half the target finds itself.
    If you store the current number before looking up its partner, a number equal to half the target finds itself.

    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 − x can 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) and find(target): trade off which operation is O(1).
    • Pair with a given difference (a − b = k): look up both x − k and x + k.

    Follow-up questions

    1. The array is sorted. Can you do it in O(1) extra space?
    2. What if there can be several pairs and you must return all of them without duplicates?
    3. 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?
    4. What is the worst case of your hash map, and when could it matter?
    5. The list has a billion numbers and doesn't fit in memory. How would you find a pair?
    6. How does the solution change if you must find a pair whose sum is closest to the target?

    Related