Skip to content
16-Week DSA Roadmap
LeetCode #1EasyProblem 3 of 8

Two Sum

Find the two numbers in an array that add up to a target, and return their positions.

  • Hash map lookup
  • Complement

Before this, know: Arrays and indexes, Hash maps (Map in JavaScript, dict in Python)

The problem in plain English

You get a list of numbers called nums and one more number called target. Somewhere in the list, exactly two numbers add up to target. Your job is to say where they are.

“Where” means their index: the position of an item in the list. Indexes start at 0, so the first item is at index 0, the second at index 1, and so on.

Here is a small example. nums = [4, 1, 5, 3] and target = 8:

nums
  1. 40
  2. 11
  3. 52
  4. 33
5 + 3 = 8, and they sit at indexes 2 and 3, so the answer is [2, 3].

So the answer is [2, 3]. A few rules from the problem statement:

  • There is always exactly one correct pair.
  • You can’t use the same position twice. If target is 8 and there is one 4, you can’t answer [0, 0].
  • You may return the two indexes in any order.

Before you code: think it through

That “someone wearing a 3” has a name in this problem: the complement. It’s the missing piece that completes your number:

target = 85? = 3nums[i]need = target − nums[i]
If the number in front of us is 5 and the target is 8, the partner we need is 8 − 5 = 3.

Pause and think

The target is 9 and you're looking at the number 7. Which number do you need to find? And what if you're looking at 11?

Approach 1: Brute force

Brute force means “try every possibility”. It’s the most obvious idea, and it’s always a good first step to say out loud in an interview.

The idea: pick the first number, then add it to every number after it. Then pick the second number and add it to every number after that. Stop when a sum equals the target. We use two pointers (variables that remember a position): i for the first number and j for the second.

Brute force: try every pair

nums = [4, 1, 5, 3], target = 8

nums
  1. 40
  2. 11
  3. 52
  4. 33
variables
target
8
nums[i] + nums[j]
—
checks so far
0
  • First number (i)
  • Second number (j)
  • Pair that works

Pick nums[0] = 4 as the first number. Now try every number after it.

Step 1 / 10

Which line is running?

function twoSum(nums, target) {Running now:   for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] + nums[j] === target) {        return [i, j];      }    }  }  return []; // LeetCode promises an answer exists, so we never get here}

Brute force

function twoSum(nums, target) {  for (let i = 0; i < nums.length; i++) {    for (let j = i + 1; j < nums.length; j++) {      if (nums[i] + nums[j] === target) {        return [i, j];      }    }  }  return []; // LeetCode promises an answer exists, so we never get here}
def two_sum(nums, target):    for i in range(len(nums)):        for j in range(i + 1, len(nums)):            if nums[i] + nums[j] == target:                return [i, j]    return []  # LeetCode promises an answer exists, so we never get here

j always starts at i + 1. That does two jobs: we never pair a number with itself, and we never check the same pair twice (4 + 1 is the same as 1 + 4).

Why is it slow?

Count the checks. With 4 numbers, the first number is checked against 3 others, the second against 2, the third against 1:

3 + 2 + 1 = 6 checks. That’s fine.

With 10,000 numbers it’s 9,999 + 9,998 + … + 1, which is 10,000 × 9,999 ÷ 2 = 49,995,000 checks. About fifty million! In general, for n numbers we do about n × n ÷ 2 checks.

We describe this growth with Big-O notation: a way of saying how the work grows as the input grows. Work that grows like n × n is written O(n²) (“O of n squared”): double the input, and the work goes up four times.

The pattern: hash map lookup

The brute force spends almost all its time searching for a partner. What if looking up “is there a 3?” took one step instead of a whole scan?

That’s exactly what a hash map gives us. A hash map stores key → value pairs, like a dictionary stores word → meaning, and it can answer “do you have this key?” in about one step, no matter how many items it holds. In JavaScript it’s called a Map; in Python it’s a dict.

Pattern

Hash map lookup (complement)

Template

Use it when: you need to find a pair (or partner) that satisfies a condition, and checking every pair would be too slow.

Signal words

  • “two numbers that add up to”
  • “find a pair”
  • “return their indices”
  • “has a matching element”

Approach 2: One pass with a hash map

  1. Create an empty hash map called seen. It will remember number → index for every number we pass.
  2. Walk through the list one number at a time. Call the current index i.
  3. Work out the partner we need: need = target − nums[i].
  4. Ask the map: is need in seen? If yes, we’re done. Return [seen[need], i].
  5. If not, write the current number into the map, seen[nums[i]] = i, so later numbers can find it. Then move on.

Press Play, or click the player and use the arrow keys. Watch the code panel underneath: the highlighted line is the one running at that moment. Try the edge-case buttons too.

One pass with a hash map

nums = [4, 1, 5, 3], target = 8

nums
  1. 40
  2. 11
  3. 52
  4. 33
seen0 items
numberindex
empty
variables
target
8
i
—
nums[i]
—
need
—
answer
—
  • Looking at now
  • Already written in the map
  • Partner found
  • Partner not found (yet)
  • Just written in the map

We want two numbers that add up to 8. We start with an empty hash map called "seen": a notebook where we'll write down every number we pass and its index.

Step 1 / 17

Which line is running?

function twoSum(nums, target) {Running now:   const seen = new Map(); // number -> the index where we saw it  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 []; // LeetCode promises an answer exists, so we never get here}

Notice the order inside the loop: we check first, then write. That’s what stops a number pairing with itself. Try the “duplicates” example: with [3, 3] and target 6, the first 3 doesn’t find a partner (the map is empty), so it gets written down. The second 3 then finds the first one.

The code, line by line

One pass with a hash map

function twoSum(nums, target) {  const seen = new Map(); // number -> the index where we saw it  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 []; // LeetCode promises an answer exists, so we never get here}
def two_sum(nums, target):    seen = {}  # number -> the index where we saw it    for i, num in enumerate(nums):        need = target - num        if need in seen:            return [seen[need], i]        seen[num] = i    return []  # LeetCode promises an answer exists, so we never get here

Lines 1–6 are the same in both languages; after that JavaScript has an extra closing brace }, so its line numbers run one ahead.

  • Line 1: define the function. It takes the list nums and the number target. (On LeetCode, Python wraps this in class Solution as def twoSum(self, nums, target); the body is identical.)
  • Line 2: create an empty hash map. new Map() in JavaScript, {} in Python. We’ll store each number as the key and its index as the value, because the index is what we have to return at the end.
  • Line 3: loop over every position. In JavaScript i counts 0, 1, 2…; in Python enumerate(nums) hands us both the index i and the number num each time.
  • Line 4: compute the complement, the partner this number needs.
  • Line 5: the key question. seen.has(need) / need in seen asks the map whether that partner has already gone by. This takes about one step, which is the whole reason the solution is fast.
  • Line 6: if it has, we know both positions: the partner’s index (stored in the map) and our own index i. Return them.
  • Line 8 (JS) / line 7 (Python): otherwise, remember the current number and its index for later. This happens after the check on purpose (see the mistakes section).
  • The last line: the problem promises an answer exists, so we never reach it. It’s there so the function always returns a list.

Dry run

Let’s trace nums = [4, 1, 5, 3], target = 8 by hand, the way you’d do it on a whiteboard. Each row is one trip around the loop.

inums[i]need = 8 − nums[i]need in seen?what happensseen afterwards
044no (empty)write 4 → 0{4: 0}
117nowrite 1 → 1{4: 0, 1: 1}
253nowrite 5 → 2{4: 0, 1: 1, 5: 2}
335yes, at index 2return [2, 3](we stop here)
nums = [4, 1, 5, 3], target = 8

Look at the i = 0 row: the number 4 needs another 4. The map is empty, so there’s no match, which is correct: there is only one 4, and we can’t use it twice.

Complexity

Brute force

Time

O(n²)

Every number is checked against every number after it: about n × n ÷ 2 additions.

Space

O(1)

Only two pointers, i and j, no matter how long the list is. O(1) means 'a fixed amount'.

One pass with a hash map

Time

O(n)

We visit each number once, and each map lookup or insert takes about one step. 10,000 numbers ≈ 10,000 steps, not 50 million.

Space

O(n)

In the worst case (the pair is at the very end) the map ends up holding almost every number.

This is a classic trade: we spend extra memory (the map) to save a huge amount of time. In interviews that trade is almost always worth it, and it’s worth saying out loud.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Restate the problem and confirm: “Exactly one answer? Can I use the same element twice? Any order?”
  2. Give the brute force and its cost: “Checking every pair is O(n²) time, O(1) space.”
  3. Spot the waste: “Most of the time goes into searching for the partner.”
  4. Fix it: “A hash map makes that search one step, so one pass is O(n) time, at the cost of O(n) extra space.”
  5. Walk through a small example (like the dry run above) before and after coding.

Likely follow-up questions:

  • “What if the array is sorted?” Then you don’t need the map at all: put one pointer at each end and move them toward each other. That’s O(n) time with O(1) space. It’s Two Sum II, coming up in week 2.
  • “What if there could be no answer?” Return an empty list (our last line already does).
  • “Return all pairs?” You’d keep going instead of returning, and think about duplicates.

Related problems: