Arrays and Iteration

Two-Sum with Hash Lookup

Walk the array once, storing seen values in a lookup table. When the complement is already present, the result indices are known.

Algorithm

execution replay The checked-in replay follows the language-neutral state table for `array-two-sum-hash`.
cross-language comparison This TypeScript DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.ts
Replay: real traced execution (multi-file project)
const arr: number[] = [2, 7, 11, 4, 5];
const target: number = 9;
const seen = new Map<number, number>();
let result: number[] | null = null;
for (let i = 0; i < arr.length; i++) {
  const need = target - arr[i];
  if (seen.has(need)) {
    result = [seen.get(need), i];
    break;
  }
  seen.set(arr[i], i);
}
console.log(`[${result[0]}, ${result[1]}]`);

  1. arr ← [2, 7, 11, 4, 5], target ← 9, seen ← {}

    1const arr: number[] = [2, 7, 11, 4, 5];2const target: number = 9;
    values this step[2, 7, 11, 4, 5]arr9target{}seen

  2. seen ← {2: 0}, hit ← no

    5for (let i = 0; i < arr.length; i++) {6  const need = target - arr[i];7  if (seen.has(need)) {
    values this step{} → {2: 0}seennohit0i2arr[i]7need

  3. hit ← yes, result ← [0, 1]

    5for (let i = 0; i < arr.length; i++) {6  const need = target - arr[i];7  if (seen.has(need)) {
    values this stepyeshit[0, 1]result1i7arr[i]2need{2: 0}seen

Complexity

  • Time: O(n) average
  • Space: O(n)

Implementation notes

  • TypeScript declares arr as number[], target as number, and result as number[] | null. The values are finite JavaScript Number values checked through TypeScript's number type.
  • The lookup table is new Map<number, number>(), storing each seen array value as the key and its 0-based index as the value.
  • Each loop computes const need = target - arr[i] before inserting the current value, so a complement is only found among earlier indices.
  • The replay shows the miss state at i=0: need is 7, seen is {}, and seen.set(2, 0) records {2: 0}. At i=1, need is 2, seen.has(2) hits, and result becomes [0, 1].
  • console.log(\[${result[0]}, ${result[1]}]`)prints[0, 1]for this guaranteed-hit input. Visible allocation is the input array, theMap, the two-element result array, and the output string; mutation is limited to seen.set(...)and rebindingresult`.