Every algorithm explained the way it should be — one step at a time, with the code highlighting in sync with what you see. No memorising. Just watching it click.
8
Topic Areas
70+
Concepts Covered
50
Practice Questions
∞
Free, Always
0%
Your Progress
Beginner·Intermediate·Advanced
Before any algorithm, you need a ruler to measure it with. Big-O isn't about counting exact operations — it's about how the work grows when the input grows. Watch the curves below; the gap between them is the entire reason DSA matters.
01
Time & Space Complexity
Plain English
Time complexity asks "how many steps as input grows?" Space complexity asks "how much extra memory as input grows?" Both are described using Big-O — the worst-case growth rate, ignoring constants.
Analogy: Looking up a word in a phone book by flipping page-by-page is O(n) — double the book, double the worst-case flips. Looking it up by jumping to the middle each time (because it's alphabetised) is O(log n) — double the book, only +1 flip.
Θ (Theta): tight bound — exact growth rate, both upper and lower.
Ω (Omega): best-case lower bound — the fastest it could ever run.
O (Big-O): worst-case upper bound — what GATE almost always asks for.
Amortised: average cost per operation across a sequence (e.g. dynamic array resizing).
GATE tip: when a loop halves input each time → log n. Nested loops over n → usually n².
O(1) constant
O(log n) logarithmic
O(n) linear
O(n log n) linearithmic
O(n²) quadratic
O(2ⁿ) exponential
02
Recurrence Relations & The Master Theorem
Plain English
Every recursive algorithm's running time can be written as a recurrence — T(n) defined in terms of T(smaller n). The Master Theorem lets you solve the most common shape of recurrence by inspection, without expanding a recursion tree by hand every time.
The Master Theorem
T(n) = a·T(n/b) + f(n), a ≥ 1, b > 1
Compare f(n) against nlogba — this single comparison decides everything:
GATE tip: if a depends on n, or f(n) isn't polynomially comparable to nlog_b a, the Master Theorem doesn't apply — fall back to the recursion-tree or substitution method.
Summations that show up constantly in derivations
Σi=1n i = n(n+1)/2 = Θ(n²)
Σi=0n 2i = 2n+1 − 1 = Θ(2ⁿ)
Σi=1n 1/i ≈ ln(n) = Θ(log n) — the harmonic series
These three identities are the algebra behind almost every "derive the complexity" question — recognise the shape, plug in, done.
Practice Questions — Foundations
Beginner·Intermediate·Advanced
Linear structures store data in a sequence — the difference between them is entirely about the trade-off between fast access and fast insertion. Master this trade-off and half of interview prep becomes pattern recognition.
01
Arrays & Two-Pointer / Sliding Window
Plain English
An array is a row of labelled boxes in memory — O(1) access by index, but inserting in the middle means shifting every box after it. Two-pointer and sliding-window are techniques that scan an array with one or two markers instead of nested loops, turning O(n²) brute force into O(n).
Analogy: Two-pointer is like two people walking towards each other from opposite ends of a queue, checking pairs as they meet in the middle — far faster than one person checking every pair.
Two-pointer: e.g. "pair sums to target" in a sorted array — move left/right pointers inward.
Sliding window: e.g. "longest substring without repeats" — expand/shrink a window over the array.
GATE tip: array search is O(n); sorted array binary search is O(log n).
Space: arrays are contiguous — cache-friendly, unlike linked lists.
Access O(1)
Search O(n)
Insert/Delete (middle) O(n)
02
Linked Lists — Singly, Doubly, Circular
Plain English
Instead of one contiguous block, a linked list is scattered nodes each holding a value and a pointer to the next. Insertion/deletion at the front is O(1) — no shifting needed — but you lose O(1) random access entirely.
Analogy: A treasure hunt where each clue tells you where to find the next clue. You can't jump to clue #7 directly — you must walk the whole chain from the start.
Singly: each node points only forward.
Doubly: each node points forward and backward — easy reverse traversal.
Circular: the last node points back to the first — used in round-robin scheduling.
GATE tip: "detect a cycle" → Floyd's slow/fast pointer (tortoise & hare), O(n) time O(1) space.
03
Stacks & Queues
Plain English
A stack is Last-In-First-Out (LIFO) — push and pop only from the top. A queue is First-In-First-Out (FIFO) — enqueue at the back, dequeue from the front. Both support O(1) insert/remove at their designated end.
Analogy: A stack is a pile of plates — you only ever take the top one. A queue is a ticket line — first person in line is served first.
Stack uses: function call stack, undo/redo, bracket matching, DFS.
Queue uses: task scheduling, BFS, print spoolers.
Deque: insert/remove from both ends — used in sliding-window maximum.
GATE tip: a queue can be built from two stacks, and vice versa — classic question.
04
Hash Tables
Plain English
A hash table maps a key to a value using a hash function that converts the key into an array index — giving average O(1) lookup, insert, and delete. Collisions (two keys hashing to the same slot) are resolved via chaining or open addressing.
Analogy: A coat check — you hand over your coat (the value), get a numbered ticket (the hash), and retrieve it instantly later without searching every hook.
Chaining: each slot holds a linked list of all keys that hash there.
Open addressing: on collision, probe the next available slot.
GATE tip: worst-case hash lookup is O(n) — all keys collide into one slot.
Load Factor & Expected Cost
α = n / m (n = entries stored, m = number of slots)
Chaining: expected chain length searched ≈ α. Open addressing (uniform hashing): expected probes ≈ 1/(1−α) for insert, ½·(1 + 1/(1−α)) for a successful search — this is why α approaching 1 makes open addressing fall off a cliff.
05
Disjoint Set / Union-Find
Plain English
A Disjoint Set tracks a collection of non-overlapping groups and answers one question fast: "are these two elements in the same group?" Two operations: Find (which group is x in?) and Union (merge x's group with y's group). It's the engine behind Kruskal's MST — you skip any edge that would connect two nodes already in the same group, since that edge would form a cycle.
Analogy: Think of friend groups at a party. "Find" asks "which clique is this person in?" "Union" is introducing two cliques to each other so they merge into one. Without any optimisation, tracing who-knows-who gets slow as cliques grow into long chains — which is exactly what the two tricks below fix.
Naive: Find walks parent pointers up to the root — O(n) worst case if the tree degenerates into a chain.
Union by rank/size: always attach the smaller tree under the bigger tree's root, keeping height bounded by O(log n).
Path compression: while doing Find, point every visited node directly at the root — future Finds on those nodes become O(1).
GATE tip: "detect a cycle in an undirected graph" and "Kruskal's MST" are the two questions where Union-Find shows up the most.
Amortised Complexity With Both Optimisations
m operations on n elements: O(m · α(n)) total ≈ O(m) in practice
α(n) here is the inverse Ackermann function — it grows so slowly that for any n you could ever actually store in memory, α(n) ≤ 4. In practice this means union-by-rank + path compression together make Find/Union effectively O(1) each, not just "fast."
Practice Questions — Linear Structures
Beginner·Intermediate·Advanced
Trees model hierarchy and order. Watch how a Binary Search Tree organises itself, then traverse it four different ways — the same tree, four different stories depending on the order you visit its nodes.
01
Binary Trees & BST
Plain English
A binary tree is a node with at most two children. A Binary Search Tree (BST) adds a rule: everything in the left subtree is smaller, everything in the right is larger. This rule alone gives O(log n) search on a balanced tree.
Analogy: A BST is the "guess my number, higher or lower" game made physical — every comparison eliminates one whole half of the remaining candidates.
AVL Tree: self-balancing BST — rotates after insert/delete to keep height ≈ log n.
Red-Black Tree: another self-balancing scheme, used inside many language libraries (e.g. C++ map).
GATE tip: an unbalanced BST degrades to a linked list — O(n) worst case search.
Height & Node Count
Balanced tree height: h = ⌊log2 n⌋
Max nodes in a tree of height h: 2h+1 − 1
Nodes at level i of a full binary tree: 2i
This is the entire reason BST search is O(log n) on a balanced tree: each comparison eliminates one whole subtree, so the number of comparisons can never exceed the height — and the height of a balanced tree grows logarithmically, not linearly, with n.
02
Tree Traversals
Inorder (Left → Node → Right): visits a BST in sorted order.
Preorder (Node → Left → Right): useful for copying a tree's structure.
Postorder (Left → Right → Node): useful for safely deleting a tree bottom-up.
Level-order (BFS): visits node by node, level by level, using a queue.
03
Heaps & Tries
Plain English
A heap is a tree where every parent is smaller (min-heap) or larger (max-heap) than its children — giving O(1) peek at the smallest/largest and O(log n) insert/remove. A trie stores strings letter-by-letter along tree paths, sharing common prefixes.
Analogy: A min-heap is a hospital triage queue — the most urgent case always floats to the front, even though the rest of the queue isn't fully sorted. A trie is a dictionary where every shared prefix (like "CAR" in "CARD" and "CART") is stored only once.
Trie uses: autocomplete, spell-checkers, IP routing tables.
GATE tip: a heap is usually array-backed — child of index i is at 2i+1 and 2i+2.
Array-Backed Heap — Index Formulas
Parent of i: ⌊(i−1)/2⌋ Left child: 2i+1 Right child: 2i+2
Build-heap total cost: Σh=0log n (n/2h+1)·h = O(n)
That last one is a classic GATE trap: it looks like n inserts × O(log n) each = O(n log n), but the sum is geometric and collapses to O(n) — building a heap from an unsorted array is linear, not linearithmic.
04
AVL Rotations — All 4 Cases
Plain English
An AVL tree is a BST that enforces one extra rule after every insert/delete: the heights of the two child subtrees of any node may differ by at most 1. The moment that balance breaks, a rotation — a local restructuring of 2-3 nodes — restores it in O(1), without touching the rest of the tree.
Balance Factor & The 4 Rotation Cases
Balance Factor(node) = height(left) − height(right), must stay in {−1, 0, 1}
LL case (left-left heavy) → single right rotation at the unbalanced node RR case (right-right heavy) → single left rotation LR case (left-right heavy) → left rotation on the child, then right rotation on the node RL case (right-left heavy) → right rotation on the child, then left rotation on the node
How to tell which case: look at the balance factor's sign at the unbalanced node, then at its heavier child — same direction twice (e.g. left-left) → single rotation; direction flips (left-right) → double rotation.
GATE tip: every rotation is O(1) — only pointers change, no subtree is re-copied — and at most one rotation (or one double-rotation) is ever needed per insert to rebalance the whole tree.
05
B-Trees & B+ Trees
Plain English
A B-Tree is a self-balancing tree where each node can hold many keys (not just 1) and have many children (not just 2) — built specifically to minimise disk reads, since one "node" maps to one disk block. B+ Trees go further: all actual data lives in the leaves, linked together, so a range scan never has to revisit internal nodes.
Analogy: A binary tree on disk would mean one slow disk seek per comparison. A B-Tree packs hundreds of keys per node, so one disk read lets you make hundreds of comparisons at once — this is exactly why every real database index is a B+ Tree, never a plain BST.
Order-m B-Tree Rules
Every node: ⌈m/2⌉ − 1 to m − 1 keys Every internal node: ⌈m/2⌉ to m children
Height stays O(logm n) — with m in the hundreds, that's effectively 2-3 disk reads to find anything, even across millions of records.
06
Segment Trees & Fenwick (BIT) Trees
Plain English
Both answer "range query" questions (sum/min/max over a[l..r]) faster than recomputing from scratch every time. A Segment Tree stores a value for every range in a binary-tree shape. A Fenwick Tree (Binary Indexed Tree) does the same job for prefix sums with far less code, exploiting binary representations of indices.
Segment Tree: build O(n), range query O(log n), point update O(log n). More general — supports min/max/gcd, not just sum.
Fenwick Tree: update and prefix-sum query both O(log n), with O(n) space and far less code than a segment tree.
GATE tip: "range sum query with updates" is the signature phrase for both — if updates never happen, a simple prefix-sum array (O(1) query) is enough and neither structure is needed.
Practice Questions — Trees & Heaps
Beginner·Intermediate·Advanced
Graphs are the most general structure in DSA — anything that's "things connected to other things" is a graph. Maps, social networks, dependency chains. Watch BFS spread outward in rings, then DFS plunge down one path at a time.
01
Representation — Adjacency List vs Matrix
Adjacency list: each node stores a list of its neighbours. Space O(V+E) — efficient for sparse graphs.
Adjacency matrix: a V×V grid, 1 if an edge exists. Space O(V²) — but O(1) edge lookup.
Handshake Lemma
Σv ∈ V deg(v) = 2|E|
Every edge touches exactly 2 vertices, so summing all degrees counts each edge twice — a one-line fact GATE loves to hide inside a longer question.
02
BFS & DFS
Plain English
BFS explores level by level using a queue — finds the shortest path in an unweighted graph. DFS dives as deep as possible down one branch using a stack (or recursion) before backtracking.
Analogy: BFS is ripples spreading outward from a stone dropped in water. DFS is exploring a maze by always taking the first unexplored turn and only backing up when you hit a dead end.
Both O(V + E)
03
Shortest Path — Dijkstra & Bellman-Ford
Dijkstra: greedy, picks the nearest unvisited node each step. Fails with negative edge weights. O((V+E) log V) with a heap.
Bellman-Ford: relaxes all edges V−1 times. Slower — O(V·E) — but handles negative weights and detects negative cycles.
Where Dijkstra's O((V+E) log V) Comes From
V × extract-min (O(log V) each) + E × decrease-key (O(log V) each) = O((V+E) log V)
Why V−1 relaxations for Bellman-Ford specifically: the shortest path between any two nodes visits at most V−1 edges (no point repeating a vertex), so V−1 full passes guarantee every shortest path has been found.
04
Minimum Spanning Tree — Kruskal & Prim
Kruskal: sort all edges by weight, add the smallest that doesn't form a cycle (Union-Find). O(E log E).
Prim: grow one tree from a start node, always adding the cheapest edge to a new node. O(E log V) with a heap.
Topological Sort: orders nodes in a DAG so every edge points forward — used for scheduling/build systems.
05
Floyd-Warshall — All-Pairs Shortest Path
Plain English
Dijkstra and Bellman-Ford both find shortest paths from one source. Floyd-Warshall finds shortest paths between every pair of nodes at once, by repeatedly asking "is it shorter to go through node k?" for every k.
The Recurrence
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] ) for every k = 1..V
Three nested loops (k, then i, then j) — that's where the O(V³) comes from directly. Handles negative edges (not negative cycles) and is simpler to code than running Dijkstra V times.
Time O(V³)
Space O(V²)
06
Strongly Connected Components — Tarjan & Kosaraju
Plain English
In a directed graph, a Strongly Connected Component (SCC) is a maximal group of nodes where every node can reach every other node in the group. Both algorithms find all SCCs in O(V+E) — Kosaraju does it with 2 DFS passes (one on the graph, one on its reverse), Tarjan does it in a single DFS pass using discovery times and low-links.
Kosaraju: DFS to get a finish-order; reverse all edges; DFS again in that order — each new DFS tree is one SCC.
Tarjan: tracks disc[] (when a node was first visited) and low[] (lowest disc reachable) in one pass; a node is an SCC root when disc[node] = low[node].
GATE tip: a graph is "strongly connected" (one single SCC) iff a DFS from any node reaches everything, AND the same is true on the reversed graph.
07
Articulation Points & Bridges
Plain English
An articulation point is a node whose removal disconnects the graph. A bridge is the same idea for an edge. Both are found with a single DFS, comparing each node's discovery time against the lowest discovery time reachable from its subtree.
The Core Test (DFS tree edge u→v)
Bridge: low[v] > disc[u]
Articulation point (u, non-root): low[v] ≥ disc[u] for some child v
In plain words: if nothing in v's subtree can reach back to u or earlier without using the edge u→v, then that edge (and u itself) is load-bearing for the graph's connectivity.
Real use: network reliability — a bridge/articulation point is a single point of failure.
GATE tip: the root of the DFS tree is an articulation point only if it has 2+ children in the DFS tree — a common off-by-one trap.
Practice Questions — Graphs
Beginner·Intermediate·Advanced
Watch the exact same 8 bars get sorted by three different algorithms below. Same input, wildly different journeys — that difference is the algorithm.
01
Selection Sort
Find the minimum of the unsorted remainder, swap it to the front, repeat. Always exactly n−1 swaps — fewest writes of any simple sort, which matters when writes are expensive (e.g. flash memory).
for i in 0..n-1:
minIdx = i
for j in i+1..n:
if arr[j] < arr[minIdx]: minIdx = j
swap(arr[i], arr[minIdx])
Best/Avg/Worst O(n²)
Space O(1)
Stable No
02
Insertion Sort
Build the sorted portion one element at a time — take the next unsorted element and shift it backward through the sorted portion until it's in the right place. Exactly how most people sort a hand of playing cards.
for i in 1..n:
key = arr[i]; j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j--
arr[j+1] = key
Best O(n)
Avg/Worst O(n²)
Space O(1)
GATE tip: on an already-sorted or nearly-sorted array, insertion sort runs close to O(n) — the inner while loop barely executes.
03
Merge Sort
Split the array in half recursively until each piece has 1 element, then merge pairs of sorted pieces back together. The "merge" step is the only real work — comparing the fronts of two sorted lists and taking the smaller each time.
mergeSort(arr):
if len(arr) <= 1: return arr
mid = len(arr) / 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right) # merge: O(n) per level
Pick a pivot, partition the array so smaller elements end up left of it and larger ones right (the pivot is now in its final position), then recurse on both sides. No extra array needed — partitioning happens in-place.
quickSort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi) # pivot lands at index p
quickSort(arr, lo, p-1)
quickSort(arr, p+1, hi)
Best/Average: pivot roughly splits the array in half each time → T(n)=2T(n/2)+O(n) → O(n log n).
Worst case: pivot is always the smallest/largest element (e.g. always picking arr[0] on an already-sorted array) → T(n)=T(n−1)+O(n) → O(n²).
GATE tip: randomised pivot selection makes the O(n²) worst case astronomically unlikely, not impossible — this is why production sorts randomise.
Best/Avg O(n log n)
Worst O(n²)
Space O(log n)
05
Heap Sort
Build a max-heap from the array (O(n), see the Trees & Heaps tab), then repeatedly swap the root — the largest remaining element — to the end and shrink the heap by 1, re-heapifying each time.
heapSort(arr):
buildMaxHeap(arr) # O(n)
for i in n-1 downto 1:
swap(arr[0], arr[i])
heapify(arr, 0, i) # O(log n), done n times
Best/Avg/Worst O(n log n)
Space O(1)
Stable No
GATE tip: the only major comparison sort that is both O(n log n) worst-case AND O(1) space — the trade-off is it's not stable and has worse cache locality than quicksort in practice.
Stability · In-Place · Complexity — Full Comparison
ALGORITHM
BEST
AVERAGE
WORST
SPACE
STABLE
IN-PLACE
Bubble Sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Yes
Selection Sort
O(n²)
O(n²)
O(n²)
O(1)
No
Yes
Insertion Sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Yes
Merge Sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Yes
No
Quick Sort
O(n log n)
O(n log n)
O(n²)
O(log n)
No
Yes
Heap Sort
O(n log n)
O(n log n)
O(n log n)
O(1)
No
Yes
Binary Search: requires a sorted array. Compare the middle element — if too big, search the left half; if too small, search the right half. O(log n) instead of O(n) linear scan.
Why No Comparison-Based Sort Beats O(n log n)
n elements have n! possible orderings
A decision tree of comparisons needs ≥ log2(n!) leaves to distinguish them all
log2(n!) = Θ(n log n) (Stirling's approximation)
This is a proven lower bound, not a coincidence — merge/quick/heap sort hitting Θ(n log n) means they're already optimal for comparison-based sorting. The only way to beat it (counting sort, radix sort, bucket sort) is to stop comparing elements and exploit something about their values instead.
Practice Questions — Sorting & Searching
Beginner·Intermediate·Advanced
Recursion is a function calling itself on a smaller version of the same problem. Backtracking adds one rule: if a path can't possibly work, abandon it immediately and try the next one. Watch the call stack grow and shrink live below.
01
The Call Stack
Every recursive call is pushed onto the call stack with its own local variables; it's popped off only once it returns a value. A function that never reaches its base case keeps pushing forever — that's a stack overflow.
Analogy: Russian nesting dolls — you must fully open the smallest doll before you can close any of the bigger ones around it.
02
N-Queens & Subset/Permutation Generation
N-Queens: place N queens on an N×N board so none attack another — backtrack the moment a placement conflicts.
Subsets: for each element, recursively choose "include" or "exclude" — generates all 2ⁿ subsets.
Permutations: swap each remaining element into the current position, recurse, then swap back ("undo" — the essence of backtracking).
Prune: the moment a partial solution can't possibly succeed, stop exploring that branch — this is what makes backtracking fast in practice despite exponential worst case.
Counting the Search Space
Subsets of n elements: 2n— each element is independently in or out
Permutations of n elements: n! Permutations choosing r of n: n!/(n−r)!
N-Queens raw placements: nn— pruning cuts this drastically in practice, but the unpruned bound is what makes brute force infeasible past n≈12
03
Divide & Conquer — The General Template
Plain English
Divide & Conquer is recursion with a specific 3-step shape: split the problem into smaller independent sub-problems (divide), solve each recursively (conquer), then combine their results (combine). Merge sort, quick sort, and binary search are all this exact template — the only thing that changes is what "combine" means.
solve(problem):
if problem is small enough: return baseCase(problem)
parts = divide(problem)
results = [solve(p) for p in parts]
return combine(results)
Merge sort: divide = split in half, combine = merge two sorted halves — O(n) combine.
Binary search: divide = pick a half based on comparison, combine = trivial (nothing to merge).
GATE tip: if combine costs more than the divide step saves, D&C isn't worth it — that's exactly what the Master Theorem's f(n) term is measuring.
04
Branch & Bound
Plain English
Branch & Bound is backtracking's cousin for optimisation problems (minimise/maximise something, not just "find any valid answer"). At each branch, compute a bound — the best possible outcome that branch could ever reach — and discard the branch immediately if that bound is already worse than the best solution found so far.
Analogy: Backtracking abandons a branch only when it's outright invalid. Branch & Bound abandons a branch even when it's still valid, the moment it's provably not going to beat what you already have — like quitting a hand of cards early once you can see you can't possibly win it.
GATE tip: Branch & Bound vs plain Backtracking — both prune, but B&B prunes using a numeric bound on the objective function, backtracking prunes using a yes/no constraint check.
Practice Questions — Recursion & Backtracking
Beginner·Intermediate·Advanced
Dynamic Programming is recursion with a memory. The moment you notice the same sub-problem being solved twice, DP says: solve it once, store the answer, reuse it. Watch the table fill cell by cell below.
01
Memoization vs Tabulation
Memoization (top-down): write the recursive solution normally, cache results in a hash map/array.
Tabulation (bottom-up): build the answer iteratively from the smallest sub-problem upward, filling a table.
Fibonacci: naive recursion is O(2ⁿ); memoized/tabulated Fibonacci is O(n).
The Recurrence, Written Out
dp[n] = dp[n−1] + dp[n−2], dp[0]=0, dp[1]=1
Every DP solution is really just: (1) write this recurrence down, (2) decide top-down or bottom-up, (3) figure out which previous values each cell actually depends on. That's it — the hard part is almost always step 1.
02
Knapsack, LCS & LIS
0/1 Knapsack: pick items to maximise value under a weight limit, each item used at most once. O(n·W).
LCS (Longest Common Subsequence): the longest sequence appearing in order in both strings. O(m·n).
LIS (Longest Increasing Subsequence): the longest strictly increasing run you can pick from an array. O(n²) naive, O(n log n) optimised.
The Three Recurrences GATE Actually Asks You To Derive
LIS — dp[i] = max( dp[j] + 1 ) for every j < i where arr[j] < arr[i]
Read each one as a sentence, not symbols: Knapsack asks "is this item worth including, given what's left?" LCS asks "do these two characters match, and if not, which side do I drop?" LIS asks "what's the best chain I can extend, ending right here?" — once you can say the sentence, the formula is just notation for it.
03
Edit Distance, Coin Change, Matrix Chain & Subset Sum
Plain English
Four more problems that show up constantly in GATE and interviews — each is the same "write the recurrence, then fill a table" idea, just with a different question being asked at each cell.
Edit Distance (Levenshtein) — min ops to turn string a into string b
The three options are delete, insert, replace — pick whichever of the three neighbouring cells is cheapest and add 1 for the operation.
Coin Change — fewest coins to make amount n
dp[n] = 1 + min( dp[n − coin] ) for every coin ≤ n, dp[0] = 0
GATE trap: greedy (always take the biggest coin) works for normal currency denominations but provably fails for arbitrary coin sets — DP is the only approach guaranteed correct for any set of denominations.
Matrix Chain Multiplication — cheapest order to multiply a chain of matrices
dp[i][j] = min over k ( dp[i][k] + dp[k+1][j] + pi-1·pk·pj ), i ≤ k < j
pi-1·pk·pj is the cost of multiplying the two resulting sub-chains together — matrix multiplication is associative, so reordering never changes the answer, only how much work it takes to get there.
Subset Sum — does any subset add up to exactly target T?
This is 0/1 Knapsack's boolean cousin — same table shape, but each cell asks "is this reachable?" instead of "what's the best value?"
Practice Questions — Dynamic Programming
Beginner·Intermediate·Advanced
Most interview and GATE problems are one of a small number of recurring patterns wearing a different costume. Learn to recognise the costume.
01
String Matching — Naive, KMP & Rabin-Karp
Plain English
"Find pattern P inside text T" — the naive approach slides P across T one position at a time, re-checking from scratch every time, even when most of the comparison work was already done on the last attempt. KMP and Rabin-Karp both exist to avoid that wasted re-work.
Naive: try every starting position, compare character by character. O(n·m) worst case (n=text, m=pattern).
KMP: precomputes a "failure function" so that on a mismatch, it never re-compares characters it already knows will match — O(n+m), no backtracking in the text at all.
Rabin-Karp: hashes the pattern and every window of the text, comparing hashes first (O(1) each) and only falling back to character comparison on a hash collision — average O(n+m), enables searching for multiple patterns at once.
KMP's Failure Function — The Key Idea
lps[i] = length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]
On a mismatch at position i, instead of restarting from i+1, jump the pattern pointer to lps[i−1] — that's the longest chunk of already-matched text we know we can reuse, which is exactly why the text pointer never has to move backward.
Fast/slow pointers: cycle detection, finding the middle of a list in one pass.
Greedy: make the locally optimal choice at each step, hoping it leads to a global optimum (works for activity selection, Kruskal's MST).
Bit manipulation: XOR to find a unique element, bitmasking to represent subsets compactly.
Bit Manipulation — The Identities Worth Memorising
x XOR x = 0, x XOR 0 = x → XOR-ing a list cancels every paired value, leaving the lone unpaired one
x AND (x−1) clears the lowest set bit → counts/clears bits in O(popcount), not O(bit-width)
x AND (−x) isolates the lowest set bit → the trick behind Fenwick Tree indexing