DSA Tracker

Visualize

Two Sum

One-pass hashmap lookup

time O(n)space O(n)

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.

Details

Animated on: Find two indices in [11, 3, 15, 2, 7, 5] whose values add up to 9.

Problem:Two SumEasy

Pattern:Hashing and Frequency Maps

One-pass hashmap lookup

step 1 / 11

11
[0]
3
[1]
15
[2]
2
[3]
7
[4]
5
[5]

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.

  • i=0· arr[0] = 11
Pseudocode
1FUNCTION twoSum(nums, target):
2  make an empty lookup table that maps a value → its index
3  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 table
7  END FOR
8END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 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.
  2. nums[0] = 11 needs need = 9 − 11 = −2 as its partner. seen = {} holds nothing, so no −2 — miss.
  3. File 11 away so a future element can find it: seen = {11:0}. Storing AFTER checking also means an element can never pair with itself.
  4. nums[1] = 3 needs 9 − 3 = 6. seen = {11:0} has no 6 — miss. Note we never re-scan the array; the map answers in O(1).
  5. Store it: seen = {11:0, 3:1}. If a 6 shows up later, it will find this 3 instantly.
  6. nums[2] = 15 needs 9 − 15 = −6. seen = {11:0, 3:1} has no −6 — miss. Negative needs are fine; the map just won't contain them here.
  7. Store it: seen = {11:0, 3:1, 15:2}. Three checked, none paired yet — but each took only O(1) work.
  8. nums[3] = 2 needs 9 − 2 = 7. seen = {11:0, 3:1, 15:2} has no 7 — miss. (The 7 exists in the array, but at index 4 — we haven't reached it, and that's exactly why we store as we go.)
  9. Store it: seen = {11:0, 3:1, 15:2, 2:3}. This entry is about to matter.
  10. nums[4] = 7 needs 9 − 7 = 2. seen = {11:0, 3:1, 15:2, 2:3} HAS 2, stored at index 3 — hit! The map hands us the partner's index with zero searching.
  11. Answer: return [3, 4] — nums[3] + nums[4] = 2 + 7 = 9. One pass, each element checked once against the map: O(n) time, O(n) space for seen.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Two Sum in the editorAll Arrays problemsBack to roadmap