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.
///
/// Initiali