Algorithms

Overview Both techniques avoid redundant recomputation in dynamic programming problems by caching subproblem results, but they build that cache in opposite directions. Memoization starts from the original problem and recurses downward, caching results lazily as calls return, while tabulation starts from the base cases and iterates upward, filling a table until the final answer is reached. Comparison Diagram Memoization (Top-Down)fib(4)fib(3)fib(2)*fib(2)fib(1)* = cache hit, no recomputememo cachefib(0)=0 fib(1)=1fib(2)=1 fib(3)=2fib(4)=3recurse down, cache on returnTabulation (Bottom-Up)for i = 0 .. ndp[0]0dp[1]1dp[2]1dp[3]2dp[4]3final answerbuild up from base cases Comparison Table Aspect Memoization (Top-Down) Tabulation (Bottom-Up) Entry point Starts from the original problem call, e.g. solve(n) Starts from the smallest base cases, e.g. dp[0], dp[1] Control flow Recursive function calls, following the natural recurrence Iterative loop over subproblem indices in dependency order Subproblems computed Only those actually reachable from the initial call All subproblems up to the target, whether needed or not Storage structure Hash map or sparse cache keyed by call arguments Array or table indexed by subproblem parameters Order dependency Implicit, resolved automatically by call stack ordering Explicit, programmer must sort iteration to respect dependencies Call overhead Function call and stack frame cost per subproblem No function call overhead, just array reads and writes Stack risk Can hit recursion depth limits or stack overflow on deep inputs No recursion, so no stack depth concerns Code shape Mirrors the recursive definition, often easier to derive first Requires reformulating the recurrence as an explicit loop Key Differences Memoization computes subproblems on demand, while tabulation computes every subproblem exhaustively in order. Memoization relies on the call stack to sequence work; tabulation relies on a manually ordered loop. Tabulation typically enables space optimization (e.g. keeping only the last few rows) since access order is known upfront. Memoization can be stack-limited on deep recursion, whereas tabulation avoids recursion entirely. Memoization is usually a smaller code change from a naive recursive solution; tabulation requires restructuring it as iteration. When to Use Each Memoization (Top-Down) ...

Overview Both techniques repeat a computation until some condition is met, but they do it through fundamentally different mechanisms. Recursion repeats by having a function call itself on the call stack, while iteration repeats by looping over the same stack frame. The choice affects memory usage, readability, and how deep a computation can safely go. Comparison Diagram RecursionIterationcall stackf(n)f(n-1)f(n-2)...new frame per callO(n) stack memoryrisk: stack overflowloop body (single frame)while / fori++, same frame reusedO(1) stack memoryno growth per cycle Comparison Table Aspect Recursion Iteration Core mechanism Function calls itself with a smaller subproblem Explicit loop (for/while) repeats a block of code Termination condition A base case stops further calls A loop condition evaluates to false State storage Held implicitly in parameters and locals of each stack frame Held explicitly in variables updated each pass Memory usage O(n) call stack space, one new frame per call O(1) auxiliary space, the same frame is reused Failure mode Stack overflow on deep or unbounded recursion Infinite loop if the condition never turns false Performance overhead Function-call overhead per level unless tail-call optimized No call overhead, just a branch/jump back Best-fit problems Tree/graph traversal, divide-and-conquer, backtracking Linear, bounded repetition like counting or array scans Key Differences Recursion breaks a problem into self-similar subcalls; iteration repeats a block via an explicit loop. Recursion grows the call stack by one frame per call; iteration reuses a single frame. Deep recursion risks stack overflow, while iteration’s main failure mode is an infinite loop. Some languages apply tail-call optimization to turn tail recursion into iteration under the hood. Recursion maps naturally onto trees and graphs; iteration suits flat, bounded repetition. When to Use Each Recursion ...

Overview Both are algorithms for visiting every node in a tree or graph, but they differ in which node they explore next. BFS spreads outward level by level using a queue, while DFS plunges down one path as far as possible before backtracking, using a stack. Comparison Diagram BFSDFS12345671253467outinQueue (FIFO)push/popStack (LIFO) Comparison Table Aspect BFS DFS Underlying structure Queue (FIFO) Stack (FILO), often via recursion Traversal pattern Explores all neighbors at current depth before going deeper Follows one branch to its end before backtracking Order nodes are visited Level by level (breadth-first) Branch by branch (depth-first) Memory usage O(width) — can be large for wide/bushy graphs O(depth) — can be large for deep graphs Shortest path guarantee Yes, on unweighted graphs (first visit = shortest path) No, may find a longer path first Implementation style Iterative with explicit queue Recursive, or iterative with explicit stack Risk of infinite loop Low with visited-set on cyclic graphs Higher on cyclic graphs without visited-set, or infinite depth Typical use cases Shortest path, level-order processing, web crawling by hops Topological sort, cycle detection, maze/backtracking problems Key Differences BFS uses a queue and expands outward level by level, while DFS uses a stack (or recursion) and dives deep before backtracking. BFS guarantees the shortest path on unweighted graphs; DFS does not. BFS memory cost scales with graph width, while DFS memory cost scales with graph depth. DFS naturally supports backtracking algorithms like maze solving and topological sort. Both require a visited set to avoid infinite loops on cyclic graphs. When to Use Each BFS ...

Overview Two Pointers and Sliding Window are both O(n) techniques for scanning arrays or strings, but they solve different shapes of problems: Two Pointers tracks two independent indices that move toward, away from, or alongside each other, while Sliding Window maintains a contiguous subrange that expands and contracts as it scans. Picking the wrong one usually means either overcomplicating a pair-search problem or missing the running aggregate a window naturally provides. Comparison Diagram Two PointersSliding WindowLRindices converge inwardover sorted dataLRcontiguous range expands/contracts, tracking an aggregate Comparison Table Aspect Two Pointers Sliding Window Core mechanism Two independent indices scan or converge across the data Two indices (left/right) define a contiguous range that grows and shrinks Pointer movement Move toward each other, away, or in lockstep at a fixed offset Right pointer expands the range forward, left pointer contracts it Input requirement Usually needs sorted data or a paired structure Works on any unsorted array or string State tracked Just the two positions and the values being compared A running aggregate of window contents (sum, count, frequency map) Problem signature Pair-sum, palindrome check, merging two sorted arrays Longest/shortest substring or max/min sum under a constraint Relationship between pointers No notion of a range between them, only the two positions matter The range between the pointers IS the answer candidate Time and space complexity O(n) time, O(1) space O(n) time, O(1) to O(k) space for the aggregate Failure mode Breaks if data isn’t sorted or orderable for the comparison Breaks if the target condition isn’t monotonic, so the window can’t shrink safely Key Differences Two Pointers tracks two independent indices; Sliding Window tracks a contiguous range between them. Two Pointers typically requires sorted input; Sliding Window works fine on unsorted sequences. Sliding Window maintains a running aggregate as it moves; Two Pointers usually just compares individual values. Sliding Window breaks down when the target condition isn’t monotonic, since the window can’t be safely shrunk. When to Use Each Two Pointers ...