Prefix Sum
ANALOGY: Like keeping a running total in a checkbook balance so you can quickly check how much you spent between two dates.
REAL WORLD USE: Used in financial apps to answer multiple range sum queries efficiently without recalculating every single time.
WHEN TO USE: When you need to compute sums over subarrays multiple times or answer range sum queries efficiently.
/*
Input:
nums = [2, 1, 5, 1, 3, 2]
k = 3
Output:
9
*/
let nums = [2, 1, 5, 1, 3, 2];
let k = 3;
let windowSum = 0;
let maxSum = 0;
for (let i = 0; i < nums.length; i++) {
windowSum += nums[i];
if (i >= k) {
windowSum -= nums[i - k];
}
maxSum = Math.max(maxSum, windowSum);
}
Two Pointers
ANALOGY: Two people starting on opposite ends of a rope and walking towards each other to find a meeting point.
REAL WORLD USE: Used in e-commerce sites to find two prices that sum to a budget quickly when prices are sorted.
WHEN TO USE: When working with sorted arrays or linked lists and you need to find pairs or compare elements in a single pass.
let left = 0;
let right = nums.length - 1;
while (left < right) {
const current = nums[left] + nums[right];
if (current === target) return true;
if (current < target) left++;
else right--;
}Sliding Window
ANALOGY: A camera sliding over a billboard capturing only a section at a time. REAL WORLD USE: Used in streaming analytics to track rolling averages or counts over the last N seconds. WHEN TO USE: When solving problems involving contiguous subarrays or substrings that satisfy a condition (max, min, count, etc.).
Fast & Slow Pointers
ANALOGY: A hare and tortoise racing where the faster one eventually catches the slower one in a loop. REAL WORLD USE: Used in systems to detect loops or cycles such as in networks or process scheduling. WHEN TO USE: When you need to detect cycles or find middle points, especially in linked lists or repeating sequences.
LinkedList In-place Reversal
ANALOGY: Physically turning a train around by rearranging the order of cars without replacing the track. REAL WORLD USE: Used in undo/redo systems where the previous states need to be reversed efficiently. WHEN TO USE: When you need to reverse part of or an entire linked list without extra space.
Monotonic Stack
ANALOGY: A stack of plates where each plate is always smaller than the one below it, so you instantly know if a new plate is larger or smaller. REAL WORLD USE: Used in stock price monitoring to find the next greater (or smaller) price point. WHEN TO USE: When you need to find next greater/smaller element efficiently in arrays or sequences.
Top ‘K’ Elements
ANALOGY: Awarding medals to only the top finishers in a race. REAL WORLD USE: Used in recommendation systems to show top-k trending items or most frequent searches. WHEN TO USE: When you need to find the largest or smallest k elements quickly from a large set.
Overlapping Intervals
ANALOGY: Combining overlapping time slots in a schedule so no two appointments conflict. REAL WORLD USE: Used in calendar apps to merge or check conflicting events. WHEN TO USE: When you are dealing with ranges that may overlap and need merging or conflict detection.
Modified Binary Search
ANALOGY: Searching for a word in a rotated dictionary where the first half might not start with A. REAL WORLD USE: Used in search systems where data might be rotated or partially sorted, e.g., rotated logs. WHEN TO USE: When dealing with sorted arrays that might be rotated or when you need binary search with added checks for special conditions.
Binary Tree Traversal
ANALOGY: Visiting every room in a house systematically in a specific order. REAL WORLD USE: Used in file system navigation to list folders/files in different orders. WHEN TO USE: When you need to visit all elements of a binary tree in a defined sequence (preorder, inorder, postorder).
Depth-First Search (DFS)
ANALOGY: Exploring a maze by taking one path as far as possible before backtracking. REAL WORLD USE: Used in puzzle solvers and game tree analysis where all possibilities need exploration. WHEN TO USE: When problems require exploring all paths deeply, such as path finding or structure exploration.
Breadth-First Search (BFS)
ANALOGY: Exploring all shops on a street before moving to the next street. REAL WORLD USE: Used in routing systems to find shortest paths in unweighted networks. WHEN TO USE: When you need level-by-level exploration or shortest path in trees/graphs.
Matrix Traversal
ANALOGY: Walking through a grid of city blocks, checking each block horizontally/vertically. REAL WORLD USE: Used in grid-based games to explore all reachable cells. WHEN TO USE: When solving problems on 2D grids where you must examine neighbors in multiple directions.
Backtracking
ANALOGY: Trying all combinations of puzzle pieces, and undoing wrong ones to try another. REAL WORLD USE: Used in scheduling combinations or permutation generators where constraints apply. WHEN TO USE: When you need to explore all candidate solutions and revert choices that don’t lead to a valid solution.
Dynamic Programming
ANALOGY: Solving a big project by breaking it into smaller milestones and remembering the results so you don’t redo work. REAL WORLD USE: Used in resource optimization problems like route planning or budgeting where repeated subproblems exist. WHEN TO USE: When problems have overlapping subproblems and optimal substructure (max/min/longest, etc.).
