K AVAILABLE
OPEN TO WORK
← BACK TO KNOWLEDGE

KNOWLEDGE

Two Sum: One-Pass Hash Table Pattern

How to convert an O(n²) pairwise search into an O(n) linear scan by dynamically storing previously visited complements in a hash map.

Updated Sep 4, 20265 min readFoundationalData Structures & Algorithms

INTERACTIVE ALGORITHM WORKBENCH

Two Sum Visualizer

EasyArrays & Hash TableTime O(n)Space O(n)
Array
Index0123
Value271115
Hash Map (value → index)
ValueIndex
  
  
  
  

We've seen 0 numbers so far.

Target9
Current2 (index 0)
Complement7
Lookup StatusReady
solution.py
1def two_sum(nums, target):
▶2    seen = {}
3    for i, num in enumerate(nums):
4        complement = target - num
5        if complement in seen:
6            return [seen[complement], i]
7        seen[num] = i
8    return []
Step 1 of 4
WHY THIS STEP WORKS

Initialize an empty hash map (seen = {}). As we iterate through the array, we check if the complement already exists before storing the current number.

  1. 1Target sum is 9
  2. 2Initialize seen = {}
  3. 3Begin array iteration at index 0