Write it from memory

Two pointers (opposite ends)

use it when…

• The array is sorted (or you can sort it) and you need a pair with some sum
• A score that depends on both ends, like width × the shorter height
• Reverse or compare from both ends: palindromes, reversing in place

Two pointers (opposite ends)

Two pointers (read / write)

use it when…

• "Remove" or "keep" some elements in place and return the new length
• "Do not allocate extra space" (O(1) memory) on an array
• Keep the order of the kept elements, like a filter

Two pointers (read / write)

Sliding window (fixed size)

use it when…

• "Every subarray (or substring) of length k"
• Find an anagram or permutation of p inside s: the window size is p.length()
• Best sum, average or count over windows of one given size

Sliding window (fixed size)

Sliding window (variable size)

use it when…

• "Longest" or "shortest" contiguous subarray or substring
• A rule about what is inside the window: no repeats, at most k zeros, sum at least target
• The rule moves one way: growing the window only pushes it further (more repeats, a bigger sum), and shrinking only pulls it back

Sliding window (variable size)

Prefix sums + HashMap

use it when…

• Many "sum of nums[l..r]" queries on an array that does not change
• "Count (or find the longest) subarray with sum exactly k"
• The numbers can be negative, so a sliding window breaks
• "Equal number of 0s and 1s": turn 0 into −1 and look for sum 0

Prefix sum + HashMap · Prefix sums

Binary search (exact match)

use it when…

• The input is sorted and you need one exact value
• "Must run in O(log n)"
• A sorted structure you can index, like a matrix read row after row

Binary search (exact & bounds)

Binary search (lower & upper bound)

use it when…

• "First" or "last" position of a value that can repeat
• "Where would it be inserted?" or "how many elements are < x?"
• The latest entry at or before a timestamp (floor) in a sorted list

Binary search (exact & bounds)

Binary search on the answer

use it when…

• "Minimum speed / capacity / time such that …" or "maximum x such that …"
• Checking one guess is easy (a greedy pass), but finding the best one directly is hard
• If a value works, every bigger value also works (or every smaller one)

Binary search on the answer

Monotonic stack

use it when…

• "Next greater" or "next smaller" element, or "how many days until …"
• For each bar, how far it can stretch left and right (histogram, rectangles)
• A brute force that scans forward from every index: O(n²) that should be O(n)

Monotonic stack

Monotonic deque

use it when…

• The maximum or minimum of every window of size k
• A sliding window where you need the best element inside it, not just a sum
• Shortest subarray with sum at least k when numbers can be negative

Monotonic deque

Reverse a linked list

use it when…

• "Reverse" the list, or a part of it (positions left..right, every k nodes)
• You must change the order in place, with O(1) extra memory
• A step of a bigger problem: palindrome check, reorder list

In-place linked-list rewiring

Fast & slow pointers

use it when…

• Find the middle of a linked list in one pass
• "Does the list have a cycle?" or "where does the cycle start?"
• Something keeps stepping to a next value (a list, nums[i], a digit sum) and may loop

Fast & slow pointers

Merge sort (and counting while you merge)

use it when…

• "Sort an array" with a guaranteed O(n log n), even in the worst case
• Count pairs i < j with a rule like nums[i] > 2 * nums[j], or "smaller numbers after self"
• Merge two (or k) sorted runs: arrays or linked lists

Merge sort & merging sorted runs · Divide and conquer

Quickselect (k-th smallest or largest)

use it when…

• "Find the k-th largest (or smallest)" and you only need that one value, not a full sort
• "The k closest points" or "the top k", in any order, in average O(n)
• You need the median of an unsorted array

Quickselect

Tree traversals (pre, in, post — recursive and iterative)

use it when…

• "Return the preorder / inorder / postorder" of a binary tree
• A BST in sorted order: inorder visits the values smallest first
• The interviewer says "now without recursion", or the tree can be very deep (a skewed tree)

Iterative tree DFS (explicit stack)

Level-order traversal (tree BFS)

use it when…

• The answer is per level: each level's values, average, maximum, or last node
• "Right side view", "zigzag", "minimum depth" — the nearest or the row matters
• You need to handle one row of the tree completely before the next

Tree BFS (level order)

Tree DFS that carries info (bottom-up and top-down)

use it when…

• The answer for a node needs answers from its children: height, diameter, balanced, max path sum
• The answer for a node needs something from its path above: max so far, running sum, valid range
• "For every node…" or "the longest path anywhere in the tree"

Tree DFS (bottom-up) · Tree DFS (top-down)

BST search, insert, delete and validate

use it when…

• The tree is a binary search tree: left < node < right everywhere
• "Insert", "delete", "search", "floor" or "successor" in a BST
• "Is this a valid BST?" — checking only the parent is not enough

BST property

Top k with a size-k heap

use it when…

• "The k largest / smallest / most frequent / closest"
• "The k-th largest" in an array or a stream of numbers
• k is much smaller than n, or the data arrives one item at a time

Top-k with a size-k heap

Two heaps (running median)

use it when…

• Numbers arrive one by one and you must report the median after each one
• You need the middle of a changing collection, not the smallest or the largest
• Sorting again after every insert would be too slow

Two heaps (median)

Trie (prefix tree)

use it when…

• Many words, and the questions are about prefixes: autocomplete, "starts with", shortest root
• You search for lots of words in one go (a dictionary against a grid or a sentence)
• Words share beginnings, so walking letter by letter saves repeated work

Trie (prefix tree)

BFS shortest path (unweighted graph)

use it when…

• "Fewest steps", "minimum moves" or "shortest transformation" and every step costs the same
• States connect to each other: words one letter apart, board squares, lock combinations
• You need the distance to every node, or one actual shortest route

BFS shortest path (unweighted) · Graph DFS / BFS traversal

Grid BFS (flood fill & shortest steps)

use it when…

• A 2D grid of cells: land and water, open and blocked, like a game map
• "Count the islands / regions" or "size of the biggest region"
• "Fewest steps from here to there" when each move costs 1

Grid flood fill · BFS shortest path (unweighted)

Multi-source BFS

use it when…

• Many starting points spread at the same time: rotting oranges, fire, signals from many towers
• "Distance from every cell to the nearest X"
• Running one BFS per source would repeat the same work again and again

Multi-source BFS

Graph DFS (recursive & iterative)

use it when…

• "How many groups / provinces / connected pieces?"
• "Can I reach B from A?" or "visit everything once" (copy a graph, collect a group)
• The order of visiting does not matter, only that every reachable node is seen

Graph DFS / BFS traversal

Topological sort (Kahn & DFS)

use it when…

• "Prerequisites", "dependencies" or "X must happen before Y"
• "Is it possible to finish everything?" (that is: is there a cycle?)
• You need a valid order of tasks, like a build tool or Git history (a DAG)

Topological sort & cycle detection

Union-Find (DSU)

use it when…

• Edges or "same group" facts arrive one by one and you ask "are these two connected?"
• "Which edge creates a cycle?" or "how many groups are left?"
• Merging accounts, friend circles or network pieces, without walking the whole graph again

Union-Find (DSU)

Dijkstra (shortest path, weights ≥ 0)

use it when…

• "Cheapest", "fastest" or "minimum cost" path, and edges have different, non-negative weights
• Network routing, delivery times, map directions: one start, many destinations
• The cost of a path is built step by step (sum, max, or product of probabilities)

Dijkstra

Bellman–Ford

use it when…

• Shortest path where some edge weights are negative
• "At most k stops" or "at most k edges": the number of edges is limited
• You must detect a negative cycle (a loop that keeps making the path cheaper)

Bellman–Ford

Floyd–Warshall (all pairs)

use it when…

• You need the shortest distance between every pair of nodes
• The graph is small: n up to about 100–400 nodes
• Questions like "how many cities are within distance d of each city"

Floyd–Warshall

Prim's minimum spanning tree

use it when…

• "Connect all points / cities / computers at the minimum total cost"
• Every node must be joined, and any cycle would only waste money
• The graph is dense, or given as points where every pair is an edge

Minimum spanning tree (Kruskal / Prim)

Kruskal's minimum spanning tree

use it when…

• "Minimum total cost to connect everything" and the input is an edge list
• The graph is sparse: far fewer edges than V²
• You must ask "is this edge in some or every MST?" (build the MST with and without it)

Minimum spanning tree (Kruskal / Prim) · Union-Find (DSU)

Backtracking: subsets

use it when…

• "Return all subsets" (the power set)
• Every element is either in or out, and order inside a group does not matter
• Small n (about 20 or less): 2ⁿ answers is fine

Backtracking: subsets

Backtracking: permutations

use it when…

• "Return all orderings / arrangements"
• Every element is used exactly once and the order matters
• Placing items in slots with rules (N-Queens: one queen per row, each column once)

Backtracking: permutations

Backtracking: combinations with pruning

use it when…

• "Pick k items" or "find all combinations that add up to target"
• Order inside a group does not matter: [2, 3] and [3, 2] are the same answer
• Can an item be reused? That one question decides i or i + 1 in the call

Backtracking: combinations & partitions · Backtracking with constraint pruning

1D DP

use it when…

• "How many ways", "minimum cost" or "maximum total" along a line of items
• The answer at position i depends only on a few earlier positions (i - 1, i - 2)
• A plain recursion works but repeats the same calls again and again

1D DP

Grid DP

use it when…

• A grid where you may only move right or down (or one row to the next)
• "Count the paths", "cheapest path" or "largest square" in a matrix
• Each cell's answer comes from its top, left or top-left neighbour

Grid DP

Knapsack (0/1 and unbounded)

use it when…

• Pick items to reach an exact sum or capacity: "can we make", "fewest", "how many ways"
• Each item is used at most once (0/1) or any number of times (unbounded: coins)
• The target number is small enough to be an array index (up to about 10⁴)

0/1 knapsack · Unbounded knapsack

Longest increasing subsequence

use it when…

• "Longest increasing (or non-decreasing) subsequence": items may be skipped, order must stay
• Chains or nesting: envelopes, boxes, pairs where each must be bigger than the last
• n up to about 10⁵, so O(n²) is too slow and you need the O(n log n) version

Longest increasing subsequence · Binary search (exact & bounds)

Two-string DP (LCS, edit distance)

use it when…

• Two strings (or two arrays) and a question about matching them up
• "Longest common subsequence", "fewest edits", "how many ways does t appear in s"
• Each step looks at the last letter of both prefixes: match it, or drop one

2D DP on two strings (LCS / edit distance)

Interval DP

use it when…

• The answer for a range [i..j] comes from smaller ranges inside it
• "Burst", "merge" or "remove" items where the neighbours change after each step
• Two players taking from either end, or palindromes in a substring

Interval DP

Bit tricks

use it when…

• "Count the 1 bits", "is it a power of two", "reverse the bits"
• Every value appears twice except one: XOR cancels the pairs
• A small set (n ≤ 20) stored as one int, with bit i meaning "element i is in"

Bit tricks (shift, mask, lowest set bit) · XOR cancellation · Bitmask as a set

Fenwick tree (BIT)

use it when…

• Range sums while values keep changing (point updates mixed with queries)
• "How many earlier (or later) values are smaller": count with ranks
• A plain prefix-sum array would need O(n) work after every update

Fenwick tree (BIT)

Segment tree

use it when…

• Many range queries (sum, min, max) mixed with updates
• The query is not a plain sum, so a Fenwick tree does not fit (range min or max)
• n and the number of queries are both up to about 10⁵

Segment tree

KMP (prefix function)

use it when…

• Find a pattern inside a text in O(n + m), with no hashing and no bad worst case
• "Longest prefix that is also a suffix" (a happy prefix, a border)
• Is a string made of one repeated block? Shortest palindrome by adding letters in front?

KMP / prefix function

Fast input & output for online assessments

use it when…

• An online assessment where you read stdin yourself (HackerRank, HackerEarth, Codeforces style)
• Input of 10⁵ – 10⁶ numbers, where Scanner alone can take seconds
• Many output lines: calling System.out.println for each one is slow