Pattern visualizer
Two Sum
The array is unsorted, so two pointers can't help. Instead, walk it ONCE keeping a hashmap of every value already seen (value → index). At each element, one O(1) question — 'have I already seen my complement, target − current?' — either finishes the problem or files the current value away for someone later. Animated on: Find two indices in [11, 3, 15, 2, 7, 5] whose values add up to 9..
One-pass hashmap lookup
time O(n)space O(n)step 1 / 11
11
[0]3
[1]15
[2]2
[3]7
[4]5
[5]line 2
Target 9, seen = {} (empty). We'll scan left to right; every element gets one chance to find a partner among values ALREADY passed — that's why one pass is enough.
Pseudocode
1FUNCTION twoSum(nums, target):2 make an empty lookup table that maps a value → its index3 FOR each position i in nums:4 need = target - nums[i]5 IF need is already in the table: RETURN [the index stored for need, i]6 store nums[i] → i in the table7 END FOR8END FUNCTION
← / → step · space play · Home restart