Two Sum: practice | DSA Trainer

1. Understand the problem

Problem statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Input

An array of integers `nums` and an integer `target`. Each input has exactly one valid answer, and you can't use the same element twice.

Output

An array of two indexes `[i, j]` (in any order) such that `nums[i] + nums[j] === target`.

Examples

input → nums = [2, 7, 11, 15], target = 9

output → [0, 1]

nums[0] + nums[1] = 2 + 7 = 9, so the answer is [0, 1].

input → nums = [3, 2, 4], target = 6

output → [1, 2]

nums[1] + nums[2] = 2 + 4 = 6.

Quick check

Before we show you any patterns, take a guess even if it's wrong!

You need to find two numbers that sum to a target and return their positions. Which data structure would you reach for?

Pick an answer to continue

2. Spot the pattern

Before any code, every problem starts with a question. For this problem:

“How can I solve this in one pass by remembering the numbers and their positions I’ve already seen?”

The question above points to one structure: a hash map. It stores key-value pairs with O(1) lookup so you can check whether any value exists in a single operation, and retrieve whatever information you stored alongside it.

You’re looking for two numbers that sum up to the target. You have the constant Target, and 1 variable that changes as you loop through the array.

How do you find the third number with the two you have? The answer is a ‘complement check’!

If the target is 9 and you’re at 7, 9-7 = 2, you check for 2 in the map. If 2 is there, you’re done. If it’s not, you store 7 and it’s index in the hash map and grab a different second number.

If the next number is 2, you compute 9-2 = 7 and check for 7 in the map.

Why not Set?

A Set only tells you if a value exists, not where it was. You need to return indexes, so you store each value mapped to its position in a Hash Map.

Quick check

A hash map stores {value: index}. A set stores {value} with no index.

You're at index 2 (value 11, target 9). Complement: 9 - 11 = -2. You check whether -2 appeared earlier.

What can the hash map tell you that the set cannot?

Pick an answer to continue

3. Brute force idea

Check every pair of numbers. For each i, loop j from i+1 to the end and test whether nums[i] + nums[j] equals target.

Brute force (the slow one)

O(n²)

for i in 0 .. len(nums) - 1:
    for j in i + 1 .. len(nums) - 1:    # ← the nested loop is the trap
        if nums[i] + nums[j] == target:
            return [i, j]

Why this is too slow

Every element is compared against every later element. For a list of size n, that's roughly n × n / 2 comparisons, quadratic. On a 10,000-element list, that's ~50 million checks.

Why this is not ideal for interviews

The brute force is the right place to start, it proves you understand the problem. But interviewers listen for the moment you say 'and I can do better.' That pivot, from O(n²) to O(n), is the signal they're waiting for. It tells them you know the hash map pattern exists.

Time: O(n²)

Space: O(1)

4. Climb the hint ladder

Five rungs. Click for the next one only when you genuinely need it. Each rung is a stronger nudge than the last.

5. The optimized approach

Think of the hash map like a notepad sitting next to you as you walk through the list. Every number you pass, you jot down: 'I've seen this value, at this position.' Then when you reach a new number, before jotting it down, you glance at the notepad and ask: 'is the complement already written here?' If it is, you have your answer. If not, add the current number and keep walking.

Pseudocode

seen = empty map  # value -> index

for i, n in enumerate(nums):
    complement = target - n
    if complement in seen:
        return [seen[complement], i]
    seen[n] = i

Quick check

Imagine you're coding the optimal solution using a hash map. The current element is at index i in the array, with the number value n. Target is t.

Which line correctly stores the current element in the map?

Pick an answer to continue

6. Dry run, row by row

Trace it with the first example: nums = [2, 7, 11, 15], target = 9.

step	i	nums[i]	complement	seen before?	seen (after)
1	0	2	9 − 2 = 7	no	{2: 0}
2	1	7	9 − 7 = 2	yes, at index 0	—

step 1: 7 isn't in the map yet. Store 2 with its index.

step 2: 2 is in the map! Return [0, 1] and stop.

Quick check

The Array is: [3, 3], the target: 6. You're at index 0 (value 3). Complement: 6 - 3 = 3.

What happens if you store 3 in the map BEFORE checking for the complement?

Pick an answer to continue

7. The code

You've seen the pseudocode and the dry run. Try writing the solution yourself in the editor on the right. Run your tests there first. The reveal stays here when you're ready to check.

Quick check

The hash map version runs in O(n) instead of O(n²). What did you give up to get there?

Pick an answer to continue

8. Review & common mistakes

Lock it in

What is the signal that tells you to use the Hash Map pattern? Write it in one sentence, in your own words.

Common mistakes

Checking the map AFTER storing the current number
If you store `nums[i]` before checking for its complement, you'll match a number with itself when target is exactly 2×n. Always check first, store second.
Returning the values instead of the indexes
The problem asks for positions, not the numbers themselves. Make sure you return `[seen[complement], i]`, not `[complement, n]`.
Using a nested loop and calling it 'good enough'
The brute force works, but it's O(n²). Interviewers expect you to recognize the hash map pattern and bring it down to O(n).

Pattern family