Skip to content
Hash map: count and look up

Lesson 4.4

Two sum with a map

7 min · 8 steps

  1. Step 1 of 8 · Explanation

    Problem: "Return the indexes of two numbers that add up to target." Brute force checks every pair, O(n²).

    With a map, flip the question. For each number x, its partner has to be target - x. Ask the map: "have I seen target - x?" If not, store x with its index and move on. One pass, O(n).

  2. Step 2 of 8 · Predict the result

    What does it return for [3, 2, 4] and target 6?

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i]    if (seen.has(need)) {      return [seen.get(need), i]    }    seen.set(nums[i], i)  }}
    1. [1, 2]
    2. [0, 0]
    3. [2, 1]

  3. Step 3 of 8 · Predict the result

    What does it return for [3, 3] and target 6?

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i]    if (seen.has(need)) {      return [seen.get(need), i]    }    seen.set(nums[i], i)  }}
    1. [0, 1]
    2. [1, 1]
    3. [0, 0]

  4. Step 4 of 8 · Find the bug

    This code looks for the indexes of two numbers that add up to target. For [3, 2, 4] and target 6, it returns [0, 0], but it should be [1, 2]. Tap the line that's in the wrong place.

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    seen.set(nums[i], i)    const need = target - nums[i]    if (seen.has(need)) return [seen.get(need), i]  }}

  5. Step 5 of 8 · Trace the code

    Fill in i and need at the marked steps, for [1, 5, 3, 7] and target 10.

    function solution(nums, target) {  const seen = new Map()  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i]    if (seen.has(need)) {      return [seen.get(need), i]    }    seen.set(nums[i], i)  }}

    solution([1, 5, 3, 7], 10)

  6. Step 6 of 8 · Pick the approach

    "Return the indexes of two numbers in nums that add up to target." Constraints: 2 ≤ nums.length ≤ 10⁵, exactly one answer, return the original indexes.
    Which approach is right?

    1. A Map from number to index, in one pass
    2. Every pair with two loops
    3. A Set of all the numbers
    4. Sort, then search from both ends

  7. Step 7 of 8 · Arrange the code

    A harder version: return how many pairs (i, j) with i < j add up to target. The map holds counts, not indexes. One line doesn't belong.

    counts.set(x, (counts.get(x) || 0) + 1)}}return pairsfor (const x of nums) {pairs += counts.get(target - x) || 0function solution(nums, target) {let pairs = 0pairs += counts.has(target - x) ? 1 : 0const counts = new Map()

  8. Step 8 of 8 · Recap

    • Flip the question: for each x, look for a target - x you've already passed.
    • Check first, then store. That stops a number from pairing with itself.
    • Store what the answer needs. Indexes for "where", counts for "how many".

    Pattern card

    Look up the partner in a map
    When to use it: When a problem looks for two items that match (a sum, a difference, a pair) and O(n²) brute force is too slow.
    const seen = new Map()for (let i = 0; i < nums.length; i++) {  const need = target - nums[i]  if (seen.has(need)) return [seen.get(need), i]  seen.set(nums[i], i)}