Two Sum and “Seen Before?”

Trade memory for speed

Part 5 is about one idea that solves many problems: as you walk through the input, remember what you have seen in a Map or a Set. A Map is a collection of key → value pairs, like a phone book that finds a number from a name. A Set is a collection of unique values that can tell you quickly whether a value is inside, like a guest list. Both find an item in O(1) time, which means the time does not grow when the collection gets bigger.

Now a question that would need an inner loop, such as “is there an earlier value that…?”, becomes one O(1) lookup. You pay O(n) extra memory, and in return O(n²) time becomes O(n) time.

Two Sum, three ways

The task: find the two values in an unsorted array that add up to a target, and return their indices (positions). It is the most famous interview question. It shows three levels of solution clearly. The first is the brute force, which means trying every possibility without being clever:

function twoSumBrute(nums, target) {  for (let i = 0; i < nums.length; i++)    for (let j = i + 1; j < nums.length; j++)      if (nums[i] + nums[j] === target) return [i, j];}function twoSumSorted(nums, target) {  // Sort indices by value so the original positions are not lost  const idx = nums.map((_, i) => i).sort((a, b) => nums[a] - nums[b]);  let l = 0, r = idx.length - 1;  while (l < r) {    const sum = nums[idx[l]] + nums[idx[r]];    if (sum === target) return [idx[l], idx[r]].sort((a, b) => a - b);    if (sum < target) l++;    else r--;  }}console.log(twoSumBrute([3, 8, 4, 5], 9));  // [ 2, 3 ]console.log(twoSumSorted([3, 8, 4, 5], 9)); // [ 2, 3 ]

Traced: Two Sum with a Map

For each value x, the partner it needs is target − x. Do not search the whole array for the partner. Look it up in the Map of values you have already passed:

1const nums = [3, 8, 4, 5], target = 9;▶const seen = new Map();3for (let i = 0; i < nums.length; i++) {4  const need = target - nums[i];5  if (seen.has(need)) {6    console.log([seen.get(need), i]);7    break;8  }9  seen.set(nums[i], i);10}

Check first, then store

The order of the two lines inside the loop matters. If you check before you store, a value can never pair with itself. Take nums = [3, 5] and target 6. If you stored first, the Map would already contain 3 when you look for the partner of 3, and you would wrongly return [0, 0]. With [3, 3], checking first still works: the second 3 finds the first 3.

for (let i = 0; i < nums.length; i++) {
  if (seen has what nums[i] needs) → answer
  record nums[i] in seen
}

What should the Map remember?

The key is usually the value from the array. What you store with it depends on what the question asks for:

Duplicates within distance k

The task: is there a value that repeats within k positions? Store each value's most recent index. An older copy is never closer than the latest copy, so overwriting the old index loses nothing.

function containsNearbyDuplicate(nums, k) {  const last = new Map();                        // value → most recent index  for (let i = 0; i < nums.length; i++) {    if (last.has(nums[i]) && i - last.get(nums[i]) <= k) return true;    last.set(nums[i], i);                        // overwrite: only the latest index matters  }  return false;}console.log(containsNearbyDuplicate([1, 2, 3, 1], 3));       // trueconsole.log(containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2)); // false

Longest consecutive sequence

The task: find the longest run of consecutive integers (numbers that follow each other, like 1, 2, 3, 4). The numbers can be in any order in the array. For example, [100, 4, 200, 1, 3, 2] contains 1, 2, 3, 4, so the answer is 4. Sorting takes O(n log n) time. A Set takes O(n) time with one clever rule: only start counting from a value x when x − 1 is not in the Set. That means x is the start of a run.

function longestConsecutive(nums) {  const set = new Set(nums);  let best = 0;  for (const x of set) {    if (set.has(x - 1)) continue;          // not the start of a run: skip    let len = 1;    while (set.has(x + len)) len++;        // walk up the run: x, x+1, x+2 …    best = Math.max(best, len);  }  return best;}console.log(longestConsecutive([100, 4, 200, 1, 3, 2]));        // 4   (1, 2, 3, 4)console.log(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])); // 9

Without that rule, counting from every value would take O(n²) time on an input like 1, 2, 3 … n. With the rule, the inner while loop visits each value only once, from the run it belongs to. So the total work is O(n).

Counting subarrays with a Map

A subarray is a block of neighbouring items inside an array. A prefix sum is the total of all items from the start up to the current position. Lesson 20 counted subarrays with sum k by storing counts of prefix sums. The same “seen before” idea works for any running total. For “subarrays with exactly k odd numbers”, the running total is the number of odd values so far:

// Count subarrays with exactly k odd numbers: prefix counts of odd numbersfunction numberOfSubarrays(nums, k) {  const seen = new Map([[0, 1]]);  let odds = 0, count = 0;  for (const x of nums) {    if (x % 2 === 1) odds++;    count += seen.get(odds - k) ?? 0;    seen.set(odds, (seen.get(odds) ?? 0) + 1);  }  return count;}console.log(numberOfSubarrays([1, 1, 2, 1, 1], 3)); // 2

The pattern is always the same. Keep a running value. Ask how many earlier running values would make the current subarray valid. Then record the current running value.

Practice questions

Before you write code for each question, say what the key is and what value the Map stores with it.

function twoSum(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);  }}console.log(twoSum([2, 7, 11, 15], 9)); // [ 0, 1 ]console.log(twoSum([3, 2, 4], 6));      // [ 1, 2 ]console.log(twoSum([3, 3], 6));         // [ 0, 1 ]

function containsNearbyDuplicate(nums, k) {  const last = new Map();  for (let i = 0; i < nums.length; i++) {    if (i - (last.get(nums[i]) ?? -Infinity) <= k) return true;    last.set(nums[i], i);  }  return false;}console.log(containsNearbyDuplicate([1, 0, 1, 1], 1));       // trueconsole.log(containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2)); // false

function longestConsecutive(nums) {  if (nums.length === 0) return 0;  const a = [...nums].sort((x, y) => x - y);  let best = 1, run = 1;  for (let i = 1; i < a.length; i++) {    if (a[i] === a[i - 1]) continue;    run = a[i] === a[i - 1] + 1 ? run + 1 : 1;    best = Math.max(best, run);  }  return best;}console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // 4

function longestConsecutive(nums) {  const set = new Set(nums);  let best = 0;  for (const x of set) {    if (set.has(x - 1)) continue;    let len = 1;    while (set.has(x + len)) len++;    best = Math.max(best, len);  }  return best;}console.log(longestConsecutive([100, 4, 200, 1, 3, 2]));         // 4console.log(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])); // 9console.log(longestConsecutive([]));                             // 0

function maxOperations(nums, k) {  const waiting = new Map();  let pairs = 0;  for (const x of nums) {    const need = k - x;    if ((waiting.get(need) ?? 0) > 0) {      waiting.set(need, waiting.get(need) - 1);      pairs++;    } else {      waiting.set(x, (waiting.get(x) ?? 0) + 1);    }  }  return pairs;}console.log(maxOperations([1, 2, 3, 4], 5));    // 2console.log(maxOperations([3, 1, 3, 4, 3], 6)); // 1

function maxOperations(nums, k) {  const a = [...nums].sort((x, y) => x - y);  let l = 0, r = a.length - 1, pairs = 0;  while (l < r) {    const s = a[l] + a[r];    if (s === k) { pairs++; l++; r--; }    else if (s < k) l++;    else r--;  }  return pairs;}console.log(maxOperations([1, 2, 3, 4], 5)); // 2

function checkSubarraySum(nums, k) {  const first = new Map([[0, -1]]);       // remainder 0 "seen" before index 0  let sum = 0;  for (let i = 0; i < nums.length; i++) {    sum = (sum + nums[i]) % k;    if (first.has(sum)) {      if (i - first.get(sum) >= 2) return true;    } else {      first.set(sum, i);    }  }  return false;}console.log(checkSubarraySum([23, 2, 4, 6, 7], 6));  // trueconsole.log(checkSubarraySum([23, 2, 6, 4, 7], 13)); // falseconsole.log(checkSubarraySum([5, 0, 0], 3));         // true

function numberOfSubarrays(nums, k) {  const seen = new Map([[0, 1]]);  let odds = 0, count = 0;  for (const x of nums) {    odds += x % 2;    count += seen.get(odds - k) ?? 0;    seen.set(odds, (seen.get(odds) ?? 0) + 1);  }  return count;}console.log(numberOfSubarrays([1, 1, 2, 1, 1], 3)); // 2console.log(numberOfSubarrays([2, 4, 6], 1));       // 0

Make it stick

What's next

Lesson 27 uses Maps to group things: anagrams (words made from the same letters) that share a key, the top k most frequent values, and the majority element. It also shows a clever voting algorithm that uses O(1) extra space.