Find the bug · Easy

Fix the Two Sum Hash Map

Easy Find the bug Most askedSeen at Amazon, Google, Meta

twoSum(nums, target) should return the indices [i, j] (i < j) of the two different elements that add up to target. Exactly one answer exists.

This one-pass hash-map version is the right idea, but it returns wrong answers for some inputs. Find the bug and fix it.

Example 1

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Example 2

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: The buggy version returns [0, 0].

The buggy code

function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    seen.set(nums[i], i);
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
  }
  return [];
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    seen.set(nums[i], i);
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
  }
  return [];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index
    for i, x in enumerate(nums):
        seen[x] = i
        if target - x in seen:
            return [seen[target - x], i]
    return []

<?php

function twoSum(array $nums, int $target): array
{
    $seen = []; // value => index
    foreach ($nums as $i => $x) {
        $seen[$x] = $i;
        if (isset($seen[$target - $x])) {
            return [$seen[$target - $x], $i];
        }
    }
    return [];
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < nums.length; i++) {
            seen.put(nums[i], i);
            Integer j = seen.get(target - nums[i]);
            if (j != null) return new int[]{j, i};
        }
        return new int[0];
    }
}

Hints

Hint 1

Trace [3, 2, 4], target 6, step by step.

Hint 2

When you look up the partner, which elements should already be in the map?

Find and fix the bug

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the bug and the fix

Time O(n) · Space O(n)

The bug: the current number is inserted into the map before its partner is looked up. When target - x == x (for example 3 + 3 = 6), the lookup finds the element itself and returns [i, i]. With duplicates, the insert also overwrites the earlier index.

The fix: look up target - nums[i] first; only if it is missing, store nums[i]. The map then only ever contains elements before i, so an element can never pair with itself.

Fixed version

function twoSum(nums, target) {
  const seen = new Map(); // value -> index, only for elements before i
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return [];
}

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value -> index, only for elements before i
  for (let i = 0; i < nums.length; i++) {
    const j = seen.get(target - nums[i]);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return [];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index, only for elements before i
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

<?php

function twoSum(array $nums, int $target): array
{
    $seen = []; // value => index, only for elements before $i
    foreach ($nums as $i => $x) {
        if (isset($seen[$target - $x])) {
            return [$seen[$target - $x], $i];
        }
        $seen[$x] = $i;
    }
    return [];
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index, only for elements before i
        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]);
            if (j != null) return new int[]{j, i};
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

Common mistakes

Patching it with if (j !== i): works here, but the overwrite problem with duplicates remains.

Fix the Binary Search · Easy
Fix the Longest Substring Without Repeats · Medium
Fix Merge Intervals · Medium
Fix the Mutable Default Argument · Easy
Fix the Substring Check · Easy
Fix the Median (JavaScript Sort) · Easy