Topic: Learning notes

LeetCode 1: Two Sum in TypeScript with a Map

Replace nested pair checks with a Map of earlier values and indices, then explain complement lookup, the loop invariant, and expected O(n) time.

A nested loop compares each number with the later elements again. A Map keeps earlier values and their indices, so each current value only needs one lookup for its complement.

Problem

Original problem: LeetCode 1: Two Sum

Given an integer array nums and an integer target, return two distinct indices whose values add up to target. The problem guarantees exactly one answer, and the order of the indices does not matter.

Brute force repeats pair checks

function twoSumBruteForce(nums: number[], target: number): number[] {
  for (let left = 0; left < nums.length; left += 1) {
    for (let right = left + 1; right < nums.length; right += 1) {
      if (nums[left] + nums[right] === target) {
        return [left, right];
      }
    }
  }

  throw new Error("No pair sums to target");
}

This version enumerates every pair of distinct indices and compares its sum with target. In the worst case, it checks about n(n - 1) / 2 pairs. Its time complexity is O(n²) and its auxiliary space is O(1).

Look up the complement with a Map

function twoSum(nums: number[], target: number): number[] {
  const indexByValue = new Map<number, number>();

  for (let index = 0; index < nums.length; index += 1) {
    const complementIndex = indexByValue.get(target - nums[index]);

    if (complementIndex !== undefined) {
      return [complementIndex, index];
    }

    indexByValue.set(nums[index], index);
  }

  throw new Error("No pair sums to target");
}

The Map uses each earlier number as a key and its index as the value. For nums[index], first look up target - nums[index]. A match gives the answer. Otherwise, store the current number and continue.

Looking up before inserting prevents one element from being used twice. get() returns undefined for a missing key, so the condition must use !== undefined, not if (complementIndex). Index 0 is a valid answer and is falsy in JavaScript.

Why the scan is correct

Before each iteration at index, indexByValue contains exactly the elements at indices smaller than index, together with their indices.

If the complement exists, its index is earlier than the current one, so the two indices differ and their values sum to target. If it does not exist, no earlier element can pair with the current value. Storing the current value cannot lose an answer.

Every valid answer has an earlier and a later index. When the scan reaches the later index, the earlier value is already in the Map, so the algorithm returns that pair.

Complexity

The brute-force solution takes O(n²) time and O(1) auxiliary space. Under the average hash-lookup model used in interviews, the Map solution uses expected O(1) work for each get() and set(), so its total time is expected O(n). The Map can store up to n values and indices, so its auxiliary space is O(n).

The JavaScript specification requires average Map access to be sublinear, but it does not require one fixed internal implementation. In an interview, say expected O(n), not O(1) space. MDN’s Map reference describes that average sublinear requirement.

Minimal verification

import assert from "node:assert/strict";

assert.deepStrictEqual(twoSum([2, 7, 11, 15], 9), [0, 1]);
assert.deepStrictEqual(twoSum([3, 2, 4], 6), [1, 2]);
assert.deepStrictEqual(twoSum([3, 3], 6), [0, 1]);

assert.deepStrictEqual() checks the array contents directly. That is more reliable than listing expected output without executing it. The Node.js assert documentation explains deep strict comparisons.

Common mistakes

• Inserting the current value before looking it up can allow the same index to form a pair with itself.
• Using if (map.get(complement)) treats a valid index of 0 as missing.
• Calling the Map storage cost O(1). Faster lookup needs up to O(n) extra space.
• Sorting first and using two pointers loses the original indices. Preserving them is possible, but adds work that the Map solution does not need.

Transferable idea

When a problem asks whether the current value can form a condition with earlier data, rewrite that condition as a value to look up. This problem looks up a complement. Other problems may look up a seen value, a count, or a group key. A Map value does not have to be an index. It can hold a count, the earliest position, or other data needed later.

References

• LeetCode 1: Two Sum: original problem, examples, and constraints.
• MDN: Map: key-value semantics, get(), set(), and the average access requirement.
• ECMAScript: Map Objects: the JavaScript specification for Map.
• Node.js: assert.deepStrictEqual(): deep strict comparison for arrays.