Data Structures & Algorithms#

# Python gives you a lot for free.
from collections import deque, defaultdict, Counter
import heapq

stack = []                      # list works as a stack
queue = deque()                 # O(1) pops from both ends
heap = []                       # heapq turns a list into a min-heap
lookup = {}                     # hash map
seen = set()                    # hash set
graph = defaultdict(list)       # adjacency list that self-initialises
freq = Counter("mississippi")   # {'i': 4, 's': 4, 'p': 2, 'm': 1}

// JavaScript gives you less, so you build a little more.
const stack = [];               // push / pop
const queue = [];               // shift() is O(n) - use an index or a ring buffer
const heap = new MinHeap();     // not built in; we write one in section 19
const lookup = new Map();       // insertion-ordered hash map, any key type
const seen = new Set();
const graph = new Map();        // Map<node, node[]>
const freq = new Map();
for (const ch of "mississippi") freq.set(ch, (freq.get(ch) ?? 0) + 1);

def example(nums):                      # n = len(nums)
    total = 0                           # O(1)

    for x in nums:                      # O(n)
        total += x

    for i in range(len(nums)):          # O(n) outer
        for j in range(len(nums)):      # O(n) inner  -> O(n^2) together
            if nums[i] + nums[j] == 10:
                total += 1

    i = len(nums)
    while i > 1:                        # halves each time -> O(log n)
        i //= 2

    return total                        # O(n) + O(n^2) + O(log n) = O(n^2)


def sum_pairs_once(nums):               # the classic O(n^2) -> O(n) rewrite
    seen, count = set(), 0
    for x in nums:                      # single pass, O(n) time
        count += (10 - x) in seen       # set membership is O(1) average
        seen.add(x)
    return count                        # O(n) time, O(n) extra space

function example(nums) {                  // n = nums.length
  let total = 0;                          // O(1)

  for (const x of nums) total += x;       // O(n)

  for (let i = 0; i < nums.length; i++) { // O(n) outer
    for (let j = 0; j < nums.length; j++) // O(n) inner -> O(n^2)
      if (nums[i] + nums[j] === 10) total++;
  }

  let i = nums.length;
  while (i > 1) i = Math.floor(i / 2);    // O(log n)

  return total;                           // dominated by O(n^2)
}

function sumPairsOnce(nums) {             // the O(n^2) -> O(n) rewrite
  const seen = new Set();
  let count = 0;
  for (const x of nums) {                 // one pass, O(n)
    if (seen.has(10 - x)) count++;        // Set lookup is O(1) average
    seen.add(x);
  }
  return count;                           // O(n) time, O(n) space
}

import sys

print(sys.getrecursionlimit())      # 1000 by default in CPython

def depth(n=0):
    try:
        return depth(n + 1)
    except RecursionError:
        return n

print(depth())                      # roughly 990-1000

# Python has no tail-call optimisation, so deep recursion must be
# rewritten as a loop with an explicit stack. This is why iterative
# graph traversals are safer on large inputs.

function depth(n = 0) {
  try {
    return depth(n + 1);
  } catch {
    return n;                       // RangeError caught here
  }
}

console.log(depth());               // ~10,000-15,000 depending on engine

// No engine ships tail-call optimisation in practice either, so the same
// advice applies: convert deep recursion into an explicit stack loop.

nums = [10, 20, 30, 40, 50]

nums[2]                 # O(1)  - pure address arithmetic
nums.append(60)         # O(1)* - amortised; may trigger a resize
nums.pop()              # O(1)  - removing from the end shifts nothing

nums.insert(1, 15)      # O(n)  - every later element shifts right
nums.pop(0)             # O(n)  - every later element shifts left
nums.remove(30)         # O(n)  - a search plus a shift
30 in nums              # O(n)  - linear scan; use a set for membership

nums.sort()             # O(n log n) - Timsort, in place, stable
sorted(nums)            # O(n log n) - returns a new list
nums.reverse()          # O(n)
nums[1:4]               # O(k)  - slicing COPIES; not free

# Two-dimensional arrays: build rows independently.
grid = [[0] * 4 for _ in range(3)]      # correct: 3 distinct rows
wrong = [[0] * 4] * 3                   # BUG: three references to ONE row
wrong[0][0] = 9
print(wrong)            # [[9,0,0,0],[9,0,0,0],[9,0,0,0]]

const nums = [10, 20, 30, 40, 50];

nums[2];                  // O(1)
nums.push(60);            // O(1)* amortised
nums.pop();               // O(1)

nums.splice(1, 0, 15);    // O(n) - insert at index 1
nums.shift();             // O(n) - removes the front, re-indexes everything
nums.indexOf(30);         // O(n)
nums.includes(30);        // O(n) - use a Set for membership tests

nums.sort((a, b) => a - b);  // O(n log n); WITHOUT the comparator JS sorts
                             // lexicographically: [1,10,2] not [1,2,10]
nums.slice(1, 4);         // O(k) - copies
nums.reverse();           // O(n) - in place

// Two-dimensional arrays: same aliasing trap as Python.
const grid = Array.from({ length: 3 }, () => new Array(4).fill(0)); // correct
const wrong = new Array(3).fill(new Array(4).fill(0));              // BUG
wrong[0][0] = 9;
console.log(wrong);       // every row shows 9 - they are the same array

def rotate(nums, k):
    """Rotate nums right by k, in place. O(n) time, O(1) space."""
    n = len(nums)
    k %= n                          # rotating by n is a no-op
    if k == 0:
        return

    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo, hi = lo + 1, hi - 1

    reverse(0, n - 1)               # whole array
    reverse(0, k - 1)               # first k
    reverse(k, n - 1)               # the rest


data = [1, 2, 3, 4, 5, 6, 7]
rotate(data, 3)
print(data)                         # [5, 6, 7, 1, 2, 3, 4]

function rotate(nums, k) {
  const n = nums.length;
  k %= n;
  if (k === 0) return;

  const reverse = (lo, hi) => {
    while (lo < hi) {
      [nums[lo], nums[hi]] = [nums[hi], nums[lo]];
      lo++;
      hi--;
    }
  };

  reverse(0, n - 1);   // whole array
  reverse(0, k - 1);   // first k
  reverse(k, n - 1);   // the rest
}

const data = [1, 2, 3, 4, 5, 6, 7];
rotate(data, 3);
console.log(data);     // [5, 6, 7, 1, 2, 3, 4]

# BAD: each += allocates a new string and copies everything so far.
def build_bad(words):
    out = ""
    for w in words:
        out += w            # O(len(out)) each time -> O(n^2) overall
    return out

# GOOD: collect the pieces, join once. O(n) total.
def build_good(words):
    parts = []
    for w in words:
        parts.append(w)     # O(1) amortised
    return "".join(parts)   # one allocation of the final size

# Useful string operations
s = "Hello, World"
s.lower(), s.upper()        # O(n), new strings
s.split(", ")               # ['Hello', 'World']
s.replace("l", "L")         # O(n), new string
s.find("World")             # 7, or -1 if absent
s[::-1]                     # 'dlroW ,olleH' - reverse by slicing
list(s)                     # a mutable list of characters when you must edit

// BAD in principle; engines optimise it with ropes, but do not rely on that.
function buildBad(words) {
  let out = "";
  for (const w of words) out += w;
  return out;
}

// GOOD: explicit and predictably O(n).
function buildGood(words) {
  const parts = [];
  for (const w of words) parts.push(w);
  return parts.join("");
}

const s = "Hello, World";
s.toLowerCase();            // O(n), new string
s.split(", ");              // ['Hello', 'World']
s.replaceAll("l", "L");     // O(n)
s.indexOf("World");         // 7, or -1
[...s].reverse().join("");  // 'dlroW ,olleH' - spread handles surrogate pairs
Array.from(s);              // mutable character array

from collections import Counter

def is_anagram(a: str, b: str) -> bool:
    """O(n) time, O(k) space where k = alphabet size."""
    if len(a) != len(b):
        return False
    return Counter(a) == Counter(b)

# Sorting also works but costs O(n log n):
#   return sorted(a) == sorted(b)

def group_anagrams(words):
    """Group words that are anagrams of each other. O(total chars)."""
    buckets = {}
    for w in words:
        key = tuple(sorted(w))          # canonical form; hashable
        buckets.setdefault(key, []).append(w)
    return list(buckets.values())

print(is_anagram("listen", "silent"))               # True
print(group_anagrams(["eat", "tea", "tan", "ate"])) # [['eat','tea','ate'], ['tan']]

function countChars(s) {
  const freq = new Map();
  for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1);
  return freq;
}

function isAnagram(a, b) {              // O(n) time, O(k) space
  if (a.length !== b.length) return false;
  const freq = countChars(a);
  for (const ch of b) {
    const left = freq.get(ch);
    if (!left) return false;            // absent or already exhausted
    freq.set(ch, left - 1);
  }
  return true;
}

function groupAnagrams(words) {
  const buckets = new Map();
  for (const w of words) {
    const key = [...w].sort().join("");        // canonical form
    if (!buckets.has(key)) buckets.set(key, []);
    buckets.get(key).push(w);
  }
  return [...buckets.values()];
}

console.log(isAnagram("listen", "silent"));               // true
console.log(groupAnagrams(["eat", "tea", "tan", "ate"])); // [['eat','tea','ate'],['tan']]

def two_sum_sorted(nums, target):
    """Indices of a pair summing to target. O(n) time, O(1) space."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return lo, hi
        if total < target:
            lo += 1         # need a bigger sum; nums[lo] is the smallest option
        else:
            hi -= 1         # need a smaller sum; nums[hi] is the biggest option
    return None


def is_palindrome(s: str) -> bool:
    """Ignore non-alphanumerics and case. O(n) time, O(1) space."""
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum():
            lo += 1
        while lo < hi and not s[hi].isalnum():
            hi -= 1
        if s[lo].lower() != s[hi].lower():
            return False
        lo, hi = lo + 1, hi - 1
    return True


print(two_sum_sorted([1, 4, 7, 11, 15, 19, 24], 26))    # (2, 5)
print(is_palindrome("A man, a plan, a canal: Panama"))  # True

function twoSumSorted(nums, target) {   // O(n) time, O(1) space
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const total = nums[lo] + nums[hi];
    if (total === target) return [lo, hi];
    if (total < target) lo++;           // need a bigger sum
    else hi--;                          // need a smaller sum
  }
  return null;
}

const isAlnum = (ch) => /[a-z0-9]/i.test(ch);

function isPalindrome(s) {              // O(n) time, O(1) space
  let lo = 0;
  let hi = s.length - 1;
  while (lo < hi) {
    while (lo < hi && !isAlnum(s[lo])) lo++;
    while (lo < hi && !isAlnum(s[hi])) hi--;
    if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
    lo++;
    hi--;
  }
  return true;
}

console.log(twoSumSorted([1, 4, 7, 11, 15, 19, 24], 26));   // [2, 5]
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true

def dedupe_sorted(nums):
    """Keep unique values at the front; return the new length. O(n)/O(1)."""
    if not nums:
        return 0
    write = 1                       # slow pointer: next slot to fill
    for read in range(1, len(nums)):   # fast pointer: scans everything
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write


def move_zeroes(nums):
    """Push every zero to the end, keeping the order of the rest."""
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1


data = [1, 1, 2, 2, 2, 3, 4, 4]
print(dedupe_sorted(data), data[:5])    # 4 [1, 2, 3, 4, 2]

z = [0, 3, 0, 5, 9, 0, 2]
move_zeroes(z)
print(z)                                # [3, 5, 9, 2, 0, 0, 0]

function dedupeSorted(nums) {           // O(n) time, O(1) space
  if (nums.length === 0) return 0;
  let write = 1;                        // slow pointer
  for (let read = 1; read < nums.length; read++) {   // fast pointer
    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read];
  }
  return write;
}

function moveZeroes(nums) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
}

const data = [1, 1, 2, 2, 2, 3, 4, 4];
console.log(dedupeSorted(data), data.slice(0, 4));  // 4 [1, 2, 3, 4]

const z = [0, 3, 0, 5, 9, 0, 2];
moveZeroes(z);
console.log(z);                          // [3, 5, 9, 2, 0, 0, 0]

def longest_unique(s: str) -> int:
    """Length of the longest substring with no repeated character. O(n)."""
    last_seen = {}          # char -> most recent index
    best = 0
    left = 0                # window is s[left:right]

    for right, ch in enumerate(s):
        # If we have seen ch inside the current window, jump left past it.
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best


def min_subarray_sum(nums, target):
    """Shortest subarray with sum >= target, or 0. Positive numbers only."""
    left = total = 0
    best = float("inf")

    for right, value in enumerate(nums):
        total += value                      # grow to the right
        while total >= target:              # shrink while still valid
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1

    return 0 if best == float("inf") else best


print(longest_unique("abcabcbb"))              # 3  ("abc")
print(min_subarray_sum([2, 3, 1, 2, 4, 3], 7)) # 2  ([4, 3])

function longestUnique(s) {               // O(n) time, O(k) space
  const lastSeen = new Map();             // char -> most recent index
  let best = 0;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;        // jump past the duplicate
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function minSubarraySum(nums, target) {   // positive numbers only
  let left = 0;
  let total = 0;
  let best = Infinity;

  for (let right = 0; right < nums.length; right++) {
    total += nums[right];                 // grow
    while (total >= target) {             // shrink while valid
      best = Math.min(best, right - left + 1);
      total -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;
}

console.log(longestUnique("abcabcbb"));               // 3
console.log(minSubarraySum([2, 3, 1, 2, 4, 3], 7));   // 2

from itertools import accumulate

def build_prefix(nums):
    """prefix[i] = sum of nums[:i]; length n + 1 so no special cases."""
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    return prefix

nums = [3, 1, 4, 1, 5, 9, 2]
prefix = build_prefix(nums)                 # or: [0, *accumulate(nums)]
range_sum = lambda i, j: prefix[j + 1] - prefix[i]   # inclusive i..j
print(range_sum(2, 5))                      # 19

function buildPrefix(nums) {              // prefix[i] = sum of nums[0..i-1]
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

const nums = [3, 1, 4, 1, 5, 9, 2];
const prefix = buildPrefix(nums);
const rangeSum = (i, j) => prefix[j + 1] - prefix[i];   // inclusive
console.log(rangeSum(2, 5));              // 19

def subarrays_summing_to(nums, k):
    """Count subarrays with sum exactly k. Works with negatives. O(n)."""
    counts = {0: 1}         # a prefix sum of 0 has been seen once (empty prefix)
    running = answer = 0
    for value in nums:
        running += value
        # If running - k was seen before, every such position starts a valid
        # subarray ending here.
        answer += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return answer

print(subarrays_summing_to([1, 2, -1, 2, 1], 3))    # 3

function subarraysSummingTo(nums, k) {    // handles negatives, O(n)
  const counts = new Map([[0, 1]]);       // empty prefix seen once
  let running = 0;
  let answer = 0;
  for (const value of nums) {
    running += value;
    answer += counts.get(running - k) ?? 0;
    counts.set(running, (counts.get(running) ?? 0) + 1);
  }
  return answer;
}

console.log(subarraysSummingTo([1, 2, -1, 2, 1], 3));   // 3

def build_prefix_2d(grid):
    """pre[r][c] = sum of the rectangle from (0,0) to (r-1,c-1)."""
    rows, cols = len(grid), len(grid[0])
    pre = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            pre[r + 1][c + 1] = (grid[r][c] + pre[r][c + 1]
                                 + pre[r + 1][c] - pre[r][c])   # inclusion-exclusion
    return pre

function buildPrefix2D(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const pre = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      pre[r + 1][c + 1] = grid[r][c] + pre[r][c + 1] + pre[r + 1][c] - pre[r][c];
    }
  }
  return pre;                             // inclusion-exclusion
}

def apply_ranges(n, updates):
    """updates = [(start, end_inclusive, delta)]. O(n + len(updates))."""
    diff = [0] * (n + 1)
    for start, end, delta in updates:
        diff[start] += delta
        diff[end + 1] -= delta          # cancel the effect after the range

    result, running = [], 0
    for i in range(n):
        running += diff[i]              # prefix sum turns marks into values
        result.append(running)
    return result

# Three flight bookings on a 5-seat manifest.
print(apply_ranges(5, [(0, 2, 10), (1, 4, 20), (3, 3, 5)]))
# [10, 30, 30, 25, 20]

function applyRanges(n, updates) {        // updates: [start, endInclusive, delta]
  const diff = new Array(n + 1).fill(0);
  for (const [start, end, delta] of updates) {
    diff[start] += delta;
    diff[end + 1] -= delta;               // cancel after the range
  }

  const result = [];
  let running = 0;
  for (let i = 0; i < n; i++) {
    running += diff[i];                   // prefix sum materialises values
    result.push(running);
  }
  return result;
}

console.log(applyRanges(5, [[0, 2, 10], [1, 4, 20], [3, 3, 5]]));
// [10, 30, 30, 25, 20]

from collections import defaultdict, Counter

# --- dict basics ---
ages = {"ada": 36, "alan": 41}
ages["grace"] = 45          # O(1) average insert
ages.get("linus", 0)        # 0 - no KeyError
"ada" in ages               # O(1) membership
del ages["alan"]            # O(1)

# defaultdict removes the "does this key exist yet?" boilerplate
graph = defaultdict(list)
graph["a"].append("b")      # no need to initialise graph["a"]

# Counter is a dict tuned for tallies
freq = Counter("mississippi")
print(freq.most_common(2))  # [('i', 4), ('s', 4)]

# --- set basics: a dict with no values ---
seen = {1, 2, 3}
seen.add(4)                 # O(1)
seen & {3, 4, 5}            # {3, 4} intersection
seen | {9}                  # union
seen - {1}                  # difference

# Tuple keys let you index by a composite - very common in DP and grids.
memo = {}
memo[(3, 7)] = "row 3, col 7"

def first_duplicate(nums):
    """The classic O(n) time / O(n) space trade against an O(n^2) scan."""
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return None

// --- Map: the right default ---
const ages = new Map([["ada", 36], ["alan", 41]]);
ages.set("grace", 45);       // O(1) average
ages.get("linus") ?? 0;      // undefined -> 0
ages.has("ada");             // O(1)
ages.delete("alan");
ages.size;                   // O(1); plain objects need Object.keys().length

// Map preserves insertion order and accepts ANY key type.
const objKey = { id: 1 };
const meta = new Map([[objKey, "metadata"]]);   // impossible with a plain object

// --- Set ---
const seen = new Set([1, 2, 3]);
seen.add(4);
seen.has(2);                 // O(1)
const other = new Set([3, 4, 5]);
const intersection = [...seen].filter((x) => other.has(x));  // [3, 4]

// Composite keys must be serialised, since objects compare by reference.
const memo = new Map();
memo.set("3,7", "row 3, col 7");

function firstDuplicate(nums) {
  const seenValues = new Set();
  for (const x of nums) {
    if (seenValues.has(x)) return x;
    seenValues.add(x);
  }
  return null;
}

// Frequency tally, the JS way
function tally(items) {
  const freq = new Map();
  for (const item of items) freq.set(item, (freq.get(item) ?? 0) + 1);
  return freq;
}

class HashMap:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                    # update in place
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / len(self.buckets) > 0.75:
            self._resize()

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _resize(self):
        """O(n), but happens rarely enough to amortise to O(1) per insert."""
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        self.size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)

class HashMap {
  constructor(capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => []);
    this.size = 0;
  }

  #hash(key) {                          // FNV-style string hash
    const s = String(key);
    let h = 2166136261;
    for (let i = 0; i < s.length; i++) {
      h ^= s.charCodeAt(i);
      h = Math.imul(h, 16777619);
    }
    return (h >>> 0) % this.buckets.length;
  }

  put(key, value) {
    const bucket = this.buckets[this.#hash(key)];
    for (const entry of bucket) {
      if (entry[0] === key) {            // update in place
        entry[1] = value;
        return;
      }
    }
    bucket.push([key, value]);
    this.size++;
    if (this.size / this.buckets.length > 0.75) this.#resize();
  }

  get(key, fallback = undefined) {
    for (const [k, v] of this.buckets[this.#hash(key)]) if (k === key) return v;
    return fallback;
  }

  remove(key) {
    const bucket = this.buckets[this.#hash(key)];
    const i = bucket.findIndex(([k]) => k === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.size--;
    return true;
  }

  #resize() {                           // O(n), amortised away
    const old = this.buckets;
    this.buckets = Array.from({ length: old.length * 2 }, () => []);
    this.size = 0;
    for (const bucket of old) for (const [k, v] of bucket) this.put(k, v);
  }
}

class Node:
    __slots__ = ("value", "next")       # __slots__ saves memory per node

    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt


def from_list(values):
    """Build a list back-to-front so each node points at the one after it."""
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

class ListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

function fromArray(values) {          // build back-to-front
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
  return head;
}

function toArray(head) {
  const out = [];
  for (let cur = head; cur; cur = cur.next) out.push(cur.value);
  return out;
}

def reverse(head):
    """Flip every pointer. O(n) time, O(1) space - the canonical question."""
    prev = None
    while head:
        nxt = head.next     # 1. remember where we were going
        head.next = prev    # 2. flip this link backwards
        prev = head         # 3. prev advances
        head = nxt          # 4. head advances
    return prev             # prev is the old tail = the new head


head = from_list([1, 2, 3, 4, 5])
print(to_list(reverse(head)))       # [5, 4, 3, 2, 1]

function reverse(head) {              // O(n) time, O(1) space
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;            // 1. remember the rest
    cur.next = prev;                  // 2. flip the link
    prev = cur;                       // 3. advance prev
    cur = next;                       // 4. advance cur
  }
  return prev;                        // the old tail is the new head
}

console.log(toArray(reverse(fromArray([1, 2, 3, 4, 5]))));  // [5,4,3,2,1]

def has_cycle(head):
    """Floyd's tortoise and hare. O(n) time, O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # if there is a loop they must meet
            return True
    return False


def middle(head):
    """The slow pointer lands on the middle when fast reaches the end."""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

function hasCycle(head) {             // Floyd's tortoise and hare
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

function middle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

class LRUCache:
    """Hash map for O(1) lookup + doubly linked list for O(1) reordering."""

    class _Node:
        __slots__ = ("key", "value", "prev", "next")

        def __init__(self, key=None, value=None):
            self.key, self.value = key, value
            self.prev = self.next = None

    def __init__(self, capacity):
        self.capacity = capacity
        self.table = {}
        # Sentinel head/tail so no insertion or removal is a special case.
        self.head, self.tail = self._Node(), self._Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.table.get(key)
        if node is None:
            return -1
        self._unlink(node)          # touch it: move to the front
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.table:
            node = self.table[key]
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.table) == self.capacity:
            lru = self.tail.prev    # the node just before the tail sentinel
            self._unlink(lru)
            del self.table[lru.key]
        node = self._Node(key, value)
        self.table[key] = node
        self._push_front(node)


cache = LRUCache(2)
cache.put(1, "a"); cache.put(2, "b")
cache.get(1)                 # 'a' - 1 is now most recent
cache.put(3, "c")            # evicts key 2
print(cache.get(2))          # -1

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.table = new Map();
    // Sentinel head/tail remove every edge case.
    this.head = { key: null, value: null };
    this.tail = { key: null, value: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  #unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  #pushFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.table.get(key);
    if (!node) return -1;
    this.#unlink(node);
    this.#pushFront(node);            // touch it
    return node.value;
  }

  put(key, value) {
    const existing = this.table.get(key);
    if (existing) {
      existing.value = value;
      this.#unlink(existing);
      this.#pushFront(existing);
      return;
    }
    if (this.table.size === this.capacity) {
      const lru = this.tail.prev;
      this.#unlink(lru);
      this.table.delete(lru.key);
    }
    const node = { key, value, prev: null, next: null };
    this.table.set(key, node);
    this.#pushFront(node);
  }
}

const cache = new LRUCache(2);
cache.put(1, "a");
cache.put(2, "b");
cache.get(1);                         // 'a'
cache.put(3, "c");                    // evicts key 2
console.log(cache.get(2));            // -1

def is_balanced(s: str) -> bool:
    """O(n) time, O(n) space."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for ch in s:
        if ch in "([{":
            stack.append(ch)            # remember what must be closed
        elif ch in pairs:
            # Must close the MOST RECENT opener - that is the LIFO rule.
            if not stack or stack.pop() != pairs[ch]:
                return False

    return not stack                    # nothing may be left open


print(is_balanced("{[()]}"))    # True
print(is_balanced("{[(])}"))    # False - correct count, wrong nesting

function isBalanced(s) {                // O(n) time, O(n) space
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];

  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;   // wrong or missing opener
    }
  }
  return stack.length === 0;            // nothing left open
}

console.log(isBalanced("{[()]}"));      // true
console.log(isBalanced("{[(])}"));      // false

def days_until_warmer(temps):
    """For each day, how many days until a warmer one. O(n) time and space."""
    answer = [0] * len(temps)
    stack = []                          # indices, temperatures decreasing

    for i, t in enumerate(temps):
        # Everything cooler than today has just found its answer.
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)

    return answer                       # unresolved indices keep 0


def largest_rectangle(heights):
    """Largest rectangle in a histogram. O(n) with a monotonic stack."""
    stack = []                          # indices, heights increasing
    best = 0
    for i, h in enumerate([*heights, 0]):   # sentinel 0 flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            # The bar extends left to the previous smaller bar (exclusive).
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best


print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
print(largest_rectangle([2, 1, 5, 6, 2, 3]))    # 10

function daysUntilWarmer(temps) {       // O(n) time and space
  const answer = new Array(temps.length).fill(0);
  const stack = [];                     // indices, decreasing temperatures

  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack.at(-1)] < temps[i]) {
      const j = stack.pop();
      answer[j] = i - j;                // today resolves day j
    }
    stack.push(i);
  }
  return answer;
}

function largestRectangle(heights) {    // O(n)
  const stack = [];                     // indices, increasing heights
  let best = 0;
  const bars = [...heights, 0];         // sentinel flushes the stack

  for (let i = 0; i < bars.length; i++) {
    while (stack.length && heights[stack.at(-1)] >= bars[i]) {
      const height = heights[stack.pop()];
      const left = stack.length ? stack.at(-1) + 1 : 0;
      best = Math.max(best, height * (i - left));
    }
    stack.push(i);
  }
  return best;
}

console.log(daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73]));
// [1, 1, 4, 2, 1, 1, 0, 0]
console.log(largestRectangle([2, 1, 5, 6, 2, 3]));   // 10

class CircularQueue:
    """Fixed-capacity FIFO. Every operation O(1), memory never grows."""

    def __init__(self, capacity):
        self.data = [None] * capacity
        self.head = 0           # index of the oldest item
        self.size = 0           # tracked explicitly - see the note below

    def enqueue(self, value):
        if self.size == len(self.data):
            raise OverflowError("queue is full")
        tail = (self.head + self.size) % len(self.data)  # wrap around
        self.data[tail] = value
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("queue is empty")
        value = self.data[self.head]
        self.data[self.head] = None                 # release the reference
        self.head = (self.head + 1) % len(self.data)
        self.size -= 1
        return value

    def __len__(self):
        return self.size


q = CircularQueue(3)
q.enqueue("a"); q.enqueue("b"); q.enqueue("c")
print(q.dequeue())          # 'a'  - slot 0 is now free again
q.enqueue("d")              # reuses slot 0 instead of growing
print(len(q))               # 3

class CircularQueue {
  constructor(capacity) {
    this.data = new Array(capacity).fill(null);
    this.head = 0;                    // oldest item
    this.size = 0;                    // tracked explicitly
  }

  enqueue(value) {
    if (this.size === this.data.length) throw new RangeError("queue is full");
    const tail = (this.head + this.size) % this.data.length;   // wrap around
    this.data[tail] = value;
    this.size++;
  }

  dequeue() {
    if (this.size === 0) return undefined;
    const value = this.data[this.head];
    this.data[this.head] = null;      // release the reference for the GC
    this.head = (this.head + 1) % this.data.length;
    this.size--;
    return value;
  }
}

const q = new CircularQueue(3);
q.enqueue("a"); q.enqueue("b"); q.enqueue("c");
console.log(q.dequeue());             // 'a' - slot 0 is free again
q.enqueue("d");                       // reuses slot 0, no growth

from collections import deque

q = deque()
q.append("a")        # enqueue at the back      O(1)
q.append("b")
q.popleft()          # dequeue from the front   O(1)

q.appendleft("z")    # deque powers: push front O(1)
q.pop()              # pop back                 O(1)

# NEVER use list.pop(0) as a queue - it shifts every remaining element,
# which is O(n) and silently turns an O(V+E) BFS into O(V^2).

# A ring buffer: a fixed-size queue that overwrites the oldest entry.
recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    recent.append(x)
print(list(recent))          # [3, 4, 5]

// JavaScript has no deque, and Array.shift() is O(n). Use a head index:
// the array grows but never re-indexes, so both ends stay O(1) amortised.
class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }

  enqueue(x) {
    this.items.push(x);                 // O(1)
  }

  dequeue() {                           // O(1) amortised
    if (this.head >= this.items.length) return undefined;
    const value = this.items[this.head];
    this.items[this.head++] = undefined; // release the reference for the GC
    if (this.head > 32 && this.head * 2 >= this.items.length) {
      this.items = this.items.slice(this.head);  // compact occasionally
      this.head = 0;
    }
    return value;
  }

  get size() {
    return this.items.length - this.head;
  }

  peek() {
    return this.items[this.head];
  }
}

const q = new Queue();
q.enqueue("a");
q.enqueue("b");
console.log(q.dequeue(), q.size);       // 'a' 1

from collections import deque

def window_max(nums, k):
    """Maximum of every window of size k. O(n) time, O(k) space."""
    dq = deque()        # indices; nums[dq] is strictly decreasing
    out = []

    for i, value in enumerate(nums):
        # 1. Drop indices that have fallen out of the window on the left.
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. Drop smaller values from the back: they can never win again.
        while dq and nums[dq[-1]] <= value:
            dq.pop()
        dq.append(i)
        # 3. Once the first full window exists, the front is the maximum.
        if i >= k - 1:
            out.append(nums[dq[0]])

    return out


print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

function windowMax(nums, k) {           // O(n) time, O(k) space
  const dq = [];                        // indices; values strictly decreasing
  const out = [];

  for (let i = 0; i < nums.length; i++) {
    if (dq.length && dq[0] <= i - k) dq.shift();       // 1. expire the front
    while (dq.length && nums[dq.at(-1)] <= nums[i]) dq.pop();  // 2. dominate
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[0]]);             // 3. front is the max
  }
  return out;
}

console.log(windowMax([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

def fib_naive(n):
    """O(2^n) - recomputes the same subproblems over and over."""
    if n <= 1:                      # base case
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)


print(fib_naive(30))        # slow: ~1.6 million calls

function fibNaive(n) {                  // O(2^n)
  if (n <= 1) return n;                 // base case
  return fibNaive(n - 1) + fibNaive(n - 2);
}

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    """O(n) time, O(n) space. One line of caching removes the whole blow-up."""
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)


print(fib_memo(300))        # instant, arbitrary precision integers

const memo = new Map();
function fibMemo(n) {                   // O(n) time and space
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, value);
  return value;
}

// A reusable memoiser for any single-argument pure function.
const memoize = (fn, cache = new Map()) => (x) =>
  cache.has(x) ? cache.get(x) : (cache.set(x, fn(x)), cache.get(x));

console.log(fibMemo(90));               // 2880067194370816000 (float precision!)

def fib_iterative(n):
    """O(n) time, O(1) space - no stack frames at all."""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_iterative(90))    # 2880067194370816120

function fibIterative(n) {              // O(n) time, O(1) space
  let [a, b] = [0, 1];
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

console.log(fibIterative(90));          // use BigInt beyond 2^53 - 1

def dfs_recursive(node, visit):
    if node is None:
        return
    visit(node.value)
    dfs_recursive(node.left, visit)
    dfs_recursive(node.right, visit)


def dfs_iterative(root, visit):
    """Same pre-order walk, but the stack is ours and lives on the heap."""
    stack = [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        visit(node.value)
        stack.append(node.right)    # push right first so left pops first
        stack.append(node.left)

function dfsRecursive(node, visit) {
  if (!node) return;
  visit(node.value);
  dfsRecursive(node.left, visit);
  dfsRecursive(node.right, visit);
}

function dfsIterative(root, visit) {    // our stack lives on the heap
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    if (!node) continue;
    visit(node.value);
    stack.push(node.right);             // push right first so left pops first
    stack.push(node.left);
  }
}

def merge_sort(nums):
    """O(n log n) always. Stable. O(n) extra space."""
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)


def merge(left, right):
    """Two-pointer merge of two sorted lists. O(n + m)."""
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        # <= (not <) is what makes this STABLE: ties take from the left.
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


print(merge_sort([38, 12, 47, 5, 29]))          # [5, 12, 29, 38, 47]

function mergeSort(nums) {              // O(n log n) always, stable
  if (nums.length <= 1) return nums;
  const mid = nums.length >> 1;
  return merge(mergeSort(nums.slice(0, mid)), mergeSort(nums.slice(mid)));
}

function merge(left, right) {           // O(n + m) two-pointer merge
  const out = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    // <= keeps it STABLE: ties come from the left run.
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

console.log(mergeSort([38, 12, 47, 5, 29]));       // [5, 12, 29, 38, 47]

def quicksort(nums, lo=0, hi=None):
    """Average O(n log n), worst O(n^2). In place, not stable."""
    if hi is None:
        hi = len(nums) - 1
    while lo < hi:
        p = partition(nums, lo, hi)
        # Recurse into the SMALLER side, loop on the larger one.
        # This caps stack depth at O(log n) even in the worst case.
        if p - lo < hi - p:
            quicksort(nums, lo, p - 1)
            lo = p + 1
        else:
            quicksort(nums, p + 1, hi)
            hi = p - 1


def partition(nums, lo, hi):
    """Lomuto partition with a median-of-three pivot."""
    mid = (lo + hi) // 2
    # Order lo, mid, hi so the median ends up at hi as the pivot.
    if nums[mid] < nums[lo]:
        nums[mid], nums[lo] = nums[lo], nums[mid]
    if nums[hi] < nums[lo]:
        nums[hi], nums[lo] = nums[lo], nums[hi]
    if nums[mid] < nums[hi]:
        nums[mid], nums[hi] = nums[hi], nums[mid]

    pivot = nums[hi]
    store = lo
    for i in range(lo, hi):
        if nums[i] < pivot:
            nums[i], nums[store] = nums[store], nums[i]
            store += 1
    nums[store], nums[hi] = nums[hi], nums[store]
    return store


data = [38, 12, 47, 5, 29]
quicksort(data)
print(data)                                     # [5, 12, 29, 38, 47]

function quicksort(nums, lo = 0, hi = nums.length - 1) {
  while (lo < hi) {
    const p = partition(nums, lo, hi);
    // Recurse on the smaller side to bound stack depth at O(log n).
    if (p - lo < hi - p) {
      quicksort(nums, lo, p - 1);
      lo = p + 1;
    } else {
      quicksort(nums, p + 1, hi);
      hi = p - 1;
    }
  }
  return nums;
}

function partition(nums, lo, hi) {      // Lomuto, median-of-three pivot
  const mid = (lo + hi) >> 1;
  const swap = (a, b) => { [nums[a], nums[b]] = [nums[b], nums[a]]; };
  if (nums[mid] < nums[lo]) swap(mid, lo);
  if (nums[hi] < nums[lo]) swap(hi, lo);
  if (nums[mid] < nums[hi]) swap(mid, hi);

  const pivot = nums[hi];
  let store = lo;
  for (let i = lo; i < hi; i++) if (nums[i] < pivot) swap(i, store++);
  swap(store, hi);
  return store;
}

console.log(quicksort([38, 12, 47, 5, 29]));       // [5, 12, 29, 38, 47]

def counting_sort(nums, max_value):
    """O(n + k) - beats the n log n bound by never comparing."""
    counts = [0] * (max_value + 1)
    for x in nums:
        counts[x] += 1
    out = []
    for value, count in enumerate(counts):
        out.extend([value] * count)
    return out


print(counting_sort([4, 1, 3, 1, 4, 0], 4))     # [0, 1, 1, 3, 4, 4]

function countingSort(nums, maxValue) { // O(n + k), no comparisons at all
  const counts = new Array(maxValue + 1).fill(0);
  for (const x of nums) counts[x]++;
  const out = [];
  counts.forEach((count, value) => {
    for (let i = 0; i < count; i++) out.push(value);
  });
  return out;
}

console.log(countingSort([4, 1, 3, 1, 4, 0], 4));  // [0, 1, 1, 3, 4, 4]

people = [("ada", 36), ("alan", 41), ("grace", 36)]

sorted(people, key=lambda p: p[1])              # by age, stable
sorted(people, key=lambda p: (-p[1], p[0]))     # age desc, then name asc
sorted(people, key=lambda p: p[1], reverse=True)

words = ["banana", "kiwi", "apple"]
words.sort(key=len)                             # in place, by length

# Stability composed: sort by the secondary key first, then the primary.
records = sorted(people, key=lambda p: p[0])    # name
records.sort(key=lambda p: p[1])                # then age; names stay ordered

const people = [["ada", 36], ["alan", 41], ["grace", 36]];

people.sort((a, b) => a[1] - b[1]);            // by age, stable
people.sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0])); // age desc, name asc

const words = ["banana", "kiwi", "apple"];
words.sort((a, b) => a.length - b.length);     // in place

// The classic bug: sort() with no comparator sorts by STRING value.
console.log([10, 9, 1].sort());                // [1, 10, 9]  - wrong
console.log([10, 9, 1].sort((a, b) => a - b)); // [1, 9, 10]  - right

def binary_search(nums, target):
    """Index of target, or -1. O(log n) time, O(1) space."""
    lo, hi = 0, len(nums) - 1           # inclusive range [lo, hi]
    while lo <= hi:
        mid = lo + (hi - lo) // 2       # overflow-safe by habit
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1                # discard mid and everything left
        else:
            hi = mid - 1                # discard mid and everything right
    return -1


print(binary_search([1, 3, 3, 3, 7, 9], 7))         # 4

function binarySearch(nums, target) {   // O(log n) time, O(1) space
  let lo = 0;
  let hi = nums.length - 1;             // inclusive range
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);  // overflow-safe midpoint
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

console.log(binarySearch([1, 3, 3, 3, 7, 9], 7));      // 4

def lower_bound(nums, target):
    """First index with nums[i] >= target (insertion point). O(log n)."""
    lo, hi = 0, len(nums)               # half-open [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid                    # mid might be the answer - keep it
    return lo


def upper_bound(nums, target):
    """First index with nums[i] > target."""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] <= target:         # the only change: <= instead of <
            lo = mid + 1
        else:
            hi = mid
    return lo


# The standard library already has both:
#   from bisect import bisect_left, bisect_right, insort

data = [1, 3, 3, 3, 7, 9]
print(lower_bound(data, 3), upper_bound(data, 3))   # 1 4  -> three 3s

function lowerBound(nums, target) {     // first index with nums[i] >= target
  let lo = 0;
  let hi = nums.length;                 // half-open range
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;                      // mid may be the answer
  }
  return lo;
}

function upperBound(nums, target) {     // first index with nums[i] > target
  let lo = 0;
  let hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] <= target) lo = mid + 1;   // the only change: <= not <
    else hi = mid;
  }
  return lo;
}

const data = [1, 3, 3, 3, 7, 9];
console.log(lowerBound(data, 3), upperBound(data, 3)); // 1 4

def min_ship_capacity(weights, days):
    """Smallest daily capacity that ships everything within `days` days."""

    def feasible(capacity):
        """Monotonic: if capacity works, capacity + 1 also works."""
        needed, load = 1, 0
        for w in weights:
            if load + w > capacity:
                needed += 1     # start a new day
                load = 0
            load += w
        return needed <= days

    # Lower bound: must fit the heaviest single package in one day.
    # Upper bound: ship everything in one day.
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid            # mid works - try to do better
        else:
            lo = mid + 1        # mid is too small
    return lo                   # first feasible capacity


print(min_ship_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))    # 15

function minShipCapacity(weights, days) {
  const feasible = (capacity) => {      // monotonic predicate
    let needed = 1;
    let load = 0;
    for (const w of weights) {
      if (load + w > capacity) {
        needed++;                       // start a new day
        load = 0;
      }
      load += w;
    }
    return needed <= days;
  };

  let lo = Math.max(...weights);        // must fit the heaviest package
  let hi = weights.reduce((a, b) => a + b, 0);   // everything in one day
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;        // works - try smaller
    else lo = mid + 1;                  // too small
  }
  return lo;
}

console.log(minShipCapacity([1,2,3,4,5,6,7,8,9,10], 5));   // 15

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


def preorder(node, out=None):
    """Node, left, right. Use to serialise or copy a tree."""
    out = [] if out is None else out
    if node:
        out.append(node.value)
        preorder(node.left, out)
        preorder(node.right, out)
    return out


def inorder(node, out=None):
    """Left, node, right. On a BST this yields sorted order."""
    out = [] if out is None else out
    if node:
        inorder(node.left, out)
        out.append(node.value)
        inorder(node.right, out)
    return out


def postorder(node, out=None):
    """Left, right, node. Children finish first - use to free or evaluate."""
    out = [] if out is None else out
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.value)
    return out

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

function preorder(node, out = []) {     // node, left, right
  if (!node) return out;
  out.push(node.value);
  preorder(node.left, out);
  preorder(node.right, out);
  return out;
}

function inorder(node, out = []) {      // left, node, right -> sorted on a BST
  if (!node) return out;
  inorder(node.left, out);
  out.push(node.value);
  inorder(node.right, out);
  return out;
}

function postorder(node, out = []) {    // left, right, node
  if (!node) return out;
  postorder(node.left, out);
  postorder(node.right, out);
  out.push(node.value);
  return out;
}

from collections import deque

def level_order(root):
    """BFS with a queue. Returns one list per level."""
    if not root:
        return []
    levels, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):         # snapshot the size = this level
            node = q.popleft()
            level.append(node.value)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        levels.append(level)
    return levels

function levelOrder(root) {             // BFS, one array per level
  if (!root) return [];
  const levels = [];
  let frontier = [root];
  while (frontier.length) {
    levels.push(frontier.map((n) => n.value));
    const next = [];
    for (const node of frontier) {
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    frontier = next;
  }
  return levels;
}

def inorder_iterative(root):
    """The same walk without recursion, using an explicit stack."""
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                      # go as far left as possible
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()               # backtrack one node
        out.append(cur.value)
        cur = cur.right                 # then explore its right subtree
    return out

function inorderIterative(root) {       // explicit stack, no recursion
  const out = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {                       // dive left
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();                  // backtrack
    out.push(cur.value);
    cur = cur.right;                    // then go right
  }
  return out;
}

def height(node):
    """O(n) - one visit per node."""
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def is_balanced(root):
    """Return -1 as a sentinel for 'already unbalanced' to stay O(n)."""
    def check(node):
        if node is None:
            return 0
        left = check(node.left)
        if left == -1:
            return -1
        right = check(node.right)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return check(root) != -1


def diameter(root):
    """Longest path between any two nodes, in edges. O(n)."""
    best = 0

    def depth(node):
        nonlocal best
        if node is None:
            return 0
        left, right = depth(node.left), depth(node.right)
        # The longest path THROUGH this node, considered once per node.
        best = max(best, left + right)
        return 1 + max(left, right)

    depth(root)
    return best


def lowest_common_ancestor(node, a, b):
    """The deepest node that has both a and b in its subtree. O(n)."""
    if node is None or node is a or node is b:
        return node
    left = lowest_common_ancestor(node.left, a, b)
    right = lowest_common_ancestor(node.right, a, b)
    if left and right:
        return node             # a and b split here, so this is the LCA
    return left or right        # both are on one side

function height(node) {                 // O(n)
  if (!node) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

function isBalanced(root) {             // -1 sentinel keeps it O(n)
  const check = (node) => {
    if (!node) return 0;
    const left = check(node.left);
    if (left === -1) return -1;
    const right = check(node.right);
    if (right === -1 || Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right);
  };
  return check(root) !== -1;
}

function diameter(root) {               // longest path in edges, O(n)
  let best = 0;
  const depth = (node) => {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    best = Math.max(best, left + right);   // path through this node
    return 1 + Math.max(left, right);
  };
  depth(root);
  return best;
}

function lowestCommonAncestor(node, a, b) {
  if (!node || node === a || node === b) return node;
  const left = lowestCommonAncestor(node.left, a, b);
  const right = lowestCommonAncestor(node.right, a, b);
  if (left && right) return node;       // a and b diverge here
  return left ?? right;
}

class BST:
    class _Node:
        __slots__ = ("value", "left", "right")

        def __init__(self, value):
            self.value = value
            self.left = self.right = None

    def __init__(self):
        self.root = None

    def insert(self, value):
        """O(h). Duplicates are ignored."""
        def go(node):
            if node is None:
                return BST._Node(value)
            if value < node.value:
                node.left = go(node.left)
            elif value > node.value:
                node.right = go(node.right)
            return node
        self.root = go(self.root)

    def contains(self, value):
        """O(h), iterative - no stack frames needed."""
        node = self.root
        while node:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def delete(self, value):
        """The only fiddly operation. Three cases, see the comments."""
        def go(node, value):
            if node is None:
                return None
            if value < node.value:
                node.left = go(node.left, value)
            elif value > node.value:
                node.right = go(node.right, value)
            else:
                # Case 1 and 2: zero or one child - splice the child up.
                if node.left is None:
                    return node.right
                if node.right is None:
                    return node.left
                # Case 3: two children. Replace this value with its
                # in-order successor (smallest value in the right subtree),
                # then delete that successor from the right subtree.
                successor = node.right
                while successor.left:
                    successor = successor.left
                node.value = successor.value
                node.right = go(node.right, successor.value)
            return node
        self.root = go(self.root, value)

    def in_order(self):
        """Sorted iteration for free. O(n)."""
        stack, node = [], self.root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            yield node.value
            node = node.right


tree = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    tree.insert(v)
print(list(tree.in_order()))    # [1, 3, 4, 6, 7, 8, 10, 13, 14]
tree.delete(3)
print(list(tree.in_order()))    # [1, 4, 6, 7, 8, 10, 13, 14]

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {                       // O(h), duplicates ignored
    const go = (node) => {
      if (!node) return { value, left: null, right: null };
      if (value < node.value) node.left = go(node.left);
      else if (value > node.value) node.right = go(node.right);
      return node;
    };
    this.root = go(this.root);
  }

  contains(value) {                     // O(h), iterative
    let node = this.root;
    while (node) {
      if (value === node.value) return true;
      node = value < node.value ? node.left : node.right;
    }
    return false;
  }

  delete(value) {
    const go = (node, value) => {
      if (!node) return null;
      if (value < node.value) node.left = go(node.left, value);
      else if (value > node.value) node.right = go(node.right, value);
      else {
        if (!node.left) return node.right;    // 0 or 1 child
        if (!node.right) return node.left;
        // Two children: promote the in-order successor.
        let successor = node.right;
        while (successor.left) successor = successor.left;
        node.value = successor.value;
        node.right = go(node.right, successor.value);
      }
      return node;
    };
    this.root = go(this.root, value);
  }

  *inOrder() {                          // sorted iteration, O(n)
    const stack = [];
    let node = this.root;
    while (stack.length || node) {
      while (node) {
        stack.push(node);
        node = node.left;
      }
      node = stack.pop();
      yield node.value;
      node = node.right;
    }
  }
}

const tree = new BST();
for (const v of [8, 3, 10, 1, 6, 14, 4, 7, 13]) tree.insert(v);
console.log([...tree.inOrder()]);       // [1,3,4,6,7,8,10,13,14]

class AVLNode:
    __slots__ = ("value", "left", "right", "height")

    def __init__(self, value):
        self.value = value
        self.left = self.right = None
        self.height = 1


def h(node):
    return node.height if node else 0


def update(node):
    node.height = 1 + max(h(node.left), h(node.right))


def balance_factor(node):
    """> 1 means left heavy, < -1 means right heavy."""
    return h(node.left) - h(node.right) if node else 0


def rotate_right(y):
    """    y            x
          / \\          / \\
         x   C   ->    A   y      O(1) pointer surgery, order preserved.
        / \\              / \\
       A   B            B   C
    """
    x = y.left
    y.left = x.right
    x.right = y
    update(y)
    update(x)
    return x                # x is the new subtree root


def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y


def avl_insert(node, value):
    """Ordinary BST insert, then rebalance on the way back up. O(log n)."""
    if node is None:
        return AVLNode(value)
    if value < node.value:
        node.left = avl_insert(node.left, value)
    elif value > node.value:
        node.right = avl_insert(node.right, value)
    else:
        return node

    update(node)
    bf = balance_factor(node)

    if bf > 1 and value < node.left.value:      # left-left
        return rotate_right(node)
    if bf < -1 and value > node.right.value:    # right-right
        return rotate_left(node)
    if bf > 1:                                  # left-right
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1:                                 # right-left
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node


root = None
for v in [10, 20, 30, 40, 50]:      # sorted input that would ruin a plain BST
    root = avl_insert(root, v)
print(root.value, root.height)      # 20 3  - height 3 instead of 5

const h = (node) => (node ? node.height : 0);
const update = (node) => { node.height = 1 + Math.max(h(node.left), h(node.right)); };
const balanceFactor = (node) => (node ? h(node.left) - h(node.right) : 0);

function rotateRight(y) {               // O(1), preserves in-order sequence
  const x = y.left;
  y.left = x.right;
  x.right = y;
  update(y);
  update(x);
  return x;                             // new subtree root
}

function rotateLeft(x) {
  const y = x.right;
  x.right = y.left;
  y.left = x;
  update(x);
  update(y);
  return y;
}

function avlInsert(node, value) {       // BST insert + rebalance on unwind
  if (!node) return { value, left: null, right: null, height: 1 };
  if (value < node.value) node.left = avlInsert(node.left, value);
  else if (value > node.value) node.right = avlInsert(node.right, value);
  else return node;

  update(node);
  const bf = balanceFactor(node);

  if (bf > 1 && value < node.left.value) return rotateRight(node);   // LL
  if (bf < -1 && value > node.right.value) return rotateLeft(node);  // RR
  if (bf > 1) {                                                      // LR
    node.left = rotateLeft(node.left);
    return rotateRight(node);
  }
  if (bf < -1) {                                                     // RL
    node.right = rotateRight(node.right);
    return rotateLeft(node);
  }
  return node;
}

let root = null;
for (const v of [10, 20, 30, 40, 50]) root = avlInsert(root, v);
console.log(root.value, root.height);   // 20 3

import heapq

# heapq turns any list into a MIN-heap in place.
nums = [5, 1, 8, 3, 9, 2]
heapq.heapify(nums)             # O(n), not O(n log n)
heapq.heappush(nums, 0)         # O(log n)
smallest = heapq.heappop(nums)  # O(log n) -> 0
peek = nums[0]                  # O(1)

# Top-k without sorting everything: O(n log k) time, O(k) space.
def top_k(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)     # evict the smallest; keep the k largest
    return sorted(heap, reverse=True)

# For a MAX-heap, negate the values (heapq has no max variant).
def max_heap_demo(values):
    heap = [-v for v in values]
    heapq.heapify(heap)
    return -heapq.heappop(heap)     # largest

# Priority queues: push (priority, tiebreaker, payload) tuples so that
# equal priorities never try to compare the payloads.
import itertools
counter = itertools.count()
tasks = []
heapq.heappush(tasks, (2, next(counter), "write tests"))
heapq.heappush(tasks, (1, next(counter), "fix outage"))
print(heapq.heappop(tasks)[2])      # 'fix outage'

print(top_k([7, 2, 9, 4, 1, 8], 3)) # [9, 8, 7]
print(heapq.nlargest(3, [7, 2, 9])) # [9, 7, 2] - built in

// JavaScript has no heap, so here is a complete one. Pass a comparator to
// get a max-heap or to order objects by any field.
class Heap {
  constructor(compare = (a, b) => a - b, items = []) {
    this.compare = compare;
    this.data = items;
    // Heapify bottom-up: O(n), not O(n log n).
    for (let i = (this.data.length >> 1) - 1; i >= 0; i--) this.#siftDown(i);
  }

  get size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];              // O(1)
  }

  push(value) {                       // O(log n)
    this.data.push(value);
    this.#siftUp(this.data.length - 1);
  }

  pop() {                             // O(log n)
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      this.#siftDown(0);
    }
    return top;
  }

  #siftUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(this.data[i], this.data[parent]) >= 0) break;
      [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
      i = parent;
    }
  }

  #siftDown(i) {
    const n = this.data.length;
    while (true) {
      let best = i;
      const l = 2 * i + 1;
      const r = 2 * i + 2;
      if (l < n && this.compare(this.data[l], this.data[best]) < 0) best = l;
      if (r < n && this.compare(this.data[r], this.data[best]) < 0) best = r;
      if (best === i) return;
      [this.data[i], this.data[best]] = [this.data[best], this.data[i]];
      i = best;
    }
  }
}

const minHeap = new Heap();
[5, 1, 8, 3].forEach((x) => minHeap.push(x));
console.log(minHeap.pop());                     // 1

const maxHeap = new Heap((a, b) => b - a);
const tasks = new Heap((a, b) => a.priority - b.priority);
tasks.push({ priority: 2, name: "write tests" });
tasks.push({ priority: 1, name: "fix outage" });
console.log(tasks.pop().name);                  // 'fix outage'

function topK(nums, k) {                        // O(n log k)
  const heap = new Heap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop();              // drop the smallest
  }
  return heap.data.sort((a, b) => b - a);
}

console.log(topK([7, 2, 9, 4, 1, 8], 3));       // [9, 8, 7]

class Trie:
    def __init__(self):
        self.children = {}      # character -> Trie
        self.is_word = False
        self.count = 0          # how many words pass through this node

    def insert(self, word):
        """O(len(word))."""
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
            node.count += 1
        node.is_word = True

    def _walk(self, prefix):
        """Follow a prefix; return the node it ends at, or None."""
        node = self
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def count_prefix(self, prefix):
        """How many stored words begin with this prefix. O(len(prefix))."""
        node = self._walk(prefix)
        return node.count if node else 0

    def autocomplete(self, prefix, limit=10):
        """Every word under the prefix, via DFS from that node."""
        node = self._walk(prefix)
        if node is None:
            return []
        out = []

        def dfs(node, path):
            if len(out) >= limit:
                return
            if node.is_word:
                out.append(prefix + path)
            for ch, child in sorted(node.children.items()):
                dfs(child, path + ch)

        dfs(node, "")
        return out


trie = Trie()
for w in ["car", "card", "care", "cat", "dog"]:
    trie.insert(w)

print(trie.search("car"))            # True
print(trie.search("ca"))             # False - a prefix is not a word
print(trie.starts_with("ca"))        # True
print(trie.count_prefix("car"))      # 3
print(trie.autocomplete("car"))      # ['car', 'card', 'care']

class Trie {
  constructor() {
    this.children = new Map();        // character -> Trie
    this.isWord = false;
    this.count = 0;                   // words passing through this node
  }

  insert(word) {                      // O(word.length)
    let node = this;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new Trie());
      node = node.children.get(ch);
      node.count++;
    }
    node.isWord = true;
  }

  #walk(prefix) {
    let node = this;
    for (const ch of prefix) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }

  search(word) {
    const node = this.#walk(word);
    return Boolean(node?.isWord);
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }

  countPrefix(prefix) {               // O(prefix.length)
    return this.#walk(prefix)?.count ?? 0;
  }

  autocomplete(prefix, limit = 10) {
    const start = this.#walk(prefix);
    if (!start) return [];
    const out = [];
    const dfs = (node, path) => {
      if (out.length >= limit) return;
      if (node.isWord) out.push(prefix + path);
      for (const ch of [...node.children.keys()].sort()) {
        dfs(node.children.get(ch), path + ch);
      }
    };
    dfs(start, "");
    return out;
  }
}

const trie = new Trie();
for (const w of ["car", "card", "care", "cat", "dog"]) trie.insert(w);

console.log(trie.search("car"));        // true
console.log(trie.search("ca"));         // false
console.log(trie.startsWith("ca"));     // true
console.log(trie.countPrefix("car"));   // 3
console.log(trie.autocomplete("car"));  // ['car','card','care']

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))    # every element is its own root
        self.rank = [0] * n             # upper bound on tree height
        self.count = n                  # number of disjoint groups

    def find(self, x):
        """Path compression: point every node on the path at the root."""
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:   # second pass re-points the path
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        """Union by rank. Returns False if they were already connected."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                # already together - a cycle edge
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra            # attach the shallower under the deeper
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


def count_islands(grid):
    """Connected components in a grid, via DSU. O(rows * cols * a(n))."""
    rows, cols = len(grid), len(grid[0])
    dsu = UnionFind(rows * cols)
    water = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:
                water += 1
                continue
            for dr, dc in ((1, 0), (0, 1)):     # right and down is enough
                nr, nc = r + dr, c + dc
                if nr < rows and nc < cols and grid[nr][nc] == 1:
                    dsu.union(r * cols + c, nr * cols + nc)
    return dsu.count - water


uf = UnionFind(7)
uf.union(0, 1); uf.union(2, 3); uf.union(1, 3)
print(uf.connected(0, 3), uf.count)     # True 4

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;                     // number of disjoint groups
  }

  find(x) {                             // with path compression
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    while (this.parent[x] !== root) {   // flatten the path
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }

  union(a, b) {                         // union by rank
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;        // already connected -> cycle edge
    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
    this.count--;
    return true;
  }

  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

const uf = new UnionFind(7);
uf.union(0, 1);
uf.union(2, 3);
uf.union(1, 3);
console.log(uf.connected(0, 3), uf.count);   // true 4

from collections import defaultdict

def build_undirected(n, edges):
    """Adjacency list. O(V + E) space."""
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)      # drop this line for a DIRECTED graph
    return graph


def build_weighted(n, edges):
    """edges = [(a, b, weight)] -> {node: [(neighbour, weight)]}"""
    graph = defaultdict(list)
    for a, b, w in edges:
        graph[a].append((b, w))
        graph[b].append((a, w))
    return graph


def build_matrix(n, edges):
    """O(V^2) space; good for dense graphs and Floyd-Warshall."""
    matrix = [[0] * n for _ in range(n)]
    for a, b in edges:
        matrix[a][b] = matrix[b][a] = 1
    return matrix


# A grid IS a graph: each cell is a vertex with up to four edges.
DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))

def grid_neighbours(grid, r, c):
    for dr, dc in DIRECTIONS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
            yield nr, nc

function buildUndirected(edges) {       // Map<node, node[]>, O(V + E)
  const graph = new Map();
  const add = (a, b) => {
    if (!graph.has(a)) graph.set(a, []);
    graph.get(a).push(b);
  };
  for (const [a, b] of edges) {
    add(a, b);
    add(b, a);                          // omit for a DIRECTED graph
  }
  return graph;
}

function buildWeighted(edges) {         // edges: [a, b, weight]
  const graph = new Map();
  const add = (a, b, w) => {
    if (!graph.has(a)) graph.set(a, []);
    graph.get(a).push([b, w]);
  };
  for (const [a, b, w] of edges) {
    add(a, b, w);
    add(b, a, w);
  }
  return graph;
}

function buildMatrix(n, edges) {        // O(V^2)
  const matrix = Array.from({ length: n }, () => new Array(n).fill(0));
  for (const [a, b] of edges) {
    matrix[a][b] = 1;
    matrix[b][a] = 1;
  }
  return matrix;
}

// A grid is a graph with implicit edges.
const DIRECTIONS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

function* gridNeighbours(grid, r, c) {
  for (const [dr, dc] of DIRECTIONS) {
    const nr = r + dr;
    const nc = c + dc;
    if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length) {
      yield [nr, nc];
    }
  }
}

from collections import deque

def bfs(graph, start):
    """Visit order plus the distance (in edges) from start. O(V + E)."""
    visited = {start}
    dist = {start: 0}
    order = []
    q = deque([start])

    while q:
        node = q.popleft()              # OLDEST first -> breadth first
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)  # mark on ENQUEUE, not on dequeue,
                dist[neighbour] = dist[node] + 1   # or nodes enter twice
                q.append(neighbour)

    return order, dist


def dfs_iterative(graph, start):
    """Same shape, but a stack. O(V + E)."""
    visited = set()
    order = []
    stack = [start]

    while stack:
        node = stack.pop()              # NEWEST first -> depth first
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in visited:
                stack.append(neighbour)

    return order


def shortest_path(graph, start, goal):
    """BFS + parent pointers. Optimal for UNWEIGHTED graphs only."""
    if start == goal:
        return [start]
    parent = {start: None}
    q = deque([start])

    while q:
        node = q.popleft()
        for neighbour in graph[node]:
            if neighbour in parent:
                continue
            parent[neighbour] = node
            if neighbour == goal:       # first time we see it = shortest
                path = [goal]
                while path[-1] is not None and parent[path[-1]] is not None:
                    path.append(parent[path[-1]])
                return path[::-1]
            q.append(neighbour)

    return None                         # unreachable


def connected_components(graph, nodes):
    """How many separate pieces does the graph have?"""
    seen, components = set(), 0
    for node in nodes:
        if node in seen:
            continue
        components += 1
        stack = [node]
        while stack:                    # flood the whole component
            cur = stack.pop()
            if cur in seen:
                continue
            seen.add(cur)
            stack.extend(graph[cur])
    return components

function bfs(graph, start) {            // O(V + E)
  const visited = new Set([start]);
  const dist = new Map([[start, 0]]);
  const order = [];
  const queue = [start];
  let head = 0;                         // index instead of shift() - O(1)

  while (head < queue.length) {
    const node = queue[head++];         // OLDEST first
    order.push(node);
    for (const neighbour of graph.get(node) ?? []) {
      if (visited.has(neighbour)) continue;
      visited.add(neighbour);           // mark on ENQUEUE
      dist.set(neighbour, dist.get(node) + 1);
      queue.push(neighbour);
    }
  }
  return { order, dist };
}

function dfsIterative(graph, start) {   // O(V + E)
  const visited = new Set();
  const order = [];
  const stack = [start];

  while (stack.length) {
    const node = stack.pop();           // NEWEST first
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    const neighbours = graph.get(node) ?? [];
    for (let i = neighbours.length - 1; i >= 0; i--) {
      if (!visited.has(neighbours[i])) stack.push(neighbours[i]);
    }
  }
  return order;
}

function shortestPath(graph, start, goal) {   // unweighted only
  if (start === goal) return [start];
  const parent = new Map([[start, null]]);
  const queue = [start];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    for (const neighbour of graph.get(node) ?? []) {
      if (parent.has(neighbour)) continue;
      parent.set(neighbour, node);
      if (neighbour === goal) {         // first sighting = shortest
        const path = [goal];
        while (parent.get(path.at(-1)) !== null) path.push(parent.get(path.at(-1)));
        return path.reverse();
      }
      queue.push(neighbour);
    }
  }
  return null;                          // unreachable
}

from collections import deque

def minutes_to_rot_all(grid):
    """2 = rotten, 1 = fresh, 0 = empty. Returns minutes, or -1."""
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c, 0))     # EVERY rotten orange is a source
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while q:
        r, c, t = q.popleft()
        minutes = max(minutes, t)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2        # mark immediately to avoid duplicates
                fresh -= 1
                q.append((nr, nc, t + 1))

    return minutes if fresh == 0 else -1


print(minutes_to_rot_all([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))    # 4

function minutesToRotAll(grid) {        // 2 rotten, 1 fresh, 0 empty
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let head = 0;
  let fresh = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c, 0]);   // every source at once
      else if (grid[r][c] === 1) fresh++;
    }
  }

  let minutes = 0;
  while (head < queue.length) {
    const [r, c, t] = queue[head++];
    minutes = Math.max(minutes, t);
    for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;               // mark on enqueue
        fresh--;
        queue.push([nr, nc, t + 1]);
      }
    }
  }
  return fresh === 0 ? minutes : -1;
}

console.log(minutesToRotAll([[2, 1, 1], [1, 1, 0], [0, 1, 1]]));   // 4

from collections import deque, defaultdict

def topo_sort_kahn(n, edges):
    """BFS-based. Returns an order, or None if there is a cycle. O(V + E)."""
    graph = defaultdict(list)
    in_degree = [0] * n
    for a, b in edges:              # edge a -> b means a must come first
        graph[a].append(b)
        in_degree[b] += 1

    # Anything with no unmet dependency can start immediately.
    q = deque(v for v in range(n) if in_degree[v] == 0)
    order = []

    while q:
        node = q.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1       # one dependency satisfied
            if in_degree[neighbour] == 0:
                q.append(neighbour)

    # If we could not place every vertex, the leftovers form a cycle.
    return order if len(order) == n else None


def topo_sort_dfs(n, edges):
    """DFS-based: a node is appended once all its descendants are done."""
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)

    WHITE, GREY, BLACK = 0, 1, 2        # unvisited / on the stack / finished
    colour = [WHITE] * n
    order = []

    def visit(node):
        if colour[node] == GREY:
            return False                # back edge -> cycle
        if colour[node] == BLACK:
            return True                 # already processed
        colour[node] = GREY
        for neighbour in graph[node]:
            if not visit(neighbour):
                return False
        colour[node] = BLACK
        order.append(node)              # post-order = reverse topological
        return True

    for v in range(n):
        if not visit(v):
            return None
    return order[::-1]


# 0 -> 1 -> 3, 0 -> 2 -> 3
print(topo_sort_kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))   # [0, 1, 2, 3]
print(topo_sort_kahn(2, [(0, 1), (1, 0)]))                   # None - cycle

function topoSortKahn(n, edges) {       // O(V + E), null if cyclic
  const graph = Array.from({ length: n }, () => []);
  const inDegree = new Array(n).fill(0);
  for (const [a, b] of edges) {         // a must come before b
    graph[a].push(b);
    inDegree[b]++;
  }

  const queue = [];
  for (let v = 0; v < n; v++) if (inDegree[v] === 0) queue.push(v);

  const order = [];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const neighbour of graph[node]) {
      if (--inDegree[neighbour] === 0) queue.push(neighbour);
    }
  }
  return order.length === n ? order : null;   // leftovers mean a cycle
}

function topoSortDfs(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) graph[a].push(b);

  const WHITE = 0;
  const GREY = 1;
  const BLACK = 2;
  const colour = new Array(n).fill(WHITE);
  const order = [];

  const visit = (node) => {
    if (colour[node] === GREY) return false;    // back edge -> cycle
    if (colour[node] === BLACK) return true;
    colour[node] = GREY;
    for (const neighbour of graph[node]) if (!visit(neighbour)) return false;
    colour[node] = BLACK;
    order.push(node);                            // post-order
    return true;
  };

  for (let v = 0; v < n; v++) if (!visit(v)) return null;
  return order.reverse();
}

console.log(topoSortKahn(4, [[0, 1], [0, 2], [1, 3], [2, 3]]));  // [0,1,2,3]
console.log(topoSortKahn(2, [[0, 1], [1, 0]]));                  // null

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """graph: {node: [(neighbour, weight)]}. O((V + E) log V)."""
    dist = defaultdict(lambda: float("inf"))
    dist[start] = 0
    prev = {}
    visited = set()
    pq = [(0, start)]           # (distance, node) - the heap orders by distance

    while pq:
        d, node = heapq.heappop(pq)
        if node in visited:
            continue            # a stale entry from an earlier, worse path
        visited.add(node)       # this distance is now final

        for neighbour, weight in graph[node]:
            candidate = d + weight
            if candidate < dist[neighbour]:     # relax
                dist[neighbour] = candidate
                prev[neighbour] = node
                heapq.heappush(pq, (candidate, neighbour))
                # We do not remove the old entry; we just skip it above.
                # This "lazy deletion" is simpler and still O(E log V).

    return dict(dist), prev


def rebuild_path(prev, start, goal):
    path, node = [], goal
    while node != start:
        path.append(node)
        node = prev.get(node)
        if node is None:
            return None         # unreachable
    path.append(start)
    return path[::-1]


graph = {
    "A": [("B", 4), ("C", 2)],
    "B": [("A", 4), ("C", 1), ("D", 5)],
    "C": [("A", 2), ("B", 1), ("D", 8), ("F", 10)],
    "D": [("B", 5), ("C", 8), ("E", 2), ("F", 6)],
    "E": [("D", 2), ("F", 3)],
    "F": [("C", 10), ("D", 6), ("E", 3)],
}
dist, prev = dijkstra(graph, "A")
print(dist["F"])                            # 12
print(rebuild_path(prev, "A", "F"))         # ['A', 'C', 'B', 'D', 'F']

// Uses the Heap class from section 19.
function dijkstra(graph, start) {       // O((V + E) log V)
  const dist = new Map([[start, 0]]);
  const prev = new Map();
  const visited = new Set();
  const pq = new Heap((a, b) => a[0] - b[0]);   // [distance, node]
  pq.push([0, start]);

  while (pq.size) {
    const [d, node] = pq.pop();
    if (visited.has(node)) continue;    // stale entry - lazy deletion
    visited.add(node);                  // distance is now final

    for (const [neighbour, weight] of graph.get(node) ?? []) {
      const candidate = d + weight;
      if (candidate < (dist.get(neighbour) ?? Infinity)) {   // relax
        dist.set(neighbour, candidate);
        prev.set(neighbour, node);
        pq.push([candidate, neighbour]);
      }
    }
  }
  return { dist, prev };
}

function rebuildPath(prev, start, goal) {
  const path = [];
  let node = goal;
  while (node !== start) {
    path.push(node);
    node = prev.get(node);
    if (node === undefined) return null;    // unreachable
  }
  path.push(start);
  return path.reverse();
}

const graph = new Map([
  ["A", [["B", 4], ["C", 2]]],
  ["B", [["A", 4], ["C", 1], ["D", 5]]],
  ["C", [["A", 2], ["B", 1], ["D", 8], ["F", 10]]],
  ["D", [["B", 5], ["C", 8], ["E", 2], ["F", 6]]],
  ["E", [["D", 2], ["F", 3]]],
  ["F", [["C", 10], ["D", 6], ["E", 3]]],
]);
const { dist, prev } = dijkstra(graph, "A");
console.log(dist.get("F"));                     // 12
console.log(rebuildPath(prev, "A", "F"));       // ['A','C','B','D','F']

def bellman_ford(n, edges, start):
    """edges = [(u, v, w)]. Returns (dist, None) or (None, 'negative cycle')."""
    dist = [float("inf")] * n
    dist[start] = 0

    # After k rounds every shortest path using <= k edges is correct.
    # A simple path has at most n - 1 edges, so n - 1 rounds suffice.
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                       # early exit: already stable

    # One more round: any further improvement means a negative cycle.
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None, "negative cycle"

    return dist, None


def floyd_warshall(matrix):
    """matrix[i][j] = weight or inf. All-pairs shortest paths. O(V^3)."""
    n = len(matrix)
    dist = [row[:] for row in matrix]

    # k is the highest-numbered intermediate vertex allowed so far.
    # The loop order matters: k MUST be outermost.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

function bellmanFord(n, edges, start) { // edges: [u, v, w]
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  for (let round = 0; round < n - 1; round++) {
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        changed = true;
      }
    }
    if (!changed) break;                // already stable
  }

  for (const [u, v, w] of edges) {      // one extra round detects negatives
    if (dist[u] + w < dist[v]) return { dist: null, error: "negative cycle" };
  }
  return { dist, error: null };
}

function floydWarshall(matrix) {        // O(V^3) all pairs
  const n = matrix.length;
  const dist = matrix.map((row) => [...row]);

  for (let k = 0; k < n; k++) {         // k MUST be the outer loop
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

import heapq

def kruskal(n, edges):
    """edges = [(weight, u, v)]. O(E log E), dominated by the sort."""
    uf = UnionFind(n)                   # from section 21
    mst, total = [], 0

    for weight, u, v in sorted(edges):  # cheapest first
        if uf.union(u, v):              # False means it would form a cycle
            mst.append((u, v, weight))
            total += weight
            if len(mst) == n - 1:
                break                   # a spanning tree has exactly n-1 edges

    return (mst, total) if len(mst) == n - 1 else (None, None)  # disconnected


def prim(graph, start):
    """graph: {node: [(neighbour, weight)]}. O(E log V)."""
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst, total = [], 0

    while pq and len(visited) < len(graph):
        weight, u, v = heapq.heappop(pq)
        if v in visited:
            continue                    # both ends already in the tree
        visited.add(v)
        mst.append((u, v, weight))
        total += weight
        for neighbour, w in graph[v]:   # extend the frontier
            if neighbour not in visited:
                heapq.heappush(pq, (w, v, neighbour))

    return mst, total


edges = [(4, 0, 1), (2, 0, 2), (1, 1, 2), (5, 1, 3), (8, 2, 3)]
print(kruskal(4, edges))    # ([(1, 2, 1), (0, 2, 2), (1, 3, 5)], 8)

function kruskal(n, edges) {            // edges: [weight, u, v]
  const uf = new UnionFind(n);          // from section 21
  const sorted = [...edges].sort((a, b) => a[0] - b[0]);
  const mst = [];
  let total = 0;

  for (const [weight, u, v] of sorted) {
    if (uf.union(u, v)) {               // false = would create a cycle
      mst.push([u, v, weight]);
      total += weight;
      if (mst.length === n - 1) break;
    }
  }
  return mst.length === n - 1 ? { mst, total } : null;   // disconnected
}

function prim(graph, start) {           // O(E log V), uses Heap from §19
  const visited = new Set([start]);
  const pq = new Heap((a, b) => a[0] - b[0]);
  for (const [v, w] of graph.get(start) ?? []) pq.push([w, start, v]);

  const mst = [];
  let total = 0;

  while (pq.size && visited.size < graph.size) {
    const [weight, u, v] = pq.pop();
    if (visited.has(v)) continue;       // already in the tree
    visited.add(v);
    mst.push([u, v, weight]);
    total += weight;
    for (const [neighbour, w] of graph.get(v) ?? []) {
      if (!visited.has(neighbour)) pq.push([w, v, neighbour]);
    }
  }
  return { mst, total };
}

console.log(kruskal(4, [[4, 0, 1], [2, 0, 2], [1, 1, 2], [5, 1, 3], [8, 2, 3]]));
// { mst: [[1,2,1],[0,2,2],[1,3,5]], total: 8 }

def max_meetings(intervals):
    """Most non-overlapping intervals. Sort by END time - that is the trick.
    O(n log n). Finishing earliest leaves the most room for everything else."""
    intervals.sort(key=lambda iv: iv[1])
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:       # no clash with the previous choice
            count += 1
            last_end = end
    return count


def can_jump(nums):
    """nums[i] = max jump length from i. Can we reach the end? O(n)."""
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:               # this index is unreachable
            return False
        reach = max(reach, i + jump)
    return True


def min_platforms(arrivals, departures):
    """Fewest train platforms needed. Classic two-pointer greedy."""
    arrivals, departures = sorted(arrivals), sorted(departures)
    i = j = platforms = best = 0
    while i < len(arrivals):
        if arrivals[i] <= departures[j]:
            platforms += 1          # a train arrives before one leaves
            best = max(best, platforms)
            i += 1
        else:
            platforms -= 1          # a platform frees up
            j += 1
    return best


print(max_meetings([(1, 3), (2, 5), (4, 7), (6, 8)]))   # 2
print(can_jump([2, 3, 1, 1, 4]))                        # True
print(can_jump([3, 2, 1, 0, 4]))                        # False

function maxMeetings(intervals) {       // sort by END time, O(n log n)
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let count = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {             // no clash
      count++;
      lastEnd = end;
    }
  }
  return count;
}

function canJump(nums) {                // O(n)
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;        // unreachable index
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

function minPlatforms(arrivals, departures) {
  const a = [...arrivals].sort((x, y) => x - y);
  const d = [...departures].sort((x, y) => x - y);
  let i = 0;
  let j = 0;
  let platforms = 0;
  let best = 0;
  while (i < a.length) {
    if (a[i] <= d[j]) {
      best = Math.max(best, ++platforms);   // a train arrives
      i++;
    } else {
      platforms--;                          // a platform frees up
      j++;
    }
  }
  return best;
}

console.log(maxMeetings([[1, 3], [2, 5], [4, 7], [6, 8]]));   // 2
console.log(canJump([2, 3, 1, 1, 4]), canJump([3, 2, 1, 0, 4])); // true false

import random

def quickselect(nums, k):
    """k-th smallest (0-indexed) in O(n) average. Like quicksort, but we
    only recurse into the ONE side that can contain the answer, which turns
    n + n/2 + n/4 + ... into 2n."""
    nums = list(nums)
    lo, hi = 0, len(nums) - 1
    while True:
        if lo == hi:
            return nums[lo]
        pivot_index = random.randint(lo, hi)    # randomise to avoid O(n^2)
        nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]
        pivot = nums[hi]

        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]

        if k == store:
            return nums[store]
        if k < store:
            hi = store - 1              # answer is on the left
        else:
            lo = store + 1              # answer is on the right


def power(base, exponent):
    """base^exponent in O(log n) multiplications instead of O(n)."""
    result = 1
    while exponent > 0:
        if exponent & 1:                # odd exponent -> take one factor out
            result *= base
        base *= base                    # square the base
        exponent >>= 1                  # halve the exponent
    return result


def count_inversions(nums):
    """Pairs (i < j) with nums[i] > nums[j]. O(n log n) via merge sort:
    when we take from the right run, every remaining left element is an
    inversion with it - counted in one operation instead of one by one."""
    def sort(a):
        if len(a) <= 1:
            return a, 0
        mid = len(a) // 2
        left, x = sort(a[:mid])
        right, y = sort(a[mid:])
        merged, z = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
                z += len(left) - i      # the whole rest of `left` is inverted
        merged.extend(left[i:]); merged.extend(right[j:])
        return merged, x + y + z

    return sort(list(nums))[1]


print(quickselect([7, 2, 9, 4, 1, 8], 2))       # 4  (third smallest)
print(power(2, 30))                             # 1073741824
print(count_inversions([2, 4, 1, 3, 5]))        # 3

function quickselect(input, k) {        // k-th smallest, O(n) average
  const nums = [...input];
  let lo = 0;
  let hi = nums.length - 1;
  const swap = (a, b) => { [nums[a], nums[b]] = [nums[b], nums[a]]; };

  while (true) {
    if (lo === hi) return nums[lo];
    swap(lo + Math.floor(Math.random() * (hi - lo + 1)), hi);   // random pivot
    const pivot = nums[hi];

    let store = lo;
    for (let i = lo; i < hi; i++) if (nums[i] < pivot) swap(i, store++);
    swap(store, hi);

    if (k === store) return nums[store];
    if (k < store) hi = store - 1;      // recurse left only
    else lo = store + 1;                // recurse right only
  }
}

function power(base, exponent) {        // O(log n) multiplications
  let result = 1n;
  let b = BigInt(base);
  let e = BigInt(exponent);
  while (e > 0n) {
    if (e & 1n) result *= b;            // odd -> peel off one factor
    b *= b;                             // square
    e >>= 1n;                           // halve
  }
  return result;
}

function countInversions(input) {       // O(n log n) via merge sort
  const sort = (a) => {
    if (a.length <= 1) return [a, 0];
    const mid = a.length >> 1;
    const [left, x] = sort(a.slice(0, mid));
    const [right, y] = sort(a.slice(mid));
    const merged = [];
    let i = 0;
    let j = 0;
    let z = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) merged.push(left[i++]);
      else {
        merged.push(right[j++]);
        z += left.length - i;           // all remaining left values invert
      }
    }
    return [[...merged, ...left.slice(i), ...right.slice(j)], x + y + z];
  };
  return sort([...input])[1];
}

console.log(quickselect([7, 2, 9, 4, 1, 8], 2));    // 4
console.log(power(2, 30).toString());               // 1073741824
console.log(countInversions([2, 4, 1, 3, 5]));      // 3

def subsets(nums):
    """All 2^n subsets. At each index: take it or skip it."""
    out, path = [], []

    def go(i):
        if i == len(nums):
            out.append(path[:])         # copy - path keeps mutating
            return
        go(i + 1)                       # skip nums[i]
        path.append(nums[i])            # choose
        go(i + 1)                       # explore
        path.pop()                      # un-choose

    go(0)
    return out


print(len(subsets([1, 2, 3])))      # 8

function subsets(nums) {                // 2^n subsets
  const out = [];
  const path = [];
  const go = (i) => {
    if (i === nums.length) {
      out.push([...path]);              // copy: path keeps mutating
      return;
    }
    go(i + 1);                          // skip
    path.push(nums[i]);                 // choose
    go(i + 1);                          // explore
    path.pop();                         // un-choose
  };
  go(0);
  return out;
}

console.log(subsets([1, 2, 3]).length); // 8

def permutations(nums):
    """All n! orderings, swapping in place."""
    out = []

    def go(start):
        if start == len(nums):
            out.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]     # choose
            go(start + 1)                                   # explore
            nums[start], nums[i] = nums[i], nums[start]     # un-choose

    go(0)
    return out


print(len(permutations([1, 2, 3]))) # 6

function permutations(nums) {           // n! orderings
  const out = [];
  const swap = (a, b) => { [nums[a], nums[b]] = [nums[b], nums[a]]; };
  const go = (start) => {
    if (start === nums.length) {
      out.push([...nums]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      swap(start, i);                   // choose
      go(start + 1);                    // explore
      swap(start, i);                   // un-choose
    }
  };
  go(0);
  return out;
}

console.log(permutations([1, 2, 3]).length);  // 6

def combinations(n, k):
    """C(n, k) combinations, with pruning."""
    out, path = [], []

    def go(start):
        if len(path) == k:
            out.append(path[:])
            return
        # PRUNE: stop early if not enough numbers remain to reach length k.
        for value in range(start, n - (k - len(path)) + 2):
            path.append(value)
            go(value + 1)
            path.pop()

    go(1)
    return out


print(len(combinations(5, 3)))      # 10

function combinations(n, k) {           // C(n, k), with pruning
  const out = [];
  const path = [];
  const go = (start) => {
    if (path.length === k) {
      out.push([...path]);
      return;
    }
    // PRUNE: stop when too few numbers remain to reach length k.
    for (let value = start; value <= n - (k - path.length) + 1; value++) {
      path.push(value);
      go(value + 1);
      path.pop();
    }
  };
  go(1);
  return out;
}

console.log(combinations(5, 3).length);  // 10

def solve_n_queens(n):
    """Count placements of n queens on n x n with no mutual attacks."""
    cols, diag, anti = set(), set(), set()
    count = 0

    def go(row):
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            # Constant-time conflict check thanks to the diagonal identities:
            # cells on a "\" diagonal share row - col; on "/" they share row + col.
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue
            cols.add(col); diag.add(row - col); anti.add(row + col)
            go(row + 1)
            cols.remove(col); diag.remove(row - col); anti.remove(row + col)

    go(0)
    return count


print(solve_n_queens(8))            # 92

function solveNQueens(n) {
  const cols = new Set();
  const diag = new Set();               // row - col
  const anti = new Set();               // row + col
  let count = 0;

  const go = (row) => {
    if (row === n) {
      count++;
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
      cols.add(col); diag.add(row - col); anti.add(row + col);
      go(row + 1);
      cols.delete(col); diag.delete(row - col); anti.delete(row + col);
    }
  };
  go(0);
  return count;
}

console.log(solveNQueens(8));                 // 92

def climb_stairs(n):
    """dp[i] = ways to reach step i. Fibonacci in disguise. O(n)/O(1)."""
    a, b = 1, 1                     # base cases: dp[0] = dp[1] = 1
    for _ in range(n - 1):
        a, b = b, a + b             # dp[i] = dp[i-1] + dp[i-2]
    return b


print(climb_stairs(10))                                     # 89

function climbStairs(n) {               // O(n) time, O(1) space
  let [a, b] = [1, 1];
  for (let i = 1; i < n; i++) [a, b] = [b, a + b];
  return b;
}

console.log(climbStairs(10));                  // 89

def rob(houses):
    """dp[i] = most money from the first i houses, no two adjacent."""
    take, skip = 0, 0
    for money in houses:
        # Taking this house means we must have skipped the previous one.
        take, skip = skip + money, max(skip, take)
    return max(take, skip)          # O(n) time, O(1) space


print(rob([2, 7, 9, 3, 1]))                                 # 12

function rob(houses) {                  // no two adjacent, O(n)/O(1)
  let take = 0;
  let skip = 0;
  for (const money of houses) {
    [take, skip] = [skip + money, Math.max(skip, take)];
  }
  return Math.max(take, skip);
}

console.log(rob([2, 7, 9, 3, 1]));             // 12

def coin_change(coins, amount):
    """Fewest coins summing to amount, or -1. O(amount * len(coins))."""
    INF = float("inf")
    dp = [0] + [INF] * amount       # dp[x] = fewest coins to make x
    for x in range(1, amount + 1):
        for coin in coins:
            if coin <= x and dp[x - coin] + 1 < dp[x]:
                dp[x] = dp[x - coin] + 1
    return -1 if dp[amount] == INF else dp[amount]


print(coin_change([1, 5, 10, 25], 30))                      # 2

function coinChange(coins, amount) {    // O(amount * coins)
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let x = 1; x <= amount; x++) {
    for (const coin of coins) {
      if (coin <= x) dp[x] = Math.min(dp[x], dp[x - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 10, 25], 30));   // 2

def longest_increasing_subsequence(nums):
    """O(n log n) with patience sorting: tails[k] = smallest possible tail
    of an increasing subsequence of length k + 1."""
    from bisect import bisect_left
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)         # x extends the longest subsequence
        else:
            tails[i] = x            # x makes a length-(i+1) tail smaller
    return len(tails)               # NOTE: length only, not the sequence


print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7]))  # 3

function lis(nums) {                    // O(n log n) patience sorting
  const tails = [];                     // tails[k] = smallest tail of length k+1
  for (const x of nums) {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {                   // lower bound
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x;                      // append or replace
  }
  return tails.length;
}

console.log(lis([10, 9, 2, 5, 3, 7]));         // 3

def lcs_length(a, b):
    """Longest common subsequence. O(n*m) time, O(min(n,m)) space here."""
    if len(a) < len(b):
        a, b = b, a                     # keep the shorter string as columns
    prev = [0] * (len(b) + 1)
    for ch_a in a:
        cur = [0] * (len(b) + 1)
        for j, ch_b in enumerate(b, start=1):
            if ch_a == ch_b:
                cur[j] = prev[j - 1] + 1        # characters pair up
            else:
                cur[j] = max(prev[j], cur[j - 1])   # drop one from either side
        prev = cur
    return prev[-1]


print(lcs_length("ABCBDAB", "BDCABA"))                  # 4

function lcsLength(a, b) {              // O(n*m) time, O(m) space
  let prev = new Array(b.length + 1).fill(0);
  for (const chA of a) {
    const cur = new Array(b.length + 1).fill(0);
    for (let j = 1; j <= b.length; j++) {
      if (chA === b[j - 1]) cur[j] = prev[j - 1] + 1;       // pair up
      else cur[j] = Math.max(prev[j], cur[j - 1]);          // drop one
    }
    prev = cur;
  }
  return prev[b.length];
}

console.log(lcsLength("ABCBDAB", "BDCABA"));               // 4

def edit_distance(a, b):
    """Levenshtein: fewest insert/delete/replace to turn a into b. O(n*m)."""
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i                    # delete every character of a
    for j in range(m + 1):
        dp[0][j] = j                    # insert every character of b

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]     # free - characters match
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],       # delete a[i-1]
                    dp[i][j - 1],       # insert b[j-1]
                    dp[i - 1][j - 1],   # replace
                )
    return dp[n][m]


print(edit_distance("kitten", "sitting"))               # 3

function editDistance(a, b) {           // Levenshtein, O(n*m)
  const n = a.length;
  const m = b.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

  for (let i = 0; i <= n; i++) dp[i][0] = i;     // delete everything
  for (let j = 0; j <= m; j++) dp[0][j] = j;     // insert everything

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];   // free
      else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
    }
  }
  return dp[n][m];
}

console.log(editDistance("kitten", "sitting"));            // 3

def knapsack(weights, values, capacity):
    """0/1 knapsack, space-optimised to one row. O(n*W) time, O(W) space."""
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Iterate capacity DOWNWARDS so each item is used at most once.
        # Going upwards would let an item be reused -> unbounded knapsack.
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]


print(knapsack([1, 3, 4, 2], [15, 20, 30, 18], 6))      # 63

function knapsack(weights, values, capacity) {  // O(n*W) time, O(W) space
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    // DOWNWARDS so each item is used at most once.
    for (let c = capacity; c >= weights[i]; c--) {
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

console.log(knapsack([1, 3, 4, 2], [15, 20, 30, 18], 6));  // 63

x = 0b1011      # 11

# --- single-bit operations ---
x | (1 << 2)        # set bit 2       -> 0b1111
x & ~(1 << 1)       # clear bit 1     -> 0b1001
x ^ (1 << 0)        # toggle bit 0    -> 0b1010
(x >> 3) & 1        # read bit 3      -> 1

# --- whole-value idioms ---
x & (x - 1)         # clear the lowest set bit
x & -x              # isolate the lowest set bit
x & (x - 1) == 0    # is x a power of two? (careful: also true for 0)
bin(x).count("1")   # population count
x.bit_length()      # 4 - position of the highest set bit

def single_number(nums):
    """Every value appears twice except one. XOR cancels the pairs. O(n)/O(1)."""
    result = 0
    for value in nums:
        result ^= value
    return result

def count_bits(x):
    """Brian Kernighan: loops once per SET bit, not once per bit."""
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

def all_subsets(items):
    """Enumerate 2^n subsets by counting in binary."""
    n = len(items)
    for mask in range(1 << n):
        yield [items[i] for i in range(n) if mask >> i & 1]

def swap_without_temp(a, b):
    a ^= b; b ^= a; a ^= b      # cute, but never do this in real code
    return a, b

print(single_number([4, 1, 2, 1, 2]))       # 4
print(list(all_subsets(["a", "b"])))        # [[], ['a'], ['b'], ['a','b']]

let x = 0b1011;         // 11

// --- single-bit operations ---
x | (1 << 2);           // set bit 2
x & ~(1 << 1);          // clear bit 1
x ^ (1 << 0);           // toggle bit 0
(x >> 3) & 1;           // read bit 3

// --- whole-value idioms ---
x & (x - 1);            // clear the lowest set bit
x & -x;                 // isolate the lowest set bit
(x & (x - 1)) === 0;    // power of two (also true for 0)
Math.clz32(x);          // count leading zeros -> highest set bit position

function singleNumber(nums) {           // XOR cancels pairs, O(n)/O(1)
  let result = 0;
  for (const value of nums) result ^= value;
  return result;
}

function countBits(x) {                 // Brian Kernighan
  let count = 0;
  while (x) {
    x &= x - 1;
    count++;
  }
  return count;
}

function* allSubsets(items) {           // 2^n subsets by counting in binary
  for (let mask = 0; mask < 1 << items.length; mask++) {
    yield items.filter((_, i) => (mask >> i) & 1);
  }
}

console.log(singleNumber([4, 1, 2, 1, 2]));   // 4
console.log([...allSubsets(["a", "b"])]);     // [[], ['a'], ['b'], ['a','b']]

from math import gcd, comb, isqrt

def euclid(a, b):
    """gcd via repeated remainder. O(log min(a, b)) - Euclid, ~300 BC."""
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """Divide first to avoid overflow in fixed-width languages."""
    return a // gcd(a, b) * b


def sieve(n):
    """All primes up to n. O(n log log n) time, O(n) space."""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    # Start crossing out at p*p: smaller multiples already have a smaller factor.
    for p in range(2, isqrt(n) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
    return [i for i, prime in enumerate(is_prime) if prime]


def prime_factors(n):
    """O(sqrt(n)). Any factor above sqrt(n) can only appear once."""
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors


def mod_pow(base, exponent, mod):
    """(base ** exponent) % mod without ever building a huge number."""
    result = 1
    base %= mod
    while exponent > 0:
        if exponent & 1:
            result = result * base % mod
        base = base * base % mod
        exponent >>= 1
    return result

# Python has these built in: pow(base, exp, mod), math.comb, math.gcd
print(sieve(30))                        # [2,3,5,7,11,13,17,19,23,29]
print(prime_factors(360))               # [2, 2, 2, 3, 3, 5]
print(mod_pow(2, 100, 1_000_000_007))   # 976371285
print(comb(10, 3))                      # 120

function gcd(a, b) {                    // O(log min(a, b))
  while (b) [a, b] = [b, a % b];
  return a;
}

const lcm = (a, b) => (a / gcd(a, b)) * b;   // divide first

function sieve(n) {                     // O(n log log n)
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let p = 2; p * p <= n; p++) {
    if (!isPrime[p]) continue;
    for (let m = p * p; m <= n; m += p) isPrime[m] = false;  // start at p*p
  }
  return isPrime.flatMap((prime, i) => (prime ? [i] : []));
}

function primeFactors(n) {              // O(sqrt(n))
  const factors = [];
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      factors.push(d);
      n /= d;
    }
  }
  if (n > 1) factors.push(n);
  return factors;
}

function modPow(base, exponent, mod) {  // BigInt avoids overflow past 2^53
  let result = 1n;
  let b = BigInt(base) % BigInt(mod);
  let e = BigInt(exponent);
  const m = BigInt(mod);
  while (e > 0n) {
    if (e & 1n) result = (result * b) % m;
    b = (b * b) % m;
    e >>= 1n;
  }
  return result;
}

console.log(sieve(30));                            // [2,3,...,29]
console.log(primeFactors(360));                    // [2,2,2,3,3,5]
console.log(modPow(2, 100, 1000000007).toString()); // 976371285

class Fenwick:
    """Prefix sums with point updates, both O(log n). 1-indexed internally."""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        """Add delta at index i (0-based). O(log n)."""
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i             # jump to the next node that covers i

    def prefix(self, i):
        """Sum of the first i elements (0-based exclusive). O(log n)."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i             # strip the lowest set bit
        return total

    def range_sum(self, lo, hi):
        """Inclusive [lo, hi]."""
        return self.prefix(hi + 1) - self.prefix(lo)


fw = Fenwick(8)
for i, v in enumerate([3, 1, 4, 1, 5, 9, 2, 6]):
    fw.update(i, v)
print(fw.range_sum(2, 5))       # 19
fw.update(3, 10)                # nums[3] becomes 11
print(fw.range_sum(2, 5))       # 29 - no rebuild needed

class Fenwick {
  constructor(n) {
    this.n = n;
    this.tree = new Array(n + 1).fill(0);
  }

  update(i, delta) {                    // O(log n), i is 0-based
    for (let k = i + 1; k <= this.n; k += k & -k) this.tree[k] += delta;
  }

  prefix(i) {                           // sum of first i elements, O(log n)
    let total = 0;
    for (let k = i; k > 0; k -= k & -k) total += this.tree[k];
    return total;
  }

  rangeSum(lo, hi) {                    // inclusive
    return this.prefix(hi + 1) - this.prefix(lo);
  }
}

const fw = new Fenwick(8);
[3, 1, 4, 1, 5, 9, 2, 6].forEach((v, i) => fw.update(i, v));
console.log(fw.rangeSum(2, 5));         // 19
fw.update(3, 10);
console.log(fw.rangeSum(2, 5));         // 29

class SegmentTree:
    """Point update, range query. O(n) build, O(log n) per operation.
    Pass any associative combine: min, max, gcd, sum, ..."""

    def __init__(self, values, combine=min, identity=float("inf")):
        self.n = len(values)
        self.combine = combine
        self.identity = identity
        # Leaves live at [n, 2n); internal node i has children 2i and 2i+1.
        self.tree = [identity] * self.n + list(values)
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = combine(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, value):
        i += self.n
        self.tree[i] = value
        i //= 2
        while i:                        # repair the ancestors
            self.tree[i] = self.combine(self.tree[2 * i], self.tree[2 * i + 1])
            i //= 2

    def query(self, lo, hi):
        """Half-open [lo, hi). Walk up from both ends, folding as we go."""
        result = self.identity
        lo += self.n
        hi += self.n
        while lo < hi:
            if lo & 1:                  # lo is a right child - take it
                result = self.combine(result, self.tree[lo])
                lo += 1
            if hi & 1:                  # hi is a right child - take hi-1
                hi -= 1
                result = self.combine(result, self.tree[hi])
            lo //= 2
            hi //= 2
        return result


st = SegmentTree([5, 2, 8, 1, 9, 3], combine=min, identity=float("inf"))
print(st.query(1, 5))       # 1  -> min of [2, 8, 1, 9]
st.update(3, 7)
print(st.query(1, 5))       # 2

class SegmentTree {
  constructor(values, combine = Math.min, identity = Infinity) {
    this.n = values.length;
    this.combine = combine;
    this.identity = identity;
    this.tree = [...new Array(this.n).fill(identity), ...values];
    for (let i = this.n - 1; i > 0; i--) {
      this.tree[i] = combine(this.tree[2 * i], this.tree[2 * i + 1]);
    }
  }

  update(i, value) {                    // O(log n)
    let k = i + this.n;
    this.tree[k] = value;
    for (k >>= 1; k > 0; k >>= 1) {
      this.tree[k] = this.combine(this.tree[2 * k], this.tree[2 * k + 1]);
    }
  }

  query(lo, hi) {                       // half-open [lo, hi), O(log n)
    let result = this.identity;
    let l = lo + this.n;
    let r = hi + this.n;
    while (l < r) {
      if (l & 1) result = this.combine(result, this.tree[l++]);
      if (r & 1) result = this.combine(result, this.tree[--r]);
      l >>= 1;
      r >>= 1;
    }
    return result;
  }
}

const st = new SegmentTree([5, 2, 8, 1, 9, 3]);
console.log(st.query(1, 5));            // 1
st.update(3, 7);
console.log(st.query(1, 5));            // 2

// Same class, different operation:
const sums = new SegmentTree([5, 2, 8, 1], (a, b) => a + b, 0);
console.log(sums.query(0, 4));          // 16

def build_lps(pattern):
    """lps[i] = length of the longest proper prefix of pattern[:i+1]
    that is also a suffix of it. O(m)."""
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]    # fall back, do not restart
        else:
            lps[i] = 0
            i += 1
    return lps


def kmp_search(text, pattern):
    """All start indices of pattern in text. O(n + m)."""
    if not pattern:
        return []
    lps = build_lps(pattern)
    matches = []
    j = 0                               # index into pattern

    for i, ch in enumerate(text):       # i never goes backwards
        while j and ch != pattern[j]:
            j = lps[j - 1]              # slide the pattern, keep the overlap
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = lps[j - 1]              # continue for overlapping matches

    return matches


def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
    """Rolling hash: compare cheap hashes, verify only on a hit. O(n + m)."""
    n, m = len(text), len(pattern)
    if m > n:
        return []

    high = pow(base, m - 1, mod)        # value of the leading digit
    pattern_hash = text_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        text_hash = (text_hash * base + ord(text[i])) % mod

    matches = []
    for i in range(n - m + 1):
        # Hash equality can be a collision, so always verify the substring.
        if text_hash == pattern_hash and text[i:i + m] == pattern:
            matches.append(i)
        if i < n - m:
            # Roll: drop the leftmost character, append the next one. O(1).
            text_hash = ((text_hash - ord(text[i]) * high) * base
                         + ord(text[i + m])) % mod
    return matches


print(kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))   # [10]
print(rabin_karp("abracadabra", "abra"))                # [0, 7]

function buildLps(pattern) {            // O(m)
  const lps = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) lps[i++] = ++length;
    else if (length) length = lps[length - 1];   // fall back, do not restart
    else lps[i++] = 0;
  }
  return lps;
}

function kmpSearch(text, pattern) {     // O(n + m)
  if (!pattern) return [];
  const lps = buildLps(pattern);
  const matches = [];
  let j = 0;

  for (let i = 0; i < text.length; i++) {   // i never moves backwards
    while (j && text[i] !== pattern[j]) j = lps[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) {
      matches.push(i - j + 1);
      j = lps[j - 1];                   // allow overlapping matches
    }
  }
  return matches;
}

function rabinKarp(text, pattern, base = 256n, mod = 1000000007n) {
  const n = text.length;
  const m = pattern.length;
  if (m > n) return [];

  let high = 1n;
  for (let i = 0; i < m - 1; i++) high = (high * base) % mod;

  let patternHash = 0n;
  let textHash = 0n;
  for (let i = 0; i < m; i++) {
    patternHash = (patternHash * base + BigInt(pattern.charCodeAt(i))) % mod;
    textHash = (textHash * base + BigInt(text.charCodeAt(i))) % mod;
  }

  const matches = [];
  for (let i = 0; i + m <= n; i++) {
    // Verify on a hash hit - collisions are possible.
    if (textHash === patternHash && text.slice(i, i + m) === pattern) matches.push(i);
    if (i + m < n) {
      textHash = (textHash - BigInt(text.charCodeAt(i)) * high) * base
        + BigInt(text.charCodeAt(i + m));
      textHash = ((textHash % mod) + mod) % mod;   // keep it non-negative
    }
  }
  return matches;
}

console.log(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"));  // [10]
console.log(rabinKarp("abracadabra", "abra"));               // [0, 7]

def longest_palindrome(s):
    """O(n^2) time, O(1) space. Try every possible centre."""
    if not s:
        return ""
    best_start, best_len = 0, 1

    def expand(lo, hi):
        nonlocal best_start, best_len
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        length = hi - lo - 1            # we overshot by one on both sides
        if length > best_len:
            best_start, best_len = lo + 1, length

    for i in range(len(s)):
        expand(i, i)        # odd-length palindromes centred on a character
        expand(i, i + 1)    # even-length palindromes centred on a gap

    return s[best_start:best_start + best_len]


print(longest_palindrome("babad"))      # 'bab' (or 'aba')
print(longest_palindrome("cbbd"))       # 'bb'

function longestPalindrome(s) {         // O(n^2) time, O(1) space
  if (!s) return "";
  let bestStart = 0;
  let bestLen = 1;

  const expand = (lo, hi) => {
    while (lo >= 0 && hi < s.length && s[lo] === s[hi]) {
      lo--;
      hi++;
    }
    const length = hi - lo - 1;         // overshot by one on each side
    if (length > bestLen) {
      bestStart = lo + 1;
      bestLen = length;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i);                       // odd length
    expand(i, i + 1);                   // even length
  }
  return s.slice(bestStart, bestStart + bestLen);
}

console.log(longestPalindrome("babad"));   // 'bab'
console.log(longestPalindrome("cbbd"));    // 'bb'

def merge_intervals(intervals):
    """Combine every overlapping pair. O(n log n)."""
    if not intervals:
        return []
    intervals = sorted(intervals)       # by start, then end
    merged = [list(intervals[0])]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:      # overlaps the current block
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end]) # disjoint - start a new block
    return merged


def insert_interval(intervals, new):
    """Insert into an already-sorted, non-overlapping list. O(n)."""
    out, i, n = [], 0, len(intervals)
    start, end = new

    while i < n and intervals[i][1] < start:     # entirely before
        out.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= end:      # overlapping - absorb
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    out.append([start, end])
    out.extend(intervals[i:])                   # entirely after
    return out


def max_concurrent(intervals):
    """Peak number of simultaneous intervals - the sweep line. O(n log n)."""
    events = []
    for start, end in intervals:
        events.append((start, 1))       # someone arrives
        events.append((end, -1))        # someone leaves
    # Ends sort before starts at the same instant, so touching intervals
    # ([1,2] and [2,3]) do not count as overlapping.
    events.sort(key=lambda e: (e[0], e[1]))

    active = best = 0
    for _, delta in events:
        active += delta
        best = max(best, active)
    return best


print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
print(max_concurrent([[0, 30], [5, 10], [15, 20]]))     # 2

function mergeIntervals(intervals) {    // O(n log n)
  if (!intervals.length) return [];
  const sorted = [...intervals].sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const merged = [[...sorted[0]]];

  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    const last = merged.at(-1);
    if (start <= last[1]) last[1] = Math.max(last[1], end);   // overlap
    else merged.push([start, end]);                            // gap
  }
  return merged;
}

function insertInterval(intervals, [start, end]) {   // O(n)
  const out = [];
  let i = 0;
  let lo = start;
  let hi = end;

  while (i < intervals.length && intervals[i][1] < lo) out.push(intervals[i++]);
  while (i < intervals.length && intervals[i][0] <= hi) {
    lo = Math.min(lo, intervals[i][0]);
    hi = Math.max(hi, intervals[i][1]);
    i++;
  }
  out.push([lo, hi]);
  return [...out, ...intervals.slice(i)];
}

function maxConcurrent(intervals) {     // sweep line, O(n log n)
  const events = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);            // arrival
    events.push([end, -1]);             // departure
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // ends before starts

  let active = 0;
  let best = 0;
  for (const [, delta] of events) best = Math.max(best, (active += delta));
  return best;
}

console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1,6],[8,10],[15,18]]
console.log(maxConcurrent([[0, 30], [5, 10], [15, 20]]));   // 2