LeetCode patterns: the 18 coding interview patterns, with templates

def pair_with_sum(nums, target):
    seen = {}  # value -> index where we saw it
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

function pairWithSum(nums, target) {
  const seen = new Map(); // value -> index where we saw it
  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 [];
}

from collections import defaultdict

def group_by_letters(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word))  # same letters, same key
        groups[key].append(word)
    return list(groups.values())

function groupByLetters(words) {
  const groups = new Map();
  for (const word of words) {
    const key = [...word].sort().join(""); // same letters, same key
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

def max_sum_of_k(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]  # add the new value, drop the oldest
        best = max(best, window)
    return best

function maxSumOfK(nums, k) {
  if (k <= 0 || k > nums.length) return null;
  let window = 0;
  for (let i = 0; i < k; i++) window += nums[i];
  let best = window;
  for (let right = k; right < nums.length; right++) {
    window += nums[right] - nums[right - k]; // add the new value, drop the oldest
    best = Math.max(best, window);
  }
  return best;
}

def longest_unique_run(s):
    counts = {}
    left = best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while counts[ch] > 1:      # the window broke the rule: shrink it
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

function longestUniqueRun(s) {
  const counts = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    counts.set(ch, (counts.get(ch) || 0) + 1);
    while (counts.get(ch) > 1) { // the window broke the rule: shrink it
      counts.set(s[left], counts.get(s[left]) - 1);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

def shortest_run_at_least(nums, target):
    # Works because every value is non-negative: growing the window never lowers the sum.
    left = total = 0
    best = float("inf")
    for right, num in enumerate(nums):
        total += num
        while total >= target:     # valid: record it, then try to shrink
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

function shortestRunAtLeast(nums, target) {
  // Works because every value is non-negative: growing the window never lowers the sum.
  let left = 0;
  let total = 0;
  let best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    total += nums[right];
    while (total >= target) { // valid: record it, then try to shrink
      best = Math.min(best, right - left + 1);
      total -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

def lower_bound(nums, target):
    lo, hi = 0, len(nums)  # search the half-open range [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # len(nums) if every value is smaller than target

function lowerBound(nums, target) {
  let lo = 0;
  let hi = nums.length; // search the half-open range [lo, hi)
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // nums.length if every value is smaller than target
}

def smallest_feasible(lo, hi, feasible):
    # feasible(x) must be False, False, ..., True, True on [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def min_speed(piles, hours):
    def finishes(speed):
        return sum((p + speed - 1) // speed for p in piles) <= hours  # ceiling division
    return smallest_feasible(1, max(piles), finishes)

function smallestFeasible(lo, hi, feasible) {
  // feasible(x) must be false, false, ..., true, true on [lo, hi]
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function minSpeed(piles, hours) {
  const finishes = (speed) =>
    piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0) <= hours;
  return smallestFeasible(1, Math.max(...piles), finishes);
}

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):  # depth-first
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def level_order(root):  # breadth-first, one level at a time
    levels = []
    queue = deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxDepth(root) { // depth-first
  if (root === null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

function levelOrder(root) { // breadth-first, one level at a time
  const levels = [];
  let queue = root ? [root] : [];
  while (queue.length) {
    levels.push(queue.map((node) => node.val));
    const next = [];
    for (const node of queue) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    queue = next;
  }
  return levels;
}

def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if root is None:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val)
            and is_valid_bst(root.right, root.val, high))

function isValidBst(root, low = -Infinity, high = Infinity) {
  if (root === null) return true;
  if (!(low < root.val && root.val < high)) return false;
  return isValidBst(root.left, low, root.val) && isValidBst(root.right, root.val, high);
}

import heapq

def k_largest(nums, k):
    heap = []  # min-heap holding the k largest values seen so far
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # drop the smallest
    return sorted(heap, reverse=True)

// JavaScript has no built-in heap, so interviews expect a small one like this.
class MinHeap {
  constructor(less = (a, b) => a < b) {
    this.items = [];
    this.less = less;
  }

  size() {
    return this.items.length;
  }

  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!this.less(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

function kLargest(nums, k) {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) heap.pop(); // drop the smallest
  }
  return heap.items.sort((a, b) => b - a);
}

from collections import deque

def count_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or (r, c) in seen:
                continue
            islands += 1
            seen.add((r, c))
            queue = deque([(r, c)])
            while queue:
                cr, cc = queue.popleft()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if (0 <= nr < rows and 0 <= nc < cols
                            and grid[nr][nc] == "1" and (nr, nc) not in seen):
                        seen.add((nr, nc))  # mark when you enqueue, not when you pop
                        queue.append((nr, nc))
    return islands

function countIslands(grid) {
  if (grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== "1" || seen[r][c]) continue;
      islands++;
      seen[r][c] = true;
      const queue = [[r, c]];
      for (let head = 0; head < queue.length; head++) {
        const [cr, cc] = queue[head];
        for (const [dr, dc] of moves) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === "1" && !seen[nr][nc]) {
            seen[nr][nc] = true; // mark when you enqueue, not when you pop
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return islands;
}

from collections import deque

def topo_order(n, edges):
    # edges: (a, b) means a must come before b
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in edges:
        graph[a].append(b)
        indegree[b] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == n else []  # [] means there is a cycle

function topoOrder(n, edges) {
  // edges: [a, b] means a must come before b
  const graph = Array.from({ length: n }, () => []);
  const indegree = new Array(n).fill(0);
  for (const [a, b] of edges) {
    graph[a].push(b);
    indegree[b]++;
  }
  const queue = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);
  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    order.push(node);
    for (const next of graph[node]) {
      indegree[next]--;
      if (indegree[next] === 0) queue.push(next);
    }
  }
  return order.length === n ? order : []; // [] means there is a cycle
}

from functools import lru_cache

def count_ways(n, steps=(1, 2)):
    @lru_cache(maxsize=None)
    def ways(i):  # number of ways to reach step i
        if i == 0:
            return 1
        return sum(ways(i - s) for s in steps if s <= i)
    return ways(n)

function countWays(n, steps = [1, 2]) {
  const memo = new Map();
  const ways = (i) => { // number of ways to reach step i
    if (i === 0) return 1;
    if (memo.has(i)) return memo.get(i);
    let total = 0;
    for (const s of steps) if (s <= i) total += ways(i - s);
    memo.set(i, total);
    return total;
  };
  return ways(n);
}

def fewest_coins(coins, amount):
    impossible = amount + 1
    dp = [0] + [impossible] * amount  # dp[a] = fewest coins that make a
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != impossible else -1

function fewestCoins(coins, amount) {
  const impossible = amount + 1;
  const dp = new Array(amount + 1).fill(impossible); // dp[a] = fewest coins that make a
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === impossible ? -1 : dp[amount];
}

def max_non_adjacent_sum(values):
    take, skip = 0, 0  # best total if the previous item was taken / skipped
    for v in values:
        take, skip = skip + v, max(take, skip)
    return max(take, skip)

function maxNonAdjacentSum(values) {
  let take = 0; // best total if the previous item was taken
  let skip = 0; // best total if it was skipped
  for (const v of values) {
    [take, skip] = [skip + v, Math.max(take, skip)];
  }
  return Math.max(take, skip);
}

def max_subarray_sum(nums):
    best = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)  # extend the run or start over here
        best = max(best, current)
    return best

def can_reach_end(jumps):
    farthest = 0
    for i, jump in enumerate(jumps):
        if i > farthest:
            return False  # stuck before index i
        farthest = max(farthest, i + jump)
    return True

function maxSubarraySum(nums) {
  let best = nums[0];
  let current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]); // extend the run or start over here
    best = Math.max(best, current);
  }
  return best;
}

function canReachEnd(jumps) {
  let farthest = 0;
  for (let i = 0; i < jumps.length; i++) {
    if (i > farthest) return false; // stuck before index i
    farthest = Math.max(farthest, i + jumps[i]);
  }
  return true;
}

def rotate_clockwise(matrix):
    n = len(matrix)
    for i in range(n):              # 1) transpose across the main diagonal
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:              # 2) reverse each row
        row.reverse()

def fast_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:      # this bit of n is set
            result *= x
        x *= x         # square for the next bit
        n >>= 1
    return result

function rotateClockwise(matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) { // 1) transpose across the main diagonal
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (const row of matrix) row.reverse(); // 2) reverse each row
}

function fastPow(x, n) {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }
  let result = 1;
  while (n > 0) {
    if (n % 2 === 1) result *= x; // this bit of n is set
    x *= x; // square for the next bit
    n = Math.floor(n / 2); // not n >> 1, which breaks past 32 bits
  }
  return result;
}