Hash Tables — Visual Learning

Two Sum —
Hash map turns O(n²) into O(n).

Two Sum is the most common interview problem — and the perfect demonstration of why hash maps matter. Brute force checks every pair in O(n²). With a hash map you check for the complement in O(1) as you scan once. Watch the map build and the lookup fire on LearnBug and the O(n) solution becomes completely intuitive.

O(n)Time complexity
O(n)Space complexity
PythonLanguage

What is Two Sum?

Given an array of integers and a target, return the indices of two numbers that add up to the target. For [2, 7, 11, 15] with target 9, return [0, 1] because 2 + 7 = 9. The key insight: for each number x, you need target - x. If that complement is already in your hash map, you found the pair.

Why the hash map makes it O(n)

Instead of checking every pair (O(n²)), you build a map of value → index as you scan. At each element, check if its complement exists in the map — an O(1) lookup. You never look back at previous elements with a loop. On LearnBug you watch the map grow entry by entry and the complement check resolve instantly.

YouTube — Two Sum Hash Map Explained
📺 Drop your YouTube embed here
LearnBug — hash map building and complement firing
🖼 Add a LearnBug screenshot here
Three Approaches

Brute force → sorted two pointer → hash map

Brute Force — O(n²)

Check every pair with two nested loops. Simple but too slow for large arrays. The inner loop always scans from j=i+1 to end.

O(n²)O(1) spaceToo slow

Sorted + Two Pointer — O(n log n)

Sort the array, then use two pointers from both ends. Works when you only need values (not original indices). Sorting costs O(n log n).

O(n log n)O(1) spaceNo original indices

Hash Map — O(n) ✓

One pass. For each element check if its complement is in the map. If yes — done. If no — add the current element to the map. Returns original indices.

O(n)O(n) spaceOptimal
Walkthrough

Hash map approach on [2, 7, 11, 15], target=9

1

i=0, val=2. Complement = 9-2 = 7. Is 7 in map? No.

Map is empty. 7 not found. Add 2 → 0 to map and continue.

2i=0
7
11
15
Map: { 2: 0 }  |  Looking for: 7 — not found
2

i=1, val=7. Complement = 9-7 = 2. Is 2 in map? YES!

Map contains 2 → 0. Found! Return [map[2], 1] = [0, 1]. Done in 2 steps.

2idx=0
7i=1
11
15
Map: { 2: 0 }  |  Looking for: 2 ✓ FOUND at index 0

Return: [0, 1] ✓ (2 + 7 = 9)

Python Code

All three approaches

PythonHash Map — O(n) time, O(n) space
def two_sum(nums, target):
    seen = dict()    # value → index

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i   # add AFTER checking to avoid using same element twice

    return []
PythonTwo Pointer — O(n log n), works for sorted input or when indices not needed
def two_sum_sorted(nums, target):
    # Only works if array is already sorted (or you don't need original indices)
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]
        if   total == target: return [left, right]
        elif total <  target: left  += 1
        else:                right -= 1

    return []

Approach Comparison

Brute ForceO(n²) / O(1)Time / Space — never use in an interview
Two PointerO(n log n) / O(1)Requires sorted input — loses original indices
Hash MapO(n) / O(n)One pass — preserves indices — optimal for the standard problem
Why add AFTER checking?Avoid self-matchIf target=6 and val=3, adding first would match 3 with itself

Frequently asked questions

Why do we add the element to the map AFTER checking for the complement?

If target = 6 and the current element is 3, its complement is also 3. If we added 3 to the map first, we'd find it immediately and return [i, i] — the same index twice. Adding after checking ensures the complement must be a previously seen element at a different index.

What if there are multiple valid pairs?

The standard LeetCode problem guarantees exactly one solution. If there could be multiple pairs, you'd collect all answers into a result list instead of returning on first match. The hash map approach extends naturally — just don't return early.

How does this extend to Three Sum?

Three Sum (LC 15) fixes one element with an outer loop, then runs Two Sum on the remaining elements. With sorting + two pointers for the inner step, total time is O(n²). Using a hash map for the inner step also gives O(n²) but with more overhead. O(n²) is the best known for Three Sum.

Can I solve Two Sum with O(1) space?

Only if the array is sorted (or you sort it first). Sort + two pointers gives O(1) extra space. But sorting costs O(n log n) time and loses original indices. If the problem requires returning original indices (which it does in LC 1), O(n) space with a hash map is unavoidable.

What is the LeetCode problem number?

LeetCode 1 — Two Sum. The very first problem on LeetCode and arguably the most important for interviews. Related variants: LC 167 (Two Sum II — sorted), LC 170 (Two Sum III — data structure design), LC 560 (Subarray Sum Equals K — prefix sum + hash map), and LC 15 (Three Sum).

Watch the hash map build and the complement fire

Paste your Two Sum problem into LearnBug and see every map insertion and lookup step by step.

Open Playground →

Related topics

Two Pointer — sorted array approach to Two Sum →Frequency Counter — hash map for counting →Subarray Sum Equals K — prefix + hash map →Two Sum Interview — all variants explained →