Two Sum: how to solve it with a hash map, step by step

In this article

1. Before you start
2. Why interviewers ask this
3. Two sum from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview questions guide, which covers the patterns behind problems like this one.

Why interviewers ask this

Two Sum is problem 1 on LeetCode, and a round that starts with it tests whether you reach for a lookup table instead of a second loop. The problem statement itself is short: LeetCode says you are given an array of integers nums and an integer target, and must return indices of the two numbers that add up to the target.

A weak answer writes two nested loops and stops. A strong answer starts there, names its cost, then trades memory for speed with a hash map and explains why the answer cannot reuse one position. A Staff-level answer also states the assumptions it relied on, such as exactly one valid pair, and says what changes if they do not hold.

Two sum from first principles

Two Sum

Two Sum is an array problem that asks for the indices of the two numbers in a list of integers whose sum equals a given target, where the same position may not be used twice and the answer is the positions, not the values.

Complement

The complement of a number x for a given target is the value target minus x, which is the one partner that makes the pair add up to the target. If the array holds that value at a different position, the two numbers are the answer, and looking the complement up is how the solution avoids comparing every pair of numbers.

Hash map

A hash map is a data structure that stores key-value pairs and finds the value for a key in constant time on average by turning the key into a storage position; in the worst case, when many keys collide, a lookup can slow down.

In plain words

Imagine you are handed cards one by one. You must find two cards that add up to nine. You hold a two, so the partner you need is a seven. Comparing every pair of cards is slow. Instead, keep a notepad of the cards you have seen, with each card's position. When a card arrives, check whether its partner is on the notepad. The analogy breaks in one place: a real notepad is slow to search, while a hash map answers in about one step.

Precisely: walk the array once. For each value x, check whether target minus x is already a key in a map from value to index.

Step 1: Turn the target into a lookup

The brute-force idea tries every pair, which is slow. The shortcut is to restate the question. For each number x, you are not asking which other numbers add up to the target; you are asking whether one particular value, the complement target minus x, exists elsewhere in the array.

Input: one number x and the target. Output: the single value you need to find. Asking about one named value is the move that makes a fast lookup possible, because a hash map answers exactly that kind of question. In the example used below, Example 1 of the problem statement with target 9, the number 2 needs a 7. LeetCode states you may assume each input has exactly one solution, that you may not use the same element twice, and that you can return the answer in any order.

Step 2: Remember what you have seen, with positions

You need to know whether the complement appeared earlier, and if so where, because the answer is indices. So you keep a hash map whose keys are the values already read and whose values are their indices. Python calls this a dictionary, and the defaultdict page covers a close relative; the Python interview questions page shows the dictionary habits used here.

Input: the numbers read so far. Output: a map from each value to its position. The map starts empty, so the first number never finds a partner. After you read the 2 at index 0, the map holds one entry: the value 2 pointing to index 0. You now have a structure that answers "have I seen this value, and where?" in one lookup.

Step 3: Check the complement before you insert

For each number, first look up its complement in the map. If it is there, you are done: the answer is the stored index and the current index. If not, insert the current number and its index, then move on.

The order matters. Insert first and the number can find itself. Take nums = [3, 2, 4] and target 6, Example 2 of the problem statement: the 3 has complement 3, and if you store the 3 before checking, the lookup succeeds against its own position and returns [0, 0], which is wrong. The check-then-insert version walks on and returns [1, 2].¹

The failure needs a number that is exactly half the target, so that x equals target minus x. With nums = [3, 3] and target 6, insert-first returns [0, 0], while check-then-insert returns [0, 1].¹ Checking first means the map only ever holds earlier positions, so an index can never pair with itself, which is exactly the rule against using the same element twice.

Step 4: Return the pair of indices

The moment a complement is found, return [seen[need], i]: the earlier index first, the current one second. The statement allows any order, so either order is accepted.

Input: a hit in the map. Output: two indices. The code is short:

def two_sum(nums, target):
    seen = {}                      # value -> index of earlier numbers
    for i, x in enumerate(nums):
        need = target - x          # the complement of x
        if need in seen:           # check first ...
            return [seen[need], i]
        seen[x] = i                # ... insert after

Each number is read once, and each read costs one lookup and at most one insert, so the work grows in step with the length of the array. The function falls off the end without a return only if no pair exists, which the stated promise of one solution rules out.

1 · Complement2 · Seen map3 · Check first4 · AnswerReplay

Step-by-step description

1. Turn the target into a lookup.
2. Store value to index.
3. Look up before inserting.
4. Return the two indices.

• The complement of x is target minus x.
• A hash map from value to index lets one pass find the complement.

The complement of x is target minus x. A hash map from value to index lets one pass find the complement.

Worked example

Take nums = [2, 7, 11, 15] and target = 9, which is Example 1 of the problem statement, run in code.¹ At index 0 the number is 2, its complement is 7, and the map is empty, so 7 is not found; the map becomes {2: 0}. At index 1 the number is 7, its complement is 2, and 2 is in the map at index 0. The function returns [0, 1] after two lookups and never reads 11 or 15.¹

The duplicate example from the problem page works the same way: nums = [3, 3] and target = 6 returns [0, 1]. The first 3 finds nothing and is stored; the second 3 finds the first. Equal values at two different indices are allowed, because only reusing the same index is forbidden.¹

The pair count is n times n minus 1, divided by 2, which at the stated maximum length of 10,000 numbers gives 49,995,000.¹ The statement limits the array to between 2 and 10,000 numbers, and each value and the target to between minus one billion and one billion. Two values of one billion sum to 2,000,000,000, which is 147,483,647 below the signed 32-bit maximum, so a 32-bit integer does not overflow under those limits.¹ The overflow check matters in Java or C++, not in Python, whose integers do not overflow. The complement target - x ranges from minus 2,000,000,000 to 2,000,000,000, which also fits in 32 bits.¹

Text description of the diagram

• A brute force checks 49,995,000 pairs at 10,000 numbers.
• The hash-map pass does at most 10,000 lookups at 10,000 numbers.

Brute force at 10,000 numbers is about fifty million cheap comparisons,¹ so whether a judge accepts it depends on that judge's time limit, which the statement does not give. In an interview, the point is the growth, not this one input.

Trade-offs and edge cases

The hash-map answer buys speed with memory: it is linear in time on average but holds up to n entries. Brute force checks every pair and keeps no extra memory, which is the right opening answer for a tiny array. The hash map is the usual answer because it is linear on average and keeps the original indices.

The sorting alternative is often mentioned. Sort the numbers, then move one pointer in from each end: if the sum is too small, move the left pointer up; if too large, move the right pointer down. It needs no map, but sorting loses the original indices unless you carry them along, and the sort itself costs more than a linear pass. It shines when the input is already sorted.

Text description of the diagram

• Brute force checks every pair and keeps no extra memory.
• Sorting loses the original indices unless you carry them along.
• The hash map is linear on average and is the usual answer.

Edge cases: a lookup is constant time on average, but the Python wiki lists the worst case as linear when many keys collide, which is the "hash map" caveat in its definition. Negative numbers are allowed in both the array and the target according to the problem statement, and the map approach needs no special handling for them. If several pairs could exist, the first complement found is returned, so say so aloud. For the same one-pass map idea applied to sums over ranges, see subarray sum equals k. The sliding-window problem also uses a one-pass map.

How to answer it in an interview

The spoken structure: name the brute force and its cost, define the complement, describe the map, state check-before-insert, then give time and space.

Common mistakes

• "I return the two numbers." (wrong) The problem asks for positions. (right) "I return the indices of the two numbers."
• "The same value cannot appear twice." (wrong) Equal values at different indices are fine; only one index may not be used twice. (right) "I may not reuse an index, but a duplicate value at another index is a valid partner."
• "I sort and use two pointers, and that is the answer." (wrong) Sorting loses the original indices, so you must carry them. (right) "Sorting works if I keep each value's index, but it is slower than the map for an unsorted array."
• "A hash lookup is always constant time." (wrong) It is constant on average and can degrade in the worst case. (right) "Lookups are constant time on average."
• "I insert the number, then look for the complement." (wrong) A number can match itself. (right) "I look up first, then insert."

Follow-up questions

What is the time complexity of Two Sum?

The hash-map solution reads each number once and does one lookup and one insert per number, so time is O(n) on average and extra space is O(n). The brute force is O(n²) in time with O(1) extra space.

Why check the map before inserting the current number?

Because the map must hold only earlier positions. If the current number is inserted first, its complement can be itself, as in the [3, 2, 4] target 6 case, and the result pairs an index with itself.

What if the array is already sorted?

Use two pointers, one at each end, moving the left up when the sum is too small and the right down when it is too large. That needs no extra memory and still gives the original indices when the array arrives sorted.

What if there are several valid pairs?

The statement says only one valid answer exists, so the solution may return the first pair it finds. If the interviewer drops that assumption, ask whether they want any pair, all pairs or a count, because that changes the data you must keep.

Is a subarray whose sum is a multiple of k the same problem as Two Sum?

No. That is a different problem about contiguous subarrays, not about two numbers adding to a target. Keep a running sum modulo k and a map from each remainder to the first index where it appeared, seeded with remainder 0 at index −1. If the same remainder shows up again at least two positions later, the elements between those positions sum to a multiple of k. It shares the idea of a hash map filled as you scan with the related prefix-sum problem, subarray sum equals k.

Sources

1. Two Sum (problem 1) — LeetCode (accessed 2026-10-26; the page is undated), 26 Oct 2026
2. Mapping Types: dict (Python standard library reference) — Python Software Foundation (accessed 2026-10-26; the page is versioned, not dated), 26 Oct 2026
3. TimeComplexity (Python wiki) — Python Software Foundation wiki (accessed 2026-10-26; the page is undated), 26 Oct 2026