heap underflow

The name is the classic Rust accident: you grab a BinaryHeap, you subtract one from a usize index, and your program panics on input of length zero. This page collects the solutions I keep rewriting, each with the canonical shape and the gotchas that differ from C++/Python muscle memory. Hit Run on any snippet to execute it (compiled server-side by codapi), or edit the code first and see what breaks.

A disclaimer: these are my implementations. Every function has tests and I ran each snippet before publishing, but a bug may still have slipped in somewhere. Don’t take my word for it, the code on this page is editable, change it and rerun it in your browser.

The companion repo with the full test suites is adamsmo/heap-underflow on GitHub.

The cheat sheet: from problem statement to pattern

Lookup layer. Find the phrase from the problem statement, jump to the matching solution. The one-line core is what you should be able to write from memory.

DP

Binary search

Subarrays, two pointers, line sweep

Graphs

Union-find

Stacks

Greedy

Digits greedy

Number theory

Grid manipulation

Rust gotchas, the cross-cutting list

Patterns under pressure

Edge cases to check before running

Classic traps

• Rolling 0/1 DP iterated FORWARD: the item gets reused, you silently get the unbounded variant. Backward for 0/1. See subset_sum.
• 1..capacity instead of 1..=capacity: the last column never gets filled. See knapsack.
• Mixing binary search styles: half-open while lo < hi with a closed-style hi = mid - 1 update, or lo = mid instead of mid + 1. On a 2-element range mid equals lo and the loop never shrinks. Walk the 3-point checklist (mid formula, loop condition, both updates) before running. See the binary search section.
• i32::MAX sentinel without a guard before + 1: overflow panic in debug, wraparound in release. See coin_change.
• s[i] on a &str does not compile; collect to Vec<char> first. See edit_distance.

Graphs

The shape: BFS uses a VecDeque and marks visited ON ENQUEUE, which is what guarantees shortest-by-layers on unweighted graphs. Dijkstra wants a min-heap, but Rust’s BinaryHeap is a max-heap, so wrap entries in Reverse. There is no decrease-key either: push a fresh entry and discard stale ones when popped (lazy deletion).

• Grid neighbours: compute as i32, reject negatives, THEN cast to usize. A usize subtraction at row 0 wraps to a huge index.
• Iterative DFS with a Vec stack: a node can be pushed twice before its first pop, so re-check visited after popping. Recursion is shorter but can blow the call stack, Rust has no tail-call optimization.
• Undirected edge lists: add BOTH directions, or a component splits when an edge is listed as (to, from).

use std::collections::VecDeque;

/// Shortest path length on a grid using BFS (4-directional).
///
/// `grid[r][c]`: `0` = open, `1` = wall. Returns the number of steps from
/// `start` to `end`, or `None` if unreachable. For 8-directional movement,
/// add the four diagonals to `DIRS`.
///
/// Gotchas:
/// - Bounds: compute neighbors as `i32`, reject negatives before casting back to `usize`
///   (a `usize` subtraction would underflow and wrap to a huge index).
/// - Mark `visited` when you ENQUEUE, not when you dequeue, or a cell can land in the
///   queue many times and you lose the shortest-by-layer guarantee.
pub fn bfs_grid(grid: &[Vec<i32>], start: (usize, usize), end: (usize, usize)) -> Option<usize> {
    if grid.is_empty() || grid[0].is_empty() {
        return None;
    }
    let (rows, cols) = (grid.len(), grid[0].len());
    if grid[start.0][start.1] == 1 || grid[end.0][end.1] == 1 {
        return None;
    }
    if start == end {
        return Some(0);
    }

    const DIRS: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

    let mut visited = vec![vec![false; cols]; rows];
    let mut queue: VecDeque<((usize, usize), usize)> = VecDeque::new();
    visited[start.0][start.1] = true;
    queue.push_back((start, 0));

    while let Some(((r, c), dist)) = queue.pop_front() {
        for (dr, dc) in DIRS {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr < 0 || nc < 0 || nr >= rows as i32 || nc >= cols as i32 {
                continue;
            }
            let (nr, nc) = (nr as usize, nc as usize);
            if grid[nr][nc] == 1 || visited[nr][nc] {
                continue;
            }
            if (nr, nc) == end {
                return Some(dist + 1);
            }
            visited[nr][nc] = true;
            queue.push_back(((nr, nc), dist + 1));
        }
    }
    None
}

fn main() {
    let grid = vec![vec![0, 1, 0], vec![0, 1, 0], vec![0, 0, 0]];
    let steps = bfs_grid(&grid, (0, 0), (0, 2));
    assert_eq!(steps, Some(6));
    println!("shortest path around the wall: {steps:?}");
}

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};

/// Dijkstra shortest distances from `start` over a weighted adjacency list.
///
/// `graph[&u]` is a list of `(neighbor, weight)`. Returns a map of every reachable
/// node to its distance from `start`; unreachable nodes are absent.
///
/// Gotchas:
/// - `BinaryHeap` is a MAX-heap. Wrap entries in `Reverse` to pop the smallest cost first.
/// - There is no decrease-key: when a shorter path is found, push a fresh `(cost, node)`
///   entry. The older, larger entry stays in the heap and is discarded by the
///   `cost > best` guard when it is popped (lazy deletion).
/// - A node with no outgoing edges (or missing as a key) is handled as "no neighbors",
///   never `unwrap`.
pub fn dijkstra(graph: &HashMap<usize, Vec<(usize, u32)>>, start: usize) -> HashMap<usize, u32> {
    let mut dist: HashMap<usize, u32> = HashMap::new();
    let mut heap: BinaryHeap<Reverse<(u32, usize)>> = BinaryHeap::new();

    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((cost, node))) = heap.pop() {
        if cost > *dist.get(&node).unwrap_or(&u32::MAX) {
            continue; // stale entry, a shorter path was already settled
        }
        if let Some(neighbors) = graph.get(&node) {
            for &(next, weight) in neighbors {
                let next_cost = cost + weight;
                if next_cost < *dist.get(&next).unwrap_or(&u32::MAX) {
                    dist.insert(next, next_cost);
                    heap.push(Reverse((next_cost, next)));
                }
            }
        }
    }
    dist
}

fn main() {
    let mut g = HashMap::new();
    g.insert(0, vec![(1, 1), (2, 4)]);
    g.insert(1, vec![(2, 2)]);
    g.insert(2, vec![]);
    let dist = dijkstra(&g, 0);
    assert_eq!(dist[&2], 3);
    println!("dist 0 -> 2 = {} (via node 1, cheaper than the direct edge)", dist[&2]);
}

/// Depth-first traversal order from `start` over an adjacency list (iterative).
///
/// Gotcha: a `Vec` is the stack. Mark visited when you POP and re-check, because
/// a node can be pushed more than once before it is first popped. The recursive
/// form is shorter but can overflow the call stack on a deep graph (Rust has no
/// tail-call optimization). Pushing neighbours in reverse visits the lowest
/// index first, matching the recursive order.
pub fn dfs_order(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut visited = vec![false; adj.len()];
    let mut stack = vec![start];
    let mut order = Vec::new();
    while let Some(node) = stack.pop() {
        if visited[node] {
            continue;
        }
        visited[node] = true;
        order.push(node);
        for &next in adj[node].iter().rev() {
            if !visited[next] {
                stack.push(next);
            }
        }
    }
    order
}

fn main() {
    let adj = vec![vec![1, 2], vec![3], vec![], vec![]];
    let order = dfs_order(&adj, 0);
    assert_eq!(order, vec![0, 1, 3, 2]);
    println!("dfs order: {order:?}");
}

/// Topological order via Kahn's algorithm, or `None` if the graph has a cycle.
///
/// Repeatedly emit nodes with in-degree 0 and decrement their neighbours. If
/// fewer than `n` nodes come out, the rest are stuck in a cycle.
pub fn topological_sort(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![Vec::new(); n];
    let mut indeg = vec![0usize; n];
    for &(from, to) in edges {
        adj[from].push(to);
        indeg[to] += 1;
    }

    // start with every node that has no incoming edge
    let mut queue: Vec<usize> = (0..n).filter(|&v| indeg[v] == 0).collect();
    let mut head = 0;
    let mut order = Vec::new();

    while head < queue.len() {
        let node = queue[head];
        head += 1;
        order.push(node);
        for &next in &adj[node] {
            indeg[next] -= 1; // remove the edge node -> next
            if indeg[next] == 0 {
                queue.push(next);
            }
        }
    }

    if order.len() == n {
        Some(order)
    } else {
        None // leftover nodes form a cycle
    }
}

fn main() {
    let order = topological_sort(3, &[(0, 1), (1, 2)]);
    assert_eq!(order, Some(vec![0, 1, 2]));
    let cyclic = topological_sort(3, &[(0, 1), (1, 2), (2, 0)]);
    assert_eq!(cyclic, None);
    println!("chain: {order:?}, with a back edge: {cyclic:?}");
}

/// Two-colour a graph by BFS. Returns the `0`/`1` colouring if the graph is
/// bipartite, or `None` if two adjacent nodes are forced the same colour.
///
/// Loops over every start index so disconnected components are all covered.
pub fn is_bipartite(adj: &[Vec<usize>]) -> Option<Vec<u8>> {
    let n = adj.len();
    let mut color = vec![u8::MAX; n]; // MAX = uncoloured

    for start in 0..n {
        if color[start] != u8::MAX {
            continue;
        }
        color[start] = 0;
        let mut head = 0;
        let mut queue = vec![start];
        while head < queue.len() {
            let node = queue[head];
            head += 1;
            for &next in &adj[node] {
                if color[next] == u8::MAX {
                    color[next] = 1 - color[node]; // opposite colour
                    queue.push(next);
                } else if color[next] == color[node] {
                    return None; // conflict, not bipartite
                }
            }
        }
    }
    Some(color)
}

fn main() {
    let square = vec![vec![1, 3], vec![0, 2], vec![1, 3], vec![0, 2]];
    let coloring = is_bipartite(&square);
    assert_eq!(coloring, Some(vec![0, 1, 0, 1]));
    let triangle = vec![vec![1, 2], vec![0, 2], vec![0, 1]];
    assert_eq!(is_bipartite(&triangle), None);
    println!("square coloring: {coloring:?}, triangle: not bipartite");
}

/// Number of connected components in an UNDIRECTED graph.
///
/// Each edge is added in both directions, otherwise a component would split
/// when an edge is listed as `(to, from)`. Every unvisited node starts a new
/// component, then DFS marks the rest of it.
pub fn count_components(n: usize, edges: &[(usize, usize)]) -> usize {
    let mut adj = vec![Vec::new(); n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }

    let mut visited = vec![false; n];
    let mut count = 0;
    for start in 0..n {
        if visited[start] {
            continue;
        }
        count += 1; // a new, previously unseen component
        let mut stack = vec![start];
        visited[start] = true;
        while let Some(node) = stack.pop() {
            for &next in &adj[node] {
                if !visited[next] {
                    visited[next] = true;
                    stack.push(next);
                }
            }
        }
    }
    count
}

fn main() {
    let components = count_components(5, &[(0, 1), (2, 3)]);
    assert_eq!(components, 3);
    println!("{components} components: {{0,1}}, {{2,3}}, {{4}}");
}

/// Topological order via Kahn's algorithm, or `None` if the graph has a cycle.
///
/// Repeatedly emit nodes with in-degree 0 and decrement their neighbours. If
/// fewer than `n` nodes come out, the rest are stuck in a cycle.
pub fn topological_sort(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut adj = vec![Vec::new(); n];
    let mut indeg = vec![0usize; n];
    for &(from, to) in edges {
        adj[from].push(to);
        indeg[to] += 1;
    }

    // start with every node that has no incoming edge
    let mut queue: Vec<usize> = (0..n).filter(|&v| indeg[v] == 0).collect();
    let mut head = 0;
    let mut order = Vec::new();

    while head < queue.len() {
        let node = queue[head];
        head += 1;
        order.push(node);
        for &next in &adj[node] {
            indeg[next] -= 1; // remove the edge node -> next
            if indeg[next] == 0 {
                queue.push(next);
            }
        }
    }

    if order.len() == n {
        Some(order)
    } else {
        None // leftover nodes form a cycle
    }
}

/// Does a directed graph contain a cycle? A topological sort fails iff it does.
pub fn has_cycle_directed(n: usize, edges: &[(usize, usize)]) -> bool {
    topological_sort(n, edges).is_none()
}

fn main() {
    let chain = has_cycle_directed(3, &[(0, 1), (1, 2)]);
    let looped = has_cycle_directed(3, &[(0, 1), (1, 2), (2, 0)]);
    assert!(!chain && looped);
    println!("chain has cycle: {chain}, with back edge 2 -> 0: {looped}");
}

Union-find (DSU)

The shape: a parent forest with path compression in find and union by rank in union, near O(1) amortized per operation. The workhorse is the boolean that union returns: false means “already in the same set”, which in an undirected graph is exactly a cycle. That one bit answers component counts, cycle detection and which edge closed the loop.

• Elements must be a dense 0..n. Emails, coordinates, sparse ids: map them through a HashMap to dense ids first.
• rank is a height bound, not a size: bump it only when two EQUAL-rank roots merge.
• There is no DSU in std, and online coding editors rarely give you external crates, so practice writing the whole struct from memory.

use std::cmp::Ordering;

/// Disjoint Set Union over the elements `0..n`.
///
/// Gotchas:
/// - Elements must be a dense `0..n`. Sparse or non-integer keys (emails, grid
///   coordinates) need a `HashMap` to map them to ids first (see `accounts_merge`).
/// - `rank` is an upper bound on height, not the set size: only bump it when two
///   roots of equal rank merge.
/// - The recursive `find` compresses the path cleanly; on adversarially deep input
///   an iterative two-pass `find` avoids growing the call stack.
pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl Dsu {
    /// Every element starts in its own singleton set.
    pub fn new(n: usize) -> Self {
        Dsu {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    /// Root of `x`'s set, compressing the path so later `find`s are flat.
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    /// Merge the sets of `x` and `y`. Returns `false` if they were already together.
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (root_x, root_y) = (self.find(x), self.find(y));
        if root_x == root_y {
            return false;
        }
        match self.rank[root_x].cmp(&self.rank[root_y]) {
            Ordering::Less => self.parent[root_x] = root_y,
            Ordering::Greater => self.parent[root_y] = root_x,
            Ordering::Equal => {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // ties are the only case the height can grow
            }
        }
        true
    }

    /// Are `x` and `y` in the same set?
    pub fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

fn main() {
    let mut d = Dsu::new(5);
    d.union(0, 1);
    d.union(2, 3);
    let before = d.connected(0, 3);
    d.union(1, 3);
    let after = d.connected(0, 3);
    assert!(!before && after);
    println!("0 and 3 connected: before {before}, after {after}");
}

use std::cmp::Ordering;

/// Disjoint Set Union over the elements `0..n`.
///
/// Gotchas:
/// - Elements must be a dense `0..n`. Sparse or non-integer keys (emails, grid
///   coordinates) need a `HashMap` to map them to ids first (see `accounts_merge`).
/// - `rank` is an upper bound on height, not the set size: only bump it when two
///   roots of equal rank merge.
/// - The recursive `find` compresses the path cleanly; on adversarially deep input
///   an iterative two-pass `find` avoids growing the call stack.
pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl Dsu {
    /// Every element starts in its own singleton set.
    pub fn new(n: usize) -> Self {
        Dsu {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    /// Root of `x`'s set, compressing the path so later `find`s are flat.
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    /// Merge the sets of `x` and `y`. Returns `false` if they were already together.
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (root_x, root_y) = (self.find(x), self.find(y));
        if root_x == root_y {
            return false;
        }
        match self.rank[root_x].cmp(&self.rank[root_y]) {
            Ordering::Less => self.parent[root_x] = root_y,
            Ordering::Greater => self.parent[root_y] = root_x,
            Ordering::Equal => {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // ties are the only case the height can grow
            }
        }
        true
    }

    /// Are `x` and `y` in the same set?
    pub fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

/// Number of connected components in an undirected graph on `0..n`.
///
/// Start with `n` singletons; every edge that actually merges two sets drops the
/// count by one. Edges inside an already-joined component change nothing. This is
/// the DSU answer to the same question `graphs::count_components` solves with DFS.
pub fn count_components(n: usize, edges: &[(usize, usize)]) -> usize {
    let mut dsu = Dsu::new(n);
    let mut components = n;
    for &(a, b) in edges {
        if dsu.union(a, b) {
            components -= 1;
        }
    }
    components
}

fn main() {
    let components = count_components(5, &[(0, 1), (2, 3)]);
    assert_eq!(components, 3);
    println!("{components} components, same answer as the DFS version");
}

use std::cmp::Ordering;

/// Disjoint Set Union over the elements `0..n`.
///
/// Gotchas:
/// - Elements must be a dense `0..n`. Sparse or non-integer keys (emails, grid
///   coordinates) need a `HashMap` to map them to ids first (see `accounts_merge`).
/// - `rank` is an upper bound on height, not the set size: only bump it when two
///   roots of equal rank merge.
/// - The recursive `find` compresses the path cleanly; on adversarially deep input
///   an iterative two-pass `find` avoids growing the call stack.
pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl Dsu {
    /// Every element starts in its own singleton set.
    pub fn new(n: usize) -> Self {
        Dsu {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    /// Root of `x`'s set, compressing the path so later `find`s are flat.
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    /// Merge the sets of `x` and `y`. Returns `false` if they were already together.
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (root_x, root_y) = (self.find(x), self.find(y));
        if root_x == root_y {
            return false;
        }
        match self.rank[root_x].cmp(&self.rank[root_y]) {
            Ordering::Less => self.parent[root_x] = root_y,
            Ordering::Greater => self.parent[root_y] = root_x,
            Ordering::Equal => {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // ties are the only case the height can grow
            }
        }
        true
    }

    /// Are `x` and `y` in the same set?
    pub fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

/// The first edge that closes a cycle in an undirected graph on `0..n`, if any.
///
/// Add edges in order; the first one whose endpoints are already connected is the
/// one that turns a tree into a graph with a cycle.
pub fn redundant_connection(n: usize, edges: &[(usize, usize)]) -> Option<(usize, usize)> {
    let mut dsu = Dsu::new(n);
    for &(a, b) in edges {
        if !dsu.union(a, b) {
            return Some((a, b));
        }
    }
    None
}

fn main() {
    let edge = redundant_connection(3, &[(0, 1), (1, 2), (0, 2)]);
    assert_eq!(edge, Some((0, 2)));
    println!("edge closing the cycle: {edge:?}");
}

use std::cmp::Ordering;

/// Disjoint Set Union over the elements `0..n`.
///
/// Gotchas:
/// - Elements must be a dense `0..n`. Sparse or non-integer keys (emails, grid
///   coordinates) need a `HashMap` to map them to ids first (see `accounts_merge`).
/// - `rank` is an upper bound on height, not the set size: only bump it when two
///   roots of equal rank merge.
/// - The recursive `find` compresses the path cleanly; on adversarially deep input
///   an iterative two-pass `find` avoids growing the call stack.
pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl Dsu {
    /// Every element starts in its own singleton set.
    pub fn new(n: usize) -> Self {
        Dsu {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    /// Root of `x`'s set, compressing the path so later `find`s are flat.
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    /// Merge the sets of `x` and `y`. Returns `false` if they were already together.
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (root_x, root_y) = (self.find(x), self.find(y));
        if root_x == root_y {
            return false;
        }
        match self.rank[root_x].cmp(&self.rank[root_y]) {
            Ordering::Less => self.parent[root_x] = root_y,
            Ordering::Greater => self.parent[root_y] = root_x,
            Ordering::Equal => {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // ties are the only case the height can grow
            }
        }
        true
    }

    /// Are `x` and `y` in the same set?
    pub fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

/// Count friend circles from an `n x n` symmetric adjacency matrix (LC 547).
///
/// `matrix[i][j] == 1` means `i` and `j` are directly connected. Scan the upper
/// triangle only (the matrix is symmetric) and merge; each real merge joins two
/// circles into one.
pub fn friend_circles(matrix: &[Vec<i32>]) -> usize {
    let mut dsu = Dsu::new(matrix.len());
    let mut circles = matrix.len();
    for (i, row) in matrix.iter().enumerate() {
        for (j, &cell) in row.iter().enumerate().skip(i + 1) {
            if cell == 1 && dsu.union(i, j) {
                circles -= 1;
            }
        }
    }
    circles
}

fn main() {
    let m = vec![vec![1, 1, 0], vec![1, 1, 0], vec![0, 0, 1]];
    let circles = friend_circles(&m);
    assert_eq!(circles, 2);
    println!("friend circles: {circles}");
}

use std::cmp::Ordering;

/// Disjoint Set Union over the elements `0..n`.
///
/// Gotchas:
/// - Elements must be a dense `0..n`. Sparse or non-integer keys (emails, grid
///   coordinates) need a `HashMap` to map them to ids first (see `accounts_merge`).
/// - `rank` is an upper bound on height, not the set size: only bump it when two
///   roots of equal rank merge.
/// - The recursive `find` compresses the path cleanly; on adversarially deep input
///   an iterative two-pass `find` avoids growing the call stack.
pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl Dsu {
    /// Every element starts in its own singleton set.
    pub fn new(n: usize) -> Self {
        Dsu {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    /// Root of `x`'s set, compressing the path so later `find`s are flat.
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    /// Merge the sets of `x` and `y`. Returns `false` if they were already together.
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (root_x, root_y) = (self.find(x), self.find(y));
        if root_x == root_y {
            return false;
        }
        match self.rank[root_x].cmp(&self.rank[root_y]) {
            Ordering::Less => self.parent[root_x] = root_y,
            Ordering::Greater => self.parent[root_y] = root_x,
            Ordering::Equal => {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // ties are the only case the height can grow
            }
        }
        true
    }

    /// Are `x` and `y` in the same set?
    pub fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

/// Number of independent cycles (the cyclomatic number) of the undirected graph
/// given as a symmetric adjacency matrix.
///
/// Every edge whose endpoints are already connected closes one more independent
/// cycle; the rest are spanning-tree edges that merge fresh components.
pub fn independent_cycles(matrix: &[Vec<i32>]) -> usize {
    let mut dsu = Dsu::new(matrix.len());
    let mut cycles = 0;
    for (i, row) in matrix.iter().enumerate() {
        for (j, &cell) in row.iter().enumerate().skip(i + 1) {
            if cell == 1 && !dsu.union(i, j) {
                cycles += 1;
            }
        }
    }
    cycles
}

fn main() {
    let triangle = vec![vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]];
    let cycles = independent_cycles(&triangle);
    assert_eq!(cycles, 1);
    println!("independent cycles in a triangle: {cycles}");
}

use std::cmp::Ordering;
use std::collections::HashMap;

/// Disjoint Set Union over the elements `0..n`.
///
/// Gotchas:
/// - Elements must be a dense `0..n`. Sparse or non-integer keys (emails, grid
///   coordinates) need a `HashMap` to map them to ids first (see `accounts_merge`).
/// - `rank` is an upper bound on height, not the set size: only bump it when two
///   roots of equal rank merge.
/// - The recursive `find` compresses the path cleanly; on adversarially deep input
///   an iterative two-pass `find` avoids growing the call stack.
pub struct Dsu {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl Dsu {
    /// Every element starts in its own singleton set.
    pub fn new(n: usize) -> Self {
        Dsu {
            parent: (0..n).collect(),
            rank: vec![0; n],
        }
    }

    /// Root of `x`'s set, compressing the path so later `find`s are flat.
    pub fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            let root = self.find(self.parent[x]);
            self.parent[x] = root;
        }
        self.parent[x]
    }

    /// Merge the sets of `x` and `y`. Returns `false` if they were already together.
    pub fn union(&mut self, x: usize, y: usize) -> bool {
        let (root_x, root_y) = (self.find(x), self.find(y));
        if root_x == root_y {
            return false;
        }
        match self.rank[root_x].cmp(&self.rank[root_y]) {
            Ordering::Less => self.parent[root_x] = root_y,
            Ordering::Greater => self.parent[root_y] = root_x,
            Ordering::Equal => {
                self.parent[root_y] = root_x;
                self.rank[root_x] += 1; // ties are the only case the height can grow
            }
        }
        true
    }

    /// Are `x` and `y` in the same set?
    pub fn connected(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
}

/// Merge accounts that share any email (LC 721).
///
/// Each account is `(name, emails)`. Two accounts belong to the same person iff
/// they share at least one email; merging is transitive. Returns one
/// `(name, sorted_emails)` per person.
///
/// Gotcha: DSU works on dense `usize` ids, but the keys here are email strings, so
/// map each distinct email to an id first, union within each account, then regroup
/// by root. The anchor for an account is its FIRST email's id, not the name (the
/// name is not a key in the email table).
pub fn accounts_merge(accounts: &[(String, Vec<String>)]) -> Vec<(String, Vec<String>)> {
    let mut email_id: HashMap<&str, usize> = HashMap::new();
    let mut email_name: HashMap<&str, &str> = HashMap::new();
    for (name, emails) in accounts {
        for email in emails {
            let next = email_id.len();
            email_id.entry(email).or_insert(next);
            email_name.insert(email, name);
        }
    }

    let mut dsu = Dsu::new(email_id.len());
    for (_, emails) in accounts {
        let mut ids = emails.iter().map(|e| email_id[e.as_str()]);
        if let Some(anchor) = ids.next() {
            for id in ids {
                dsu.union(anchor, id);
            }
        }
    }

    let mut groups: HashMap<usize, Vec<&str>> = HashMap::new();
    for (&email, &id) in &email_id {
        let root = dsu.find(id);
        groups.entry(root).or_default().push(email);
    }

    let mut result = Vec::with_capacity(groups.len());
    for mut emails in groups.into_values() {
        emails.sort_unstable();
        let name = email_name[emails[0]].to_string();
        let owned = emails.into_iter().map(String::from).collect();
        result.push((name, owned));
    }
    result
}

fn main() {
    let accounts = vec![
        ("John".to_string(), vec!["js@m.com".to_string(), "jn@m.com".to_string()]),
        ("John".to_string(), vec!["js@m.com".to_string(), "j0@m.com".to_string()]),
        ("Mary".to_string(), vec!["mary@m.com".to_string()]),
    ];
    let merged = accounts_merge(&accounts);
    assert_eq!(merged.len(), 2);
    println!("merged into {} people", merged.len());
}

Binary search

The shape: pick ONE convention and never mix them. Closed [lo, hi] uses i32 bounds, while lo <= hi and moves past mid with mid ± 1. Half-open [lo, hi) uses hi = a.len(), while lo < hi, and hi = mid / lo = mid + 1. In Rust prefer half-open: a.len() never underflows on empty input and hi = mid never subtracts from a usize.

• Three sources of an infinite loop, all off-by-one: a branch keeps mid in range (lo = mid), the loop condition disagrees with the bound style, or mid rounds toward the side that stays.
• Always mid = lo + (hi - lo) / 2, never (lo + hi) / 2 (overflow).
• slice::partition_point IS lower/upper bound, and most “find first/last/count” questions reduce to it plus one check.
• Binary search on the ANSWER: search a value range instead of indices, with a monotone feasibility predicate. Triggers: “smallest X such that”, “split into k parts minimizing the max”.

use std::cmp::Ordering;

/// Classic binary search over a sorted slice. Returns the index or -1.
///
/// Closed interval with `i32` bounds, because `mid - 1` can go below 0.
/// `Ordering::cmp` collapses the three-way branch into a single `match`.
pub fn binary_search(a: &[i32], target: i32) -> i32 {
    if a.is_empty() {
        return -1;
    }
    let mut lo: i32 = 0;
    let mut hi: i32 = (a.len() - 1) as i32;

    while lo <= hi {
        let mid: i32 = lo + (hi - lo) / 2; // overflow-safe (Bentley/Bloch)
        let m = mid as usize;
        match a[m].cmp(&target) {
            Ordering::Equal => return mid,
            Ordering::Greater => hi = mid - 1,
            Ordering::Less => lo = mid + 1,
        }
    }
    -1
}

fn main() {
    let a = [1, 3, 5, 7, 9];
    let idx = binary_search(&a, 7);
    assert_eq!(idx, 3);
    println!("found 7 at index {idx}");
}

/// Index of the first occurrence of `target`, or -1.
///
/// Half-open lower-bound scan, then one check: keep moving `hi` left while
/// `a[mid] >= target` so you land on the leftmost candidate.
pub fn first_occurrence(a: &[i32], target: i32) -> i32 {
    if a.is_empty() {
        return -1;
    }
    let mut lo = 0;
    let mut hi = a.len();
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if a[mid] < target {
            lo = mid + 1;
        } else {
            hi = mid; // candidate, keep it in range
        }
    }
    // a.get(lo) does the bounds check and the read together, no panic risk
    if a.get(lo) == Some(&target) {
        lo as i32
    } else {
        -1
    }
}

fn main() {
    let a = [1, 2, 2, 2, 3];
    let idx = first_occurrence(&a, 2);
    assert_eq!(idx, 1);
    println!("first 2 at index {idx}");
}

/// Lower bound: smallest `i` with `a[i] >= t`.
///
/// `slice::partition_point` IS binary search with a predicate, and it is the
/// idiomatic way to write it in Rust.
pub fn lower_bound(a: &[i32], t: i32) -> usize {
    a.partition_point(|&x| x < t)
}

fn main() {
    let a = [1, 2, 2, 2, 3, 5];
    let lo = lower_bound(&a, 2);
    assert_eq!(lo, 1);
    println!("lower_bound(2) = {lo}");
}

/// Lower bound: smallest `i` with `a[i] >= t`.
///
/// `slice::partition_point` IS binary search with a predicate, and it is the
/// idiomatic way to write it in Rust.
pub fn lower_bound(a: &[i32], t: i32) -> usize {
    a.partition_point(|&x| x < t)
}

/// Upper bound: smallest `i` with `a[i] > t`. `upper_bound - lower_bound` counts `t`.
pub fn upper_bound(a: &[i32], t: i32) -> usize {
    a.partition_point(|&x| x <= t)
}

fn main() {
    let a = [1, 2, 2, 2, 3, 5];
    let (lo, up) = (lower_bound(&a, 2), upper_bound(&a, 2));
    assert_eq!((lo, up), (1, 4));
    println!("count of 2s = upper - lower = {}", up - lo);
}

/// Search in a rotated sorted array (no duplicates). Returns the index or -1.
///
/// Each step, exactly one half `[lo..=mid]` or `[mid..=hi]` is sorted. Decide
/// which, then test whether the target lies inside that sorted half.
pub fn search_rotated(a: &[i32], t: i32) -> i32 {
    let (mut lo, mut hi) = (0i32, a.len() as i32 - 1);
    while lo <= hi {
        let mid = lo + (hi - lo) / 2;
        let m = mid as usize;

        if a[m] == t {
            return mid;
        }

        if a[lo as usize] <= a[m] {
            // left half is sorted: is t in [a[lo], a[m]) ?
            if a[lo as usize] <= t && t < a[m] {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            // right half is sorted: is t in (a[m], a[hi]] ?
            if a[m] < t && t <= a[hi as usize] {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    -1
}

fn main() {
    let a = [4, 5, 6, 7, 0, 1, 2];
    let idx = search_rotated(&a, 0);
    assert_eq!(idx, 4);
    println!("found 0 at index {idx}");
}

/// Index of any peak: `a[i] > a[i-1]` and `a[i] > a[i+1]`, with `a[-1] = a[n] = -inf`.
///
/// Binary search on the slope: compare with the NEIGHBOR, not a target. Walk
/// toward the rising side, which always contains a peak.
pub fn find_peak(a: &[i32]) -> usize {
    let mut lo = 0;
    let mut hi = a.len() - 1;
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if a[mid] < a[mid + 1] {
            lo = mid + 1; // rising slope, peak is to the right
        } else {
            hi = mid; // peak is at mid or to the left
        }
    }
    lo
}

fn main() {
    let a = [1, 3, 2];
    let i = find_peak(&a);
    assert_eq!(i, 1);
    println!("peak at index {i} (value {})", a[i]);
}

/// Greedy predicate: can `a` be packed into <= `k` blocks, each summing to <= `max_sum`?
fn can_split(a: &[i32], max_sum: i32, k: usize) -> bool {
    let mut blocks = 1;
    let mut current = 0;
    for &x in a {
        if current + x > max_sum {
            blocks += 1; // start a new block, this element goes there
            current = x;
            if blocks > k {
                return false;
            }
        } else {
            current += x;
        }
    }
    true
}

/// Split `a` into at most `k` contiguous blocks, minimizing the largest block sum.
///
/// Binary search on the ANSWER (the block-sum limit) with a greedy feasibility
/// predicate. Range is `[max(a), sum(a)]`: a single element must fit in a block.
pub fn min_max_division(a: &[i32], k: usize) -> i32 {
    let max_elem = *a.iter().max().unwrap();
    let total_sum: i32 = a.iter().sum();

    let mut lo = max_elem;
    let mut hi = total_sum;
    let mut answer = total_sum;

    while lo <= hi {
        let mid = lo + (hi - lo) / 2;
        if can_split(a, mid, k) {
            answer = mid; // mid is enough, try smaller
            hi = mid - 1;
        } else {
            lo = mid + 1; // not enough, allow a bigger limit
        }
    }
    answer
}

fn main() {
    let a = [2, 1, 5, 1, 2, 2, 2];
    let best = min_max_division(&a, 3);
    assert_eq!(best, 6);
    println!("minimal largest block sum with 3 blocks: {best}");
}

use std::cmp::Ordering;

/// Integer square root: the largest `x` with `x * x <= n`.
///
/// Binary search on the answer. `checked_mul` returns `None` on overflow, which
/// folds into the "mid too big" branch via `Option<Ordering>`.
pub fn isqrt(n: i64) -> i64 {
    if n < 2 {
        return n;
    }
    let mut lo: i64 = 1;
    let mut hi: i64 = n;
    let mut answer: i64 = 1;
    while lo <= hi {
        let mid = lo + (hi - lo) / 2;
        match mid.checked_mul(mid).map(|s| s.cmp(&n)) {
            Some(Ordering::Equal) => return mid,
            Some(Ordering::Less) => {
                answer = mid;
                lo = mid + 1;
            }
            _ => hi = mid - 1, // Some(Greater) or None (overflow): mid too big
        }
    }
    answer
}

fn main() {
    let r = isqrt(1_000_000_000_000);
    assert_eq!(r, 1_000_000);
    println!("isqrt(10^12) = {r}");
}

Dynamic programming

The shape: the optimum of the problem is the optimum of its subproblems plus one decision made now. The families: 1D with look-back 2 (stairs, house robber), 1D unbounded with a MAX sentinel (coin change), 1D subsequence in O(n²) (LIS, MSIS), 2D string-vs-string (LCS, edit distance), 2D path on a grid, and 2D knapsack 0/1.

• “Subsequence” means DP, not Kadane. Kadane is for contiguous subarrays only.
• Subsequence DPs can end anywhere: return *dp.iter().max().unwrap(), not dp[n-1].
• The i32::MAX sentinel needs a guard before + 1 or it overflows. A -1 sentinel silently wins every min(), do not use it.
• Indexing strings: collect to Vec<char> first, &str cannot be indexed by position.

/// Minimum cost to climb the stairs (look back 2). Steps of 1 or 2, start at 0.
pub fn climbing_stairs(cost: &[i32]) -> i32 {
    let n = cost.len();
    if n == 0 {
        return 0;
    }
    if n == 1 {
        return cost[0];
    }
    // rolling O(1) state instead of a full dp vector
    let (mut a, mut b) = (cost[0], cost[0] + cost[1]);
    for &c in &cost[2..] {
        (a, b) = (b, c + a.min(b));
    }
    b
}

fn main() {
    let cost = [10, 15, 20];
    let c = climbing_stairs(&cost);
    assert_eq!(c, 30);
    println!("min cost to the top: {c}");
}

/// Minimum number of coins to make `amount`, each coin unlimited. -1 if impossible.
pub fn coin_change(coins: &[i32], amount: i32) -> i32 {
    if amount == 0 {
        return 0;
    }
    let amount = amount as usize;
    let mut dp = vec![i32::MAX; amount + 1]; // MAX sentinel = unreachable
    dp[0] = 0;

    // unbounded: for each amount try every coin
    for i in 1..=amount {
        // the `dp[i-c] != MAX` guard prevents a MAX + 1 overflow
        dp[i] = coins
            .iter()
            .filter_map(|&coin| {
                let c = coin as usize;
                (c <= i && dp[i - c] != i32::MAX).then(|| dp[i - c] + 1)
            })
            .min()
            .unwrap_or(i32::MAX);
    }

    if dp[amount] == i32::MAX {
        -1
    } else {
        dp[amount]
    }
}

fn main() {
    let n = coin_change(&[1, 2, 5], 11);
    assert_eq!(n, 3);
    println!("fewest coins for 11: {n} (5 + 5 + 1)");
}

/// Maximum sum path from (0,0) to (n-1, m-1) moving only right or down.
pub fn grid_path(grid: &[Vec<i32>]) -> i32 {
    let n = grid.len();
    let m = grid[0].len();
    let mut dp = vec![vec![0i32; m]; n];

    // corners are the base, first column comes from above, first row from the left,
    // the interior takes the better of (above, left)
    for i in 0..n {
        for j in 0..m {
            let prev = match (i, j) {
                (0, 0) => 0,
                (0, j) => dp[0][j - 1],
                (i, 0) => dp[i - 1][0],
                (i, j) => dp[i - 1][j].max(dp[i][j - 1]),
            };
            dp[i][j] = grid[i][j] + prev;
        }
    }
    dp[n - 1][m - 1]
}

fn main() {
    let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
    let best = grid_path(&grid);
    assert_eq!(best, 12);
    println!("max path sum: {best}");
}

/// Longest strictly increasing subsequence (LIS), O(n^2).
pub fn lis(a: &[i32]) -> i32 {
    if a.is_empty() {
        return 0;
    }
    // dp[i] = length of the LIS ending at i; base case 1 (the element itself)
    let mut dp = vec![1i32; a.len()];

    for i in 1..a.len() {
        for j in 0..i {
            if a[j] < a[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }
    *dp.iter().max().unwrap() // the optimum can end in the middle
}

fn main() {
    let len = lis(&[10, 9, 2, 5, 3, 7, 101, 18]);
    assert_eq!(len, 4);
    println!("LIS length: {len} (e.g. 2, 3, 7, 18)");
}

/// Maximum-sum strictly increasing subsequence (MSIS). A subsequence, not a
/// subarray, so this is DP, not Kadane.
pub fn msis(a: &[i32]) -> i32 {
    if a.is_empty() {
        return 0;
    }
    // dp[i] = max sum of an increasing subsequence ending at i; base case a[i] alone
    let mut dp: Vec<i32> = a.to_vec();

    for i in 1..a.len() {
        for j in 0..i {
            if a[j] < a[i] {
                dp[i] = dp[i].max(dp[j] + a[i]);
            }
        }
    }
    *dp.iter().max().unwrap()
}

fn main() {
    let s = msis(&[1, 101, 2, 3, 100, 4, 5]);
    assert_eq!(s, 106);
    println!("max sum increasing subsequence: {s} (1 + 2 + 3 + 100)");
}

/// Longest common subsequence (LCS).
pub fn lcs(a: &str, b: &str) -> i32 {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let n = a.len();
    let m = b.len();
    let mut dp = vec![vec![0i32; m + 1]; n + 1];

    for i in 1..=n {
        for j in 1..=m {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1 // match: extend the LCS by one
            } else {
                dp[i - 1][j].max(dp[i][j - 1]) // mismatch: drop a char from a or b
            };
        }
    }
    dp[n][m]
}

fn main() {
    let l = lcs("AGGTAB", "GXTXAYB");
    assert_eq!(l, 4);
    println!("LCS length: {l} (GTAB)");
}

/// Edit distance (Levenshtein): minimum insert/delete/replace ops to turn `a` into `b`.
pub fn edit_distance(a: &str, b: &str) -> i32 {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let n = a.len();
    let m = b.len();
    let mut dp = vec![vec![0i32; m + 1]; n + 1];

    // base: an empty prefix needs j inserts or i deletes
    for (i, row) in dp.iter_mut().enumerate() {
        row[0] = i as i32;
    }
    for (j, cell) in dp[0].iter_mut().enumerate() {
        *cell = j as i32;
    }

    for i in 1..=n {
        for j in 1..=m {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] // match: copy the diagonal
            } else {
                // mismatch: 1 + min(delete, insert, replace)
                1 + dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1])
            };
        }
    }
    dp[n][m]
}

fn main() {
    let d = edit_distance("kitten", "sitting");
    assert_eq!(d, 3);
    println!("kitten -> sitting: {d} edits");
}

/// 0/1 knapsack: maximum value within `capacity`.
pub fn knapsack(weights: &[i32], values: &[i32], capacity: i32) -> i32 {
    let items = weights.len();
    let cap = capacity as usize;
    let mut dp = vec![vec![0i32; cap + 1]; items + 1];

    for i in 1..=items {
        let wi = weights[i - 1] as usize;
        let vi = values[i - 1];
        for w in 0..=cap {
            // skip the item, or take it (value + best for the remaining capacity)
            dp[i][w] = if wi <= w {
                dp[i - 1][w].max(dp[i - 1][w - wi] + vi)
            } else {
                dp[i - 1][w]
            };
        }
    }
    dp[items][cap]
}

fn main() {
    let value = knapsack(&[2, 3, 4, 5], &[3, 4, 5, 6], 8);
    assert_eq!(value, 10);
    println!("best value within capacity 8: {value}");
}

/// 0/1 knapsack with backtracking: indices of the taken items (0-based, ascending).
pub fn knapsack_items(weights: &[i32], values: &[i32], capacity: i32) -> Vec<usize> {
    let items = weights.len();
    let cap = capacity as usize;

    // phase 1: the same DP as knapsack()
    let mut dp = vec![vec![0i32; cap + 1]; items + 1];
    for i in 1..=items {
        let wi = weights[i - 1] as usize;
        let vi = values[i - 1];
        for w in 0..=cap {
            dp[i][w] = if wi <= w {
                dp[i - 1][w].max(dp[i - 1][w - wi] + vi)
            } else {
                dp[i - 1][w]
            };
        }
    }

    // phase 2: backtrack from dp[items][cap]; if dp[i][w] beat dp[i-1][w], item i-1 was taken
    let mut taken = Vec::new();
    let mut w = cap;
    for i in (1..=items).rev() {
        if dp[i][w] > dp[i - 1][w] {
            taken.push(i - 1);
            w -= weights[i - 1] as usize;
        }
    }
    taken.reverse();
    taken
}

fn main() {
    let taken = knapsack_items(&[2, 3, 4, 5], &[3, 4, 5, 6], 8);
    assert_eq!(taken, vec![1, 3]);
    println!("take items {taken:?} (weights 3 + 5 = 8)");
}

Subset sum (rolling 1D)

The shape: 0/1 knapsack reachability in 1D space. One row, iterated BACKWARD per item: when you update dp[j], the dp[j - v] you read is still from before this item, so each element is used at most once. Forward iteration turns it into the unbounded variant, that is the whole difference between the two.

• Boolean “does a subset exist” uses dp[j] |= dp[j - v] with base dp[0] = true. Counting uses dp[j] += dp[j - v] with base 1.
• Counts grow exponentially: switch to i64 or count modulo 1e9+7 before they overflow.
• “+/- before each element” is not a new DP: solve P = (target + total) / 2 and call the subset counter (the same trick covers “partition into two equal sets” and “min difference of two sets”).

/// Does some subset of `a` sum to `target`?
pub fn subset_sum(a: &[i32], target: i32) -> bool {
    if target < 0 {
        return false;
    }
    let target = target as usize;
    // dp[j] = is sum j reachable? Base case dp[0] = true (the empty subset).
    let mut dp = vec![false; target + 1];
    dp[0] = true;

    for &val in a {
        if val < 0 {
            continue;
        }
        let v = val as usize;
        if v > target {
            continue;
        }
        // backward, or we would use `val` more than once
        for j in (v..=target).rev() {
            dp[j] |= dp[j - v];
        }
    }
    dp[target]
}

fn main() {
    let possible = subset_sum(&[3, 34, 4, 12, 5, 2], 9);
    assert!(possible);
    println!("9 reachable: {possible} (4 + 5)");
}

/// How many subsets of `a` sum to `target`?
pub fn subset_sum_count(a: &[i32], target: i32) -> i32 {
    if target < 0 {
        return 0;
    }
    let target = target as usize;
    // dp[j] = number of ways. Base case dp[0] = 1 (one way: the empty subset).
    let mut dp = vec![0i32; target + 1];
    dp[0] = 1;

    for &val in a {
        if val < 0 {
            continue;
        }
        let v = val as usize;
        if v > target {
            continue;
        }
        // backward (0/1), summing ways instead of OR-ing reachability
        for j in (v..=target).rev() {
            dp[j] += dp[j - v];
        }
    }
    dp[target]
}

fn main() {
    let ways = subset_sum_count(&[1, 1, 1], 2);
    assert_eq!(ways, 3);
    println!("ways to sum 2 from [1, 1, 1]: {ways}");
}

/// How many subsets of `a` sum to `target`?
pub fn subset_sum_count(a: &[i32], target: i32) -> i32 {
    if target < 0 {
        return 0;
    }
    let target = target as usize;
    // dp[j] = number of ways. Base case dp[0] = 1 (one way: the empty subset).
    let mut dp = vec![0i32; target + 1];
    dp[0] = 1;

    for &val in a {
        if val < 0 {
            continue;
        }
        let v = val as usize;
        if v > target {
            continue;
        }
        // backward (0/1), summing ways instead of OR-ing reachability
        for j in (v..=target).rev() {
            dp[j] += dp[j - v];
        }
    }
    dp[target]
}

/// Target sum: assign + or - before each element so the total equals `target`.
///
/// Algebraic reduction: with positives `P` and negatives `N`, `P - N = target`
/// and `P + N = total`, so `P = (total + target) / 2`, which is a subset-count.
pub fn target_sum(a: &[i32], target: i32) -> i32 {
    let total: i32 = a.iter().sum();

    // feasibility: P must be a non-negative integer
    if (total + target) % 2 != 0 || target.abs() > total {
        return 0;
    }
    let p = (total + target) / 2;
    if p < 0 {
        return 0;
    }
    subset_sum_count(a, p)
}

fn main() {
    let ways = target_sum(&[1, 1, 1, 1, 1], 3);
    assert_eq!(ways, 5);
    println!("sign assignments hitting 3: {ways}");
}

Kadane, two pointers, line sweep

The shape: current = x.max(current + x) is one decision per element, extend the running subarray or restart at x; the answer is the best current seen. Reach for it when the problem says “contiguous” plus sum, product or profit. Two pointers walk a sorted array from both ends and the comparison decides which pointer moves. Line sweep sorts starts and ends separately and keeps a counter of open intervals.

• Initialize best = a[0], not 0, or an all-negative array returns a bogus 0.
• Circular max wrap case is total - min_subarray, but all-negative input must fall back to plain Kadane.
• Product version tracks min AND max ending at each index, one negative element swaps their roles.

/// Kadane's classic: maximum contiguous subarray sum.
///
/// Initialize `best = a[0]` (not 0) so an all-negative array returns its least
/// negative element instead of a bogus 0.
pub fn max_subarray(a: &[i32]) -> i32 {
    assert!(!a.is_empty(), "max_subarray: empty input");
    let mut best_sum = a[0];
    let mut current_sum = 0;
    for &x in a {
        // two choices: start fresh at x, or extend the previous subarray
        current_sum = x.max(current_sum + x);
        best_sum = best_sum.max(current_sum);
    }
    best_sum
}

fn main() {
    let best = max_subarray(&[-2, 1, -3, 4, -1, 2, 1, -5, 4]);
    assert_eq!(best, 6);
    println!("max subarray sum: {best} (4, -1, 2, 1)");
}

/// Maximum subarray sum on a CIRCULAR array.
///
/// Either the answer does not wrap (plain Kadane on max) or it wraps, in which
/// case it equals `total - min_subarray`. Guard all-negative: if the plain max
/// is negative, return it (the wrap case would wrongly yield 0).
pub fn max_circular_subarray(a: &[i32]) -> i32 {
    let total: i32 = a.iter().sum();
    let mut cur_min = a[0];
    let mut tot_min = a[0];
    let mut cur_max = a[0];
    let mut tot_max = a[0];

    for &x in a.iter().skip(1) {
        cur_min = x.min(cur_min + x);
        tot_min = tot_min.min(cur_min);
        cur_max = x.max(cur_max + x);
        tot_max = tot_max.max(cur_max);
    }

    if tot_max < 0 {
        tot_max // all-negative: the wrap case is undefined, fall back to plain Kadane
    } else {
        tot_max.max(total - tot_min)
    }
}

fn main() {
    let best = max_circular_subarray(&[5, -3, 5]);
    assert_eq!(best, 10);
    println!("max circular sum: {best} (wraps around)");
}

/// Maximum product subarray. A negative element flips max and min, so track both
/// the max and min product ending at each index.
pub fn max_product_subarray(a: &[i32]) -> i32 {
    let mut min_e = a[0];
    let mut max_e = a[0];
    let mut best = a[0];

    for &x in a.iter().skip(1) {
        let a_cand = min_e * x;
        let b_cand = max_e * x;
        // old min * negative becomes the new max, old max * negative the new min
        min_e = x.min(a_cand).min(b_cand);
        max_e = x.max(a_cand).max(b_cand);
        best = best.max(max_e);
    }
    best
}

fn main() {
    let best = max_product_subarray(&[-2, 3, -4]);
    assert_eq!(best, 24);
    println!("max product: {best} (the two negatives cancel)");
}

/// Maximum sum over subarrays of length EXACTLY `k`. Sliding window, not Kadane.
pub fn max_subarray_len_k(a: &[i32], k: usize) -> i32 {
    if a.len() < k {
        return 0;
    }
    a.windows(k).map(|w| w.iter().sum()).max().unwrap_or(0)
}

fn main() {
    let best = max_subarray_len_k(&[1, 4, 2, 10, 23, 3, 1, 0, 20], 4);
    assert_eq!(best, 39);
    println!("best window of exactly 4: {best}");
}

/// Maximum subarray sum with length at least `k`. Sliding window plus a Kadane
/// prefix carried in with `Iterator::scan`.
pub fn max_subarray_at_least_k(a: &[i32], k: usize) -> i32 {
    if a.is_empty() || a.len() < k {
        return 0;
    }
    if a.len() == k {
        return a.iter().sum();
    }

    // sums[i] = sum of the length-k window starting at i
    let sums: Vec<i32> = a.windows(k).map(|w| w.iter().sum()).collect();

    // best[i] = max(0, Kadane ending at i); scan keeps the running state
    let best: Vec<i32> = a
        .iter()
        .scan(0i32, |cur, &x| {
            *cur = x.max(*cur + x);
            Some((*cur).max(0))
        })
        .collect();

    // for each window: window sum + best Kadane prefix ending before the window
    sums.iter()
        .zip(best.iter().skip(k))
        .map(|(window, kadane)| window + kadane)
        .max()
        .unwrap()
}

fn main() {
    let best = max_subarray_at_least_k(&[1, 2, 3, -10, 4, 5], 3);
    assert_eq!(best, 6);
    println!("best sum with length >= 3: {best}");
}

/// Max double slice: `a[X+1..=Y-1] + a[Y+1..=Z-1]` with `0 <= X < Y < Z < N`.
///
/// Bidirectional Kadane: `left[i]` is the best slice ending before `i`, `right[i]`
/// the best slice starting after `i`; answer is `max(left[Y-1] + right[Y+1])`.
pub fn max_double_slice(a: &[i32]) -> i32 {
    if a.len() <= 3 {
        // minimal valid X=0, Y=1, Z=2 gives two empty slices = 0
        return 0;
    }
    let n = a.len();
    let mut left = vec![0i32; n];
    let mut right = vec![0i32; n];

    // left[i] = best subarray sum ending at i, floored at 0 (empty slices allowed)
    let mut cur = 0;
    for (idx, &x) in a.iter().enumerate().skip(1) {
        cur = (cur + x).max(0);
        left[idx] = cur;
    }

    // right[i] = the same from the right; enumerate().rev() keeps the original
    // index (n-1, n-2, ...) so there is no need to reverse afterwards
    let mut cur = 0;
    for (idx, &x) in a.iter().enumerate().rev().skip(1) {
        cur = (cur + x).max(0);
        right[idx] = cur;
    }

    // Y in 1..n-1, maximize left[Y-1] + right[Y+1]; substitute i = Y-1
    (0..n - 2).map(|i| left[i] + right[i + 2]).max().unwrap()
}

fn main() {
    let best = max_double_slice(&[3, 2, 6, -1, 4, 5, -1, 2]);
    assert_eq!(best, 17);
    println!("max double slice: {best}");
}

/// Maximum profit from a single buy/sell. Kadane over consecutive price diffs.
pub fn max_profit_kadane(prices: &[i32]) -> i32 {
    if prices.len() < 2 {
        return 0;
    }
    let mut current = 0;
    let mut best = 0;
    for window in prices.windows(2) {
        let diff = window[1] - window[0];
        current = diff.max(current + diff);
        best = best.max(current);
    }
    best.max(0)
}

fn main() {
    let p = max_profit_kadane(&[7, 1, 5, 3, 6, 4]);
    assert_eq!(p, 5);
    println!("max profit: {p} (buy at 1, sell at 6)");
}

use std::cmp::Ordering;

/// Minimum `|a[i] + a[j]|`. Sort, then two pointers from both ends.
/// The pair may use the same index (i == j).
pub fn min_abs_sum_of_two(a: &[i32]) -> i32 {
    let mut sorted = a.to_vec();
    sorted.sort();

    let (mut lo, mut hi) = (0, a.len() - 1);
    let mut best = (sorted[lo] + sorted[hi]).abs();

    while lo != hi - 1 {
        let s = sorted[lo] + sorted[hi];
        best = best.min(s.abs());
        match s.cmp(&0) {
            Ordering::Greater => hi -= 1, // need a smaller sum
            Ordering::Less => lo += 1,    // need a larger sum
            Ordering::Equal => return 0,
        }
    }

    // all-negative / all-positive: the optimum can be the doubled value closest
    // to zero from either end
    best = best.min((2 * sorted[lo]).abs());
    best = best.min((2 * sorted[hi]).abs());
    best
}

fn main() {
    let m = min_abs_sum_of_two(&[-8, 4, 5, -10, 3]);
    assert_eq!(m, 3);
    println!("min |a[i] + a[j]|: {m}");
}

/// Count triples `(P, Q, R)` with `P < Q < R` and `a[P] + a[Q] > a[R]`.
/// After sorting, a single inequality suffices and a failed `R` lets us break.
pub fn count_triangles(a: &[i32]) -> i32 {
    let mut sorted = a.to_vec();
    sorted.sort();
    let mut count = 0;
    for p in 0..a.len() {
        for q in (p + 1)..a.len() {
            for r in (q + 1)..a.len() {
                if sorted[p] + sorted[q] > sorted[r] {
                    count += 1;
                } else {
                    break; // everything past r is only larger
                }
            }
        }
    }
    count
}

fn main() {
    let t = count_triangles(&[10, 2, 5, 1, 8, 12]);
    assert_eq!(t, 4);
    println!("triangle triples: {t}");
}

/// Line sweep: number of intersecting discs (center `i`, radius `a[i]`).
/// Returns -1 if the count exceeds 10_000_000.
pub fn disc_intersections(a: &[i32]) -> i32 {
    let n = a.len();
    if n < 2 {
        return 0;
    }
    // each disc -> [i - a[i], i + a[i]]; i64 avoids overflow at the edges
    let (mut starts, mut ends): (Vec<i64>, Vec<i64>) = a
        .iter()
        .enumerate()
        .map(|(i, &r)| (i as i64 - r as i64, i as i64 + r as i64))
        .unzip();
    starts.sort();
    ends.sort();

    let mut count: i64 = 0;
    let mut active: i64 = 0;
    let mut j = 0;
    for &s in &starts {
        // close every disc that ended before this start
        while j < n && ends[j] < s {
            j += 1;
            active -= 1;
        }
        count += active; // the new disc intersects every currently open one
        active += 1;
        if count > 10_000_000 {
            return -1;
        }
    }
    count as i32
}

fn main() {
    let pairs = disc_intersections(&[1, 5, 2, 1, 4, 0]);
    assert_eq!(pairs, 11);
    println!("intersecting disc pairs: {pairs}");
}

Prefix sums

The shape: pay O(n) once, answer every range-sum query in O(1) as prefix[r+1] - prefix[l]. The table has n + 1 entries with a leading zero, and that extra zero is exactly what makes the subtraction valid at l = 0.

• Off-by-one lives in the table size: prefix.len() == a.len() + 1, always.
• “Count subarrays with sum K” is the same table plus a HashMap of seen prefixes.
• Sums of many i32 values overflow: accumulate in i64 when n is large.

/// Answer each `(l, r)` query with `sum(a[l..=r])`. O(n) preprocess, O(1) per query.
pub fn range_sum(a: &[i32], queries: &[(usize, usize)]) -> Vec<i32> {
    let mut prefix = vec![0i32; a.len() + 1];
    for i in 0..a.len() {
        prefix[i + 1] = prefix[i] + a[i];
    }

    queries.iter().map(|&(l, r)| prefix[r + 1] - prefix[l]).collect()
}

fn main() {
    let sums = range_sum(&[1, 2, 3, 4, 5], &[(0, 1), (2, 4), (1, 3)]);
    assert_eq!(sums, vec![3, 12, 9]);
    println!("range sums: {sums:?}");
}

Stacks

The shape: a Vec is the stack. For balanced brackets, push the EXPECTED closing character so all closers collapse into one comparison. A monotonic stack holds indices whose values stay sorted; each element is pushed and popped at most once, so the whole scan is O(n) even with the inner while loop.

• Store indices on a monotonic stack, not values: you need the index to write the answer.
• If the question only asks for depth, a counter replaces the stack entirely.

/// Balanced brackets `() [] {}`. Push the EXPECTED closing char, then on a
/// closing char check the top. Pushing the expectation collapses the three
/// closing branches into one.
pub fn brackets(s: &str) -> bool {
    let mut stack: Vec<char> = Vec::new();

    for c in s.chars() {
        match c {
            '{' => stack.push('}'),
            '[' => stack.push(']'),
            '(' => stack.push(')'),
            '}' | ']' | ')' if stack.pop() != Some(c) => return false,
            _ => {}
        }
    }

    stack.is_empty() // every opener must have been matched
}

fn main() {
    let ok = brackets("{{[[(())]]}}");
    let bad = brackets("([)]");
    assert!(ok && !bad);
    println!("nested: {ok}, interleaved: {bad}");
}

/// Next greater element to the right for each position, monotonic stack O(n).
pub fn next_greater(a: &[i32]) -> Vec<i32> {
    let mut result = vec![-1; a.len()];
    // the stack holds INDICES still waiting for their next-greater; their values
    // are monotonically decreasing
    let mut stack: Vec<usize> = Vec::new();
    for i in 0..a.len() {
        while let Some(&top) = stack.last() {
            if a[top] < a[i] {
                result[top] = a[i]; // a[i] is the next greater for `top`
                stack.pop();
            } else {
                break;
            }
        }
        stack.push(i);
    }
    // indices left on the stack have no greater element, they keep the -1 default
    result
}

fn main() {
    let ng = next_greater(&[2, 7, 3, 5, 4, 6, 8]);
    assert_eq!(ng, vec![7, 8, 5, 6, 6, 8, -1]);
    println!("next greater: {ng:?}");
}

/// Maximum nesting depth: `()()` -> 1, `(())` -> 2. A counter suffices; a stack
/// would just stay in lockstep with it. Returns -1 if a closer is unmatched.
pub fn max_nesting_depth(s: &str) -> i32 {
    let mut current_depth = 0;
    let mut max_depth = 0;

    for c in s.chars() {
        match c {
            '(' => {
                current_depth += 1;
                max_depth = max_depth.max(current_depth);
            }
            ')' => {
                if current_depth == 0 {
                    return -1; // unbalanced: a closer with no opener
                }
                current_depth -= 1;
            }
            _ => {}
        }
    }
    max_depth
}

fn main() {
    let d = max_nesting_depth("(()(()))");
    assert_eq!(d, 3);
    println!("max depth: {d}");
}

Greedy

The shape: sort by the RIGHT key, then take in one pass. Interval scheduling sorts by end (not start, not duration). Waiting time sorts by duration ascending. The proof pattern behind each is an exchange argument: swapping any other choice for the greedy one never makes the result worse.

• Read the spec for the boundary: “back-to-back allowed” is >=, “strict gap” is >. Closed segments compare with strict >.
• When the input is pre-sorted by the key you need, skip your own sort and say so, that is an O(n log n) to O(n) win for free.
• In max_profit update the minimum AFTER computing today’s profit, or you trade with yourself.

/// Activity selection (interval scheduling): maximum number of non-overlapping
/// activities. Sort by END ascending, then take greedily (exchange argument).
pub fn activity_selection(start: &[i32], end: &[i32]) -> i32 {
    if start.is_empty() {
        return 0;
    }
    let mut activities: Vec<(i32, i32)> = start.iter().zip(end).map(|(&s, &e)| (s, e)).collect();
    activities.sort_by_key(|&(_, e)| e); // sorting by end is what makes it optimal

    let mut count = 1;
    let mut last_end = activities[0].1;
    for &(s, e) in &activities[1..] {
        if s >= last_end {
            // no collision (end is exclusive)
            count += 1;
            last_end = e;
        }
    }
    count
}

fn main() {
    let n = activity_selection(&[1, 3, 0, 5, 8, 5], &[2, 4, 6, 7, 9, 9]);
    assert_eq!(n, 4);
    println!("max non-overlapping activities: {n}");
}

/// Maximum non-overlapping closed segments `[a[i], b[i]]`, input already sorted
/// by `b[i]`. The `>` is strict because the segments are closed.
pub fn max_nonoverlapping(a: &[i32], b: &[i32]) -> i32 {
    if a.is_empty() {
        return 0;
    }
    let mut count = 1;
    let mut last_end = b[0];
    for (&ai, &bi) in a.iter().zip(b.iter()).skip(1) {
        if ai > last_end {
            count += 1;
            last_end = bi;
        }
    }
    count
}

fn main() {
    let n = max_nonoverlapping(&[1, 3, 7, 9, 9], &[5, 6, 8, 9, 10]);
    assert_eq!(n, 3);
    println!("max non-overlapping segments: {n}");
}

/// Maximum profit from a single buy/sell. Single pass, tracking the min so far.
pub fn max_profit(prices: &[i32]) -> i32 {
    if prices.is_empty() {
        return 0;
    }
    let mut min_so_far = prices[0];
    let mut best = 0;
    for &price in &prices[1..] {
        best = best.max(price - min_so_far); // sell today against the cheapest seen
        min_so_far = min_so_far.min(price); // update the min AFTER computing profit
    }
    best
}

fn main() {
    let p = max_profit(&[7, 1, 5, 3, 6, 4]);
    assert_eq!(p, 5);
    println!("max profit: {p}");
}

/// Minimum total waiting time. Sort ascending; element i makes the `n-1-i`
/// people behind it wait `a[i]` longer.
pub fn min_waiting_time(a: &[i32]) -> i32 {
    let mut a = a.to_vec();
    a.sort();
    let n = a.len();
    a.iter().enumerate().map(|(i, &x)| x * (n - 1 - i) as i32).sum()
}

fn main() {
    let w = min_waiting_time(&[3, 2, 1]);
    assert_eq!(w, 4);
    println!("min total waiting time: {w}");
}

Digits greedy

The shape: digit problems are greedy over a string, and position weight decides everything, a change at an earlier position always outweighs a later one. Four sub-patterns: monotonic-stack removal, sort-then-adjust to meet a constraint, precompute a rightmost-occurrence table then scan from the left, and counting plus parity.

• Post-process the stack version: leftover budget pops from the END, strip leading zeros, and map an empty result to "0".
• For one-swap maximum, swap with the RIGHTMOST occurrence of the bigger digit, it keeps the smaller digits earlier.
• Digits are 0..=9: a fixed [i32; 10] beats a HashMap every time.

/// Remove `k` digits to make the smallest possible number. Monotonic-stack greedy.
pub fn remove_k_digits(s: &str, k: usize) -> String {
    let mut stack: Vec<char> = Vec::new();
    let mut k = k;

    for c in s.chars() {
        // while the top is larger than c and we still have budget, drop it:
        // removing a big digit at an earlier position lowers the number more
        while let Some(&top) = stack.last() {
            if top > c && k > 0 {
                stack.pop();
                k -= 1;
            } else {
                break;
            }
        }
        stack.push(c);
    }

    // unused budget: pop from the end (the stack is non-decreasing, so the tail is largest)
    while k > 0 {
        stack.pop();
        k -= 1;
    }

    // strip leading zeros, and never return an empty string
    let trimmed: String = stack.into_iter().skip_while(|&c| c == '0').collect();
    if trimmed.is_empty() {
        "0".to_string()
    } else {
        trimmed
    }
}

fn main() {
    let small = remove_k_digits("1432219", 3);
    assert_eq!(small, "1219");
    println!("smallest after removing 3 digits: {small}");
}

use std::cmp::Reverse;

/// Largest even number formable from `digits`. Sort descending, then sacrifice
/// the smallest even digit to the last position.
pub fn largest_even_number(digits: &str) -> String {
    let mut chars: Vec<char> = digits.chars().collect();
    if chars.is_empty() {
        return "0".to_string();
    }
    chars.sort_by_key(|&c| Reverse(c)); // descending for the theoretical maximum
    let n = chars.len();

    // already even at the end: done
    if matches!(chars[n - 1], '0' | '2' | '4' | '6' | '8') {
        return chars.iter().collect();
    }

    // otherwise swap the rightmost even digit (the smallest one after the sort)
    // into the last position, keeping the larger digits on the left
    if let Some(i) = chars[..n - 1]
        .iter()
        .rposition(|&c| matches!(c, '0' | '2' | '4' | '6' | '8'))
    {
        chars.swap(i, n - 1);
        return chars.iter().collect();
    }

    "0".to_string() // no even digit: impossible
}

fn main() {
    let big = largest_even_number("123456");
    assert_eq!(big, "654312");
    println!("largest even: {big}");
}

/// Maximum value after at most ONE swap of two digits.
pub fn maximum_swap(n: i32) -> i32 {
    let mut chars: Vec<char> = n.to_string().chars().collect();
    let len = chars.len();

    // last[d] = rightmost index where digit d occurs
    let mut last = [0usize; 10];
    for (i, &c) in chars.iter().enumerate() {
        let d = c.to_digit(10).unwrap() as usize;
        last[d] = i;
    }

    // for each position, find the largest digit > current that occurs LATER
    for i in 0..len {
        let current = chars[i].to_digit(10).unwrap() as usize;
        if let Some(d) = ((current + 1)..=9).rev().find(|&d| last[d] > i) {
            // using the rightmost occurrence keeps smaller digits in the middle
            chars.swap(i, last[d]);
            return chars.iter().collect::<String>().parse().unwrap();
        }
    }

    n // no beneficial swap
}

fn main() {
    let m = maximum_swap(2736);
    assert_eq!(m, 7236);
    println!("2736 -> {m}");
}

/// Minimum removals so every digit occurs an even number of times.
pub fn min_removals_even_counts(digits: &str) -> i32 {
    // digits are 0-9, so a fixed array beats a HashMap
    let mut count = [0i32; 10];
    for c in digits.chars() {
        let d = c.to_digit(10).unwrap() as usize;
        count[d] += 1;
    }

    // each digit with an odd count needs exactly one removal
    count.iter().filter(|&&c| c % 2 == 1).count() as i32
}

fn main() {
    let r = min_removals_even_counts("11221");
    assert_eq!(r, 1);
    println!("removals needed: {r}");
}

Number theory

The shape: the sieve of Eratosthenes runs the outer loop only to sqrt(n) and starts crossing off at i * i, smaller multiples were already handled by smaller primes. Divisor enumeration pairs d with x / d up to sqrt(x). When the problem asks many range queries, preprocess once (sieve, flags, prefix sums) and answer each query in O(1).

• Table size is n + 1: you want index n to be valid.
• Perfect squares: guard d == x / d or the root gets counted twice.
• GCD goes iterative, (a, b) = (b, a % b), Rust has no tail-call optimization.

/// Sieve of Eratosthenes. `result[i]` is true iff `i` is prime.
pub fn sieve(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    if n >= 1 {
        is_prime[1] = false;
    }

    // only sieve up to sqrt(n): a larger prime has no multiple left in range
    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            // start at i*i; smaller multiples were already crossed off by smaller primes
            for j in (i * i..=n).step_by(i) {
                is_prime[j] = false;
            }
        }
        i += 1;
    }
    is_prime
}

fn main() {
    let s = sieve(30);
    let primes: Vec<usize> = (0..=30).filter(|&i| s[i]).collect();
    assert_eq!(primes, vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
    println!("primes up to 30: {primes:?}");
}

/// For each `a[i]`, count how many elements do NOT divide it.
pub fn count_non_divisible(a: &[i32]) -> Vec<i32> {
    let n = a.len();
    if n == 0 {
        return Vec::new();
    }
    // count[v] = how many times v appears in a (bucket array)
    let max_val = *a.iter().max().unwrap() as usize;
    let mut count = vec![0i32; max_val + 1];
    for &x in a {
        count[x as usize] += 1;
    }

    let total = n as i32;
    a.iter()
        .map(|&x| {
            let xu = x as usize;
            // pair d with x/d in O(sqrt(x)); the `d == xu/d` guard avoids
            // double counting a perfect square's root
            let divisors_count: i32 = (1..)
                .take_while(|&d| d * d <= xu)
                .filter(|&d| xu % d == 0)
                .map(|d| if d == xu / d { count[d] } else { count[d] + count[xu / d] })
                .sum();
            total - divisors_count
        })
        .collect()
}

fn main() {
    let counts = count_non_divisible(&[3, 1, 2, 3, 6]);
    assert_eq!(counts, vec![2, 4, 3, 2, 0]);
    println!("non-divisors per element: {counts:?}");
}

/// Sieve of Eratosthenes. `result[i]` is true iff `i` is prime.
pub fn sieve(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    if n >= 1 {
        is_prime[1] = false;
    }

    // only sieve up to sqrt(n): a larger prime has no multiple left in range
    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            // start at i*i; smaller multiples were already crossed off by smaller primes
            for j in (i * i..=n).step_by(i) {
                is_prime[j] = false;
            }
        }
        i += 1;
    }
    is_prime
}

/// Count semiprimes (a product of exactly two primes: 4=2*2, 6=2*3, 9=3*3) in
/// each query range `[p[i], q[i]]` within `1..=n`.
pub fn count_semiprimes(n: i32, p: &[i32], q: &[i32]) -> Vec<i32> {
    let n = n as usize;
    let is_prime = sieve(n);

    let mut is_semi = vec![false; n + 1];
    for i in 2..=n {
        // look for a factorization d * (i/d) where both factors are prime
        is_semi[i] = (2..)
            .take_while(|&d| d * d <= i)
            .any(|d| i % d == 0 && is_prime[d] && is_prime[i / d]);
    }

    // prefix sums for O(1) per query
    let mut prefix = vec![0i32; n + 2];
    for i in 1..=n {
        prefix[i + 1] = prefix[i] + is_semi[i] as i32;
    }

    p.iter()
        .zip(q.iter())
        .map(|(&pk, &qk)| prefix[qk as usize + 1] - prefix[pk as usize])
        .collect()
}

fn main() {
    let counts = count_semiprimes(26, &[1, 4, 16], &[26, 10, 20]);
    assert_eq!(counts, vec![10, 4, 0]);
    println!("semiprimes per query range: {counts:?}");
}

/// Euclidean algorithm: `gcd(a, b) = gcd(b, a mod b)`, base `gcd(a, 0) = a`.
/// Iterative (Rust has no tail-call optimization, so recursion could overflow).
pub fn gcd(mut a: i64, mut b: i64) -> i64 {
    while b != 0 {
        (a, b) = (b, a % b);
    }
    a
}

fn main() {
    let g = gcd(48, 18);
    assert_eq!(g, 6);
    println!("gcd(48, 18) = {g}");
}

Grid symmetry

The shape: requiring every row AND every column to be a palindrome ties each cell to a group of four mirrored cells, and the cheapest fix per group is min(blacks, whites) flips. Cells on the middle row or column collapse into smaller groups, which a HashSet handles for free. Per-row palindrome checks are one iterator chain: zip(rev()).take(m/2).

• .all() short-circuits on the first mismatch, .filter().count() when you need how many.
• take(m / 2) skips the middle of an odd-length row, it has no pair.

use std::collections::HashSet;

/// Minimum flips so every row AND every column is a palindrome simultaneously.
///
/// Two axes of symmetry tie each cell to a group of four mirrored cells (with
/// duplicates on the middle row/column, removed by the `HashSet`).
pub fn grid_symmetry(grid: &[String]) -> i32 {
    if grid.is_empty() {
        return 0;
    }
    let n = grid.len();
    let m = grid[0].chars().count();
    if m == 0 {
        return 0;
    }

    let chars: Vec<Vec<char>> = grid.iter().map(|s| s.chars().collect()).collect();

    let mut visited = vec![vec![false; m]; n];
    let mut total = 0;

    for i in 0..n {
        for j in 0..m {
            if visited[i][j] {
                continue;
            }
            let ni = n - 1 - i;
            let nj = m - 1 - j;
            let cells: HashSet<(usize, usize)> =
                [(i, j), (i, nj), (ni, j), (ni, nj)].into_iter().collect();

            for &(x, y) in &cells {
                visited[x][y] = true;
            }
            let b = cells.iter().filter(|&&(x, y)| chars[x][y] == 'B').count();
            let w = cells.iter().filter(|&&(x, y)| chars[x][y] == 'W').count();
            // flip the smaller colour so the whole group matches
            total += b.min(w) as i32;
        }
    }
    total
}

fn main() {
    let grid = vec!["BBB".to_string(), "BWB".to_string(), "WBW".to_string()];
    let flips = grid_symmetry(&grid);
    assert_eq!(flips, 2);
    println!("min flips for full symmetry: {flips}");
}

/// Count broken mirror pairs per row (column `j` against `m-1-j`).
pub fn count_broken_pairs(grid: &[String]) -> i32 {
    if grid.is_empty() {
        return 0;
    }
    let m = grid[0].chars().count();
    if m <= 1 {
        return 0; // a single column has no pairs
    }

    grid.iter()
        .map(|s| {
            let row: Vec<char> = s.chars().collect();
            // pairs (j, m-1-j) for j < m-1-j; the middle of an odd row has no pair
            row.iter()
                .zip(row.iter().rev())
                .take(m / 2)
                .filter(|(a, b)| a != b)
                .count() as i32
        })
        .sum()
}

fn main() {
    let grid = vec!["BWBW".to_string(), "BWWB".to_string()];
    let broken = count_broken_pairs(&grid);
    assert_eq!(broken, 2);
    println!("broken mirror pairs: {broken}");
}

/// Count rows that are palindromes.
pub fn count_symmetric_rows(grid: &[String]) -> usize {
    if grid.is_empty() {
        return 0;
    }
    grid.iter()
        .filter(|s| {
            let chars: Vec<char> = s.chars().collect();
            let m = chars.len();
            // `.all` short-circuits on the first mismatch
            chars.iter().zip(chars.iter().rev()).take(m / 2).all(|(a, b)| a == b)
        })
        .count()
}

fn main() {
    let grid = vec!["BWB".to_string(), "BBW".to_string(), "WWW".to_string()];
    let sym = count_symmetric_rows(&grid);
    assert_eq!(sym, 2);
    println!("palindrome rows: {sym}");
}