Examples

// ===== 1. Two-sum (hash map) =====
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);
  }
  return [];
}
// O(n)

// ===== 2. Container with most water (two pointers) =====
function maxArea(heights) {
  let l = 0, r = heights.length - 1, best = 0;
  while (l < r) {
    const h = Math.min(heights[l], heights[r]);
    best = Math.max(best, h * (r - l));
    if (heights[l] < heights[r]) l++; else r--;
  }
  return best;
}
// O(n)

// ===== 3. Longest substring without repeating chars (sliding window) =====
function longestUnique(s) {
  const last = new Map();
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    if (last.has(s[i]) && last.get(s[i]) >= start) start = last.get(s[i]) + 1;
    last.set(s[i], i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}
// O(n)

// ===== 4. Climbing stairs (DP, 1D) =====
function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}
// O(n) time, O(1) space

// ===== 5. Edit distance (DP, 2D) =====
function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1]
        : 1 + Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}
// O(m*n)

// ===== 6. BFS shortest path in grid =====
function shortestPath(grid, start, end) {
  const [rows, cols] = [grid.length, grid[0].length];
  const visited = new Set();
  const queue = [[start, 0]];
  while (queue.length) {
    const [[r, c], d] = queue.shift();
    if (r === end[0] && c === end[1]) return d;
    const key = r + ',' + c;
    if (visited.has(key)) continue;
    visited.add(key);
    for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] !== 1) {
        queue.push([[nr, nc], d + 1]);
      }
    }
  }
  return -1;
}
// O(rows * cols)

// ===== 7. K-th largest element (heap) =====
class MinHeap {
  constructor() { this.h = []; }
  push(x) { this.h.push(x); this.up(this.h.length - 1); }
  pop() {
    if (!this.h.length) return undefined;
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this.down(0); }
    return top;
  }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
  up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p;
    }
  }
  down(i) {
    const n = this.h.length;
    for (;;) {
      const l = i*2+1, r = i*2+2;
      let m = i;
      if (l < n && this.h[l] < this.h[m]) m = l;
      if (r < n && this.h[r] < this.h[m]) m = r;
      if (m === i) break;
      [this.h[m], this.h[i]] = [this.h[i], this.h[m]]; i = m;
    }
  }
}

function kthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}
// O(n log k)

// ===== Patterns to internalise =====
// - Hash map for any 'have I seen this' lookup -> linear time
// - Two pointers for sorted arrays / linear scans
// - Sliding window for substring / contiguous subarray problems
// - DP for overlapping subproblems
// - BFS for shortest path in unweighted graphs
// - Min-heap of size k for top-k

// ===== Pitfalls =====
// - DP table off-by-one (dp[m][n], indices [i-1][j-1])
// - BFS queue.shift() is O(n) in JS; consider a deque
// - Heap inversion: min-heap for largest, max-heap for smallest top-k
// - Hash map without tracking position vs value for duplicates

// Each lesson body has 2-3 hand-traced patterns end-to-end.