DSA

Sort nonnegative integers digit by digit, starting with the least significant decimal digit. Each digit pass uses stable buckets.

02Data structures

Tries / prefix trees

Insert words character by character, reusing shared prefixes. A terminal marker records a complete word even when that word is also a prefix of another.

03Graphs

Repeatedly settle the unsettled vertex with minimum tentative distance, then relax its outgoing edges. The fixed graph has only nonnegative weights. This trace uses a linear scan to select the minimum.

04Graphs

Topological sorting

Use Kahn’s algorithm on a fixed directed acyclic graph. Remove zero-indegree vertices and reduce their outgoing neighbours’ indegrees.

05Graphs

Union–find / disjoint sets

Process undirected edges, find the root of each endpoint and merge distinct components. Union by rank and path compression keep trees shallow.

06Dynamic programming

0/1 knapsack

Choose from four fixed items with weights 2,3,4,5 and values 3,4,5,8. Each item can be used at most once. A table records the best value for each item prefix and capacity.

07Dynamic programming

Longest common subsequence

Compare two strings, separated by |. A subsequence preserves order but may skip characters; it need not be contiguous. The table returns the LCS length.

08Dynamic programming

Coin change / minimum coins

Find the fewest coins for an exact target, with unlimited uses of each positive denomination. Unreachable states remain ∞. Zero denominations are not allowed.

09Backtracking

N-Queens / backtracking

Place one queen per row so no two share a column or diagonal. Try a column, recurse to the next row, and undo a placement if the branch fails. Stop at the first solution.

10Range-query structures

Fenwick trees / prefix queries

Build a one-based binary indexed tree, then query the first k values. Each node stores a block whose length is its least significant set bit.

11Range-query structures

Segment trees / range sums

Build a binary hierarchy of interval sums, then query the first k values. A fully covered segment contributes its stored sum; a disjoint segment contributes zero.

12Graphs

Kruskal / minimum spanning tree

Sort the fixed connected undirected graph’s weighted edges and accept an edge only when it joins different components. Stop after V−1 accepted edges.

13Graphs

Bellman–Ford shortest paths

Relax every edge repeatedly on a directed graph that includes a negative edge but no negative cycle. A final extra pass checks for a reachable negative cycle.

14Strings

KMP string matching

Search text for a pattern, separated by |. Build the pattern’s longest-prefix-suffix table, then reuse it on mismatches without moving the text pointer backwards. Matching is case-sensitive.