Two Sum

You are given a list of integers nums and a number target. Exactly one pair of different positions in the list holds values that add up to target.

Return the two positions (0-based indices) of that pair. The order of the two indices in your answer does not matter.

Example 1

Example 2

Example 3

Constraints

• 2 <= nums.length <= 104
• -109 <= nums[i], target <= 109
• Exactly one valid pair exists.

Pattern Path · Hashing & Counting · problem 1 of 169

Start simple

Try every pair (i, j) with two nested loops: O(n²) time, O(1) space.

The key idea

Scan the list once while remembering every value you have passed and its index. For the current value x, its partner must be target - x. If that partner is already in the dictionary, the pair is complete. Otherwise store x and move on.

Checking before inserting matters: it stops an element from pairing with itself, and it still handles duplicates like [3, 3], because the first 3 is stored when the second one arrives.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def twoSum(self, nums, target):
        seen = {}
        for i, x in enumerate(nums):
            if target - x in seen:
                return [seen[target - x], i]
            seen[x] = i

JavaScript

var twoSum = function(nums, target) {
  const seen = new Map();
  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);
  }
};

What the interviewer is checking

This is a warm-up to see whether you reach for a hash map to trade memory for speed, and whether you can explain that trade-off out loud.

Mistakes to avoid

• Inserting before checking, which pairs an element with itself when target = 2·x.
• Returning the values instead of their indices.
• Sorting first and losing the original indices.

Follow-ups to expect

• What if the input is already sorted? (Two pointers, O(1) extra space.)
• What if you must return every pair, or the input is a stream?
• What if the data does not fit in memory?

In real software

Matching payments to invoices that sum to an amount, or finding two items that fit a budget, uses the same remember-what-you-have-seen idea.

Practice next