Why check the map before inserting the current number?

If the number were recorded first, a target equal to twice that number would find the number itself and return the same index twice. Looking up the complement first means the map only holds earlier indices.

What is the time and space complexity of Two Sum with a hash map?

O(n) time on average: each number is looked up and recorded once, and a hash map lookup takes O(1) on average. O(n) extra space for the map.

When is two pointers better than a hash map for Two Sum?

When the input is already sorted, as in Two Sum II. Two pointers then finds the pair in O(n) time with O(1) extra space. Sorting an unsorted array first would lose the original indices that Two Sum asks for.

Two Sum

Find the indices of two numbers that add up to a target in one pass with a hash map.

EasySolve on LeetCode

Problem Understanding

Two Sum: given an array nums and a target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and the same element may not be used twice.

Example: nums = [2, 7, 11, 15], target = 9 returns [0, 1], because 2 + 7 = 9.

Attempt 1: Check Every Pair

Try every pair i < j and return the first one whose values sum to target. Two nested loops: O(n²) time, O(1) extra space. For each nums[i], the inner loop is really asking one question — is target - nums[i] somewhere else in the array? — and it answers it by scanning.

Visualizing the Issue

The inner loop rescans numbers it has already looked at. By the time the outer loop reaches index 5, indices 0 to 4 have each been read several times, and nothing was remembered. A hash map remembers them: one lookup replaces the whole inner scan.

The Intuition: Look Up the Complement

Walk the array once. For each number, the partner it needs is need = target - nums[i].

If need was seen earlier, the pair is found: return the stored index of need and i.
Otherwise, record nums[i] -> i so a later number that needs it can find it.

The order matters: look up first, record second. That way the map only ever contains earlier indices, so a number can never be paired with itself.

Interactive Walkthrough

target = 9

START

nums

Need

—

Answer

—

seen (value → index)

Empty

Find two indices whose values add up to 9. seen starts empty

nums[0] = 2: it needs 9 − 2 = 7

Array

Target

Legend & Complexity

i: the number being processed

The seen entry looked up or just recorded

The two indices returned

Time

O(n)

Space

O(n)

The array is scanned left to right while seen fills up beside it as value → index. On each step, watch the lookup for need — it either finds an earlier index and the two answer cells fill, or it misses and the current number is recorded.

Dry Run Table

Input: nums = [3, 2, 4], target = 6

`i`	`nums[i]`	`need`	In `seen`?	`seen` after
0	3	3	no — the map is empty	`{3: 0}`
1	2	4	no	`{3: 0, 2: 1}`
2	4	2	yes, at index 1	— return `[1, 2]`

At i = 0, need is 3 — the number's own value. Because the lookup happens before 3 is recorded, it misses, and index 0 is never paired with itself.

Why Not Sort and Use Two Pointers?

Sorting and walking two pointers inward finds a pair in O(n log n) time — but the sort moves every number, and Two Sum asks for the original indices. You would have to sort (value, index) pairs to keep them. When the array is already sorted, as in Two Sum II, two pointers wins: O(n) time and O(1) space. Unsorted input with indices required is the hash map's case.

The Solution Template

One pass with a value → index hash map.

Two Sum Code

1var twoSum = function(nums, target) {
2    const seen = new Map();
3    for (let i = 0; i < nums.length; i++) {
4        const need = target - nums[i];
5        if (seen.has(need)) {
6            return [seen.get(need), i];
7        }
8        seen.set(nums[i], i);
9    }
10    return [];
11};

Edge Cases & Common Mistakes

Same value twice ([3, 3], target 6): the second 3 finds the first in the map — answer [0, 1]. This only works because the lookup comes before the insert.
Recording before looking up: with [3, 2, 4] and target 6, index 0 would find itself and return [0, 0].
Negative numbers and zero: nothing changes — the complement is just target - nums[i].
Returning values instead of indices: the map stores indices because the problem asks for them.

Summary

Two Sum is the hash map pattern in its smallest form: turn "is the partner somewhere in the array?" into a single lookup by remembering what you have already seen. Look up first, record second.

Valid Anagram