Which pattern is this?

• The statement spells out a process: rounds, turns, a line of people
• Small limits and no obvious shortcut
• Digit-by-digit arithmetic with a carry

Do exactly what the statement describes, step by step (often with a queue or a few counters), and keep the bookkeeping clean.

• The numbers form a known range like 0…n
• "How many paths/ways" on a plain grid
• The answer depends only on counts, not on the order of events

Replace a loop or a search with a formula: Gauss's sum, a combination count, or a counting argument.

• The definition is self-similar (row n is built from row n − 1)
• A list or string that shrinks by one element or pair
• "This piece + the answer for the rest"

Trust the call: solve the same problem for a smaller input, then do one step of work to finish yours.

• Halving the input halves the work (xⁿ, sorted ranges)
• The answer combines a left part and a right part
• Build a balanced structure from a sorted array

Split the input into halves, solve each half recursively, then combine — about log n levels of work.

• "Greatest common divisor", or fractions and ratios to simplify
• Count or list the primes up to n
• Two cycles must line up again (lcm)

Euclid's algorithm finds gcd(a, b) in O(log min(a, b)); the sieve of Eratosthenes lists every prime up to n in O(n log log n).

• "Reverse the digits" or "is the number a palindrome" without a String
• Sum, square or count the digits of a number
• The result must fit in a 32-bit int, or else return 0

x % 10 reads the last digit and x / 10 drops it; rebuild with rev * 10 + d, and check for overflow before the multiply, not after.

• "Maximum (or minimum) subarray sum or product"
• Best buy-then-sell, or any best pair with i < j
• A negative running total can only hurt what follows

Carry the best answer that ends at the current index (or the best value so far) and decide at each step: extend or restart.

• "Product of everything except i" without division
• Each position depends on the max to its left and to its right
• A rule must hold towards both neighbours (candy ratings)

The answer at i combines something about everything left of i with something about everything right of i; build each side in one pass.

• "Spiral order" or "layer by layer"
• "Rotate the matrix in place"
• Index tricks like r × cols + c or r + c for diagonals

Walk a grid by index arithmetic — shrinking boundaries, layers, transpose then reverse — without extra memory.

• "Longest common prefix"
• Words sorted in a custom alphabet
• Deduce letter order from adjacent sorted words

Strings are ordered by their first differing character: scan column by column and stop there.

• The input is a path, an expression or an encoded string
• Numbers with several digits sit inside the text
• Repeated separators or empty tokens

Walk the string with an index, pulling out tokens and multi-digit numbers, and handle separators and empty pieces on purpose.

• "O(1) extra space" on an array or a matrix
• Values are in 1…n, so indices can hold flags
• Every cell's next state depends on the current board

Reuse the input as scratch space — flip a sign, use the first row and column, or encode two states in one cell — for O(1) extra memory.

• "Next lexicographically greater arrangement"
• "Next greater number with the same digits"
• Step through permutations one at a time without recursion

From the right, find the first dip; swap it with the smallest bigger value after it, then reverse the falling suffix — the next arrangement in dictionary order, in place.

• "Appears more than n / 2 times" (or n / 3 with two candidates)
• Find the majority in O(1) extra space
• Pairs of different values can cancel each other out

Keep one candidate and a counter: a match adds a vote, a different value cancels one. A value filling more than half the array always survives.

• Sorted array + "pair or triplet with sum X"
• Palindrome check or reverse in place
• Maximise the area between two lines

Start at both ends and move one pointer inward per step based on a comparison: pairs, palindromes and in-place reversals in O(n).

• "Remove or move elements in place" and return the new length
• Keep the relative order while filtering
• Compact duplicates in a sorted array

A fast read pointer scans every element; a slow write pointer marks where the next kept element goes.

• Only three distinct values (0, 1, 2)
• Partition around a pivot when many values are equal
• Sort in one pass with O(1) space

Keep the zones < pivot | = pivot | unknown | > pivot with three indices and shrink the unknown zone one element at a time.

• "Every subarray or substring of length k"
• "Contains a permutation or anagram of p"
• Indices must be at most k apart

Slide a window of exactly k: add the element entering, remove the one leaving, and update the answer in O(1).

• "Longest or shortest contiguous subarray/substring such that…"
• "At most k" distinct values, zeros or replacements
• All numbers are positive, so sums grow with the window

Grow the right edge; while the window breaks the rule, shrink the left edge. Each index enters and leaves once, so it's O(n).

• "Longest palindromic substring"
• "Count the palindromic substrings"
• n up to a few thousand, so O(n²) is fine

Every palindrome mirrors around a centre: try all 2n − 1 centres and expand outward while the ends match.

• Two sorted arrays or lists to merge or intersect
• "Is s a subsequence of t?"
• Merge in place: fill from the back so nothing is overwritten

Give each input its own pointer and advance the one that is behind or smaller: merge, compare or match two sequences in O(n + m).

• "Pair that sums to target" in an unsorted array
• "Contains a duplicate" or "first repeat"
• Map old → new objects while copying a structure

Store what you've seen in a HashSet or HashMap so "have I seen x — or target − x — and where?" costs O(1) on average.

• "Anagram", "permutation of", "same letters"
• "Most or least frequent"
• Order doesn't matter, only how many of each

Count occurrences with an int[26] or map.merge(x, 1, Integer::sum), then reason about the counts instead of the order.

• "Group the items that are equivalent"
• Anagrams, rotations or shifted strings
• Two items match when some normalised form matches

Give equivalent items the same key (sorted letters, letter counts, a normalised shape) and bucket them in a HashMap.

• Many "sum of range [l, r]" queries on an array that never changes
• Running totals
• Sums of rectangles in a matrix

prefix[i+1] = prefix[i] + a[i]; then any range sum is one subtraction — in 1D, or in 2D with inclusion–exclusion.

• "Count subarrays with sum k" when negatives are allowed
• "Longest subarray with equal 0s and 1s"
• "Subarray sum divisible by k"

A subarray (j, i] sums to k exactly when prefix[i] − prefix[j] = k, so count (or index) earlier prefixes in a HashMap.

• "Reverse" all or part of a list
• "Merge, reorder or swap nodes" without making new ones
• The head itself might change

Reverse, splice and reconnect nodes by changing next pointers in place; a dummy head removes the special case for the first node.

• "Detect a cycle" or "where does the cycle start"
• "Middle of the list" in one pass
• "N-th node from the end" in one pass

Move two pointers at different speeds (or with a fixed gap): they meet inside a cycle, and the slow one stops at the middle.

• Brackets must match or nest
• "Evaluate" an expression or decode k[…]
• ".." means go back one level

Push context when you open a level; pop and combine when you close it — brackets, nested encodings, postfix expressions, paths.

• "Next greater element" or "days until a warmer day"
• Largest rectangle in a histogram
• For each item, the nearest item to one side that beats it

Keep the stack in increasing or decreasing order; whatever pops an element is its next greater (or smaller), and each index is pushed and popped once.

• "Max or min of every window of size k"
• Shortest subarray with sum ≥ k when negatives exist
• A DP step that needs the best of the last k states

A deque of indices in sorted value order: drop expired indices at the front and dominated ones at the back; the front is the window's best.

• "Implement a queue/stack using…"
• "Design a circular queue" with a fixed capacity
• "Retrieve the minimum in O(1)"

Build containers from simpler parts: a queue from two stacks (amortized O(1)), a ring buffer with head + size, a stack that carries its running minimum.

• Sorted input and "find x" or "where would x go"
• "First and last position" of a value
• A sorted 2D matrix you can treat as one array

Halve a sorted range each step to find a value, or its first/last position (lower and upper bound), in O(log n).

• "Rotated sorted array"
• "Find a peak" in O(log n)
• Median or k-th element of two sorted arrays

The data isn't plainly sorted (rotated, has peaks, or is split across two arrays), but a local check still tells you which half holds the answer.

• "Minimum speed, capacity or time such that…"
• Minimise the maximum (or maximise the minimum)
• An integer answer with a huge range, like up to 10⁹

If "can we do it with x?" flips from no to yes as x grows, binary search x over its range and test each guess (often greedily).

• "Merge two sorted lists or arrays"
• Sort a linked list in O(n log n)
• "Count pairs i < j where nums[i] > k·nums[j]"

Merge two sorted sequences by always taking the smaller head; merge sort applies that recursively, and counting during the merge solves inversion problems.

• "K-th largest or smallest" with all the data available
• "K closest" when the order inside the answer doesn't matter
• Find the median without sorting

Partition around a random pivot and keep only the side that contains index k: O(n) on average to find the k-th element.

• Values lie in a small range (0…2, letters, 0…n)
• "Top k by frequency" — a count is at most n
• Group values into buckets of width t

When keys are small integers or bounded counts, index an array by value (or by frequency) instead of comparing: O(n + range).

• "Arrange the numbers to form the largest number"
• Sort by frequency, ties broken by value
• The right order isn't the natural one

Define the order you need (by frequency then value, by concatenation) and let the sort do the rest — with Integer.compare, not subtraction.

• Height, depth, diameter or balance
• A path that may bend through any node
• Lowest common ancestor, or comparing two trees

Postorder: each child reports a value up (height, gain, found?), the parent combines them, and a global variable can track the best path.

• Each node must respect bounds set by its ancestors
• Root-to-leaf path conditions
• Visit by depth with DFS (right child first)

Preorder: pass state down to the children (an allowed range, the depth, the path so far) and decide at each node.

• "Level by level", "each depth", "right side view"
• Minimum depth or the nearest leaf
• Serialize row by row

A queue plus a size snapshot processes the tree one level at a time.

• "Construct the tree from preorder and inorder"
• "Convert a sorted array to a balanced BST"
• "Serialize and deserialize" a tree

Pick the root (first preorder value, middle of a sorted range), split the rest into left and right parts, and recurse.

• Search, insert or delete in a BST
• "K-th smallest" or "validate" a BST
• Iterate a BST in sorted order

Left < node < right: walk one branch per step (O(h)), and an inorder traversal visits the values in sorted order.

• "Closest value ≤ or ≥ x" while inserting
• Bookings or intervals that must not overlap
• Repeatedly take the smallest remaining key

TreeMap and TreeSet keep keys sorted, so floor, ceiling, first and last are O(log n) — perfect for "nearest value" questions.

• "Can you do it without recursion?"
• The tree may be 10⁵ levels deep (a skewed chain)
• Pause and resume a traversal (an iterator, next smallest)

Do the call stack's job yourself with an ArrayDeque: dive left pushing nodes, pop one, visit it, go right — same order as recursion, but no StackOverflowError.

• "K largest, smallest, closest or most frequent"
• "K-th largest in a stream"
• k is much smaller than n

Keep a heap of size k (a min-heap for the k largest): its root is the k-th best, and each update costs O(log k).

• "Median of a data stream"
• A running median as numbers arrive
• Balance a lower half against an upper half

A max-heap holds the lower half and a min-heap the upper half; keep their sizes balanced and the median sits on top.

• "Merge k sorted lists or arrays"
• The newest n items across many sorted feeds
• Smallest range covering k lists

Put the head of each sorted list in a min-heap; pop the smallest and push its successor: O(N log k).

• "Repeatedly take the two largest"
• Schedule tasks with a cooldown, or spread equal letters apart
• How many rooms or servers are busy at once

Keep the candidates in a heap and always act on the current best (largest count, heaviest stone, earliest end time).

• "Starts with", autocomplete or other prefix queries
• Search many words at once (a word-search grid)
• Wildcard '.' matching, or the maximum XOR of a pair

Store words character by character in a tree so prefix questions cost O(word length), not O(number of words); a binary trie does the same with bits.

• "Connected", "groups", "provinces", "reachable"
• Clone or copy a graph
• An adjacency matrix or list is given

Visit everything reachable with DFS or BFS and a visited set; restart from each unvisited node to count connected components.

• "Number of islands" or regions in a grid
• "Fill the area connected to (r, c)"
• Mark cells as visited by changing them in place

Treat cells as nodes and their 4 neighbours as edges; one DFS or BFS from a cell marks its whole region.

• Regions "not connected to the border"
• "Can water flow to both oceans?"
• Many sources share the same target

Instead of asking "can this cell reach the edge?" for every cell, start from the edge once and mark everything it reaches.

• "Minimum number of steps, moves or transformations"
• Every move costs the same
• The states are implicit (words, board positions)

BFS visits nodes in order of distance, so the first time it reaches the target is the fewest steps.

• "Minutes until every cell is affected" from several starts
• Distance from each cell to the nearest X
• Peel layers from all leaves or all edges at once

Seed the queue with every source at distance 0 and expand them together, layer by layer.

• "Split into two groups with no edge inside a group"
• "Is the graph bipartite?"
• Odd cycles must be detected

Colour each node opposite to its neighbour with BFS or DFS; a clash means an odd cycle, so the graph isn't bipartite.

• Prerequisites, dependencies or a build order
• "Is it possible to finish everything?" (is there a cycle?)
• Derive an order from pairwise rules

Order a DAG so every edge points forward: Kahn's algorithm peels nodes with in-degree 0 (or use DFS colours); if some never peel, there's a cycle.

• "Longest path" or "earliest finish time" with dependencies
• "Number of ways" along shortest paths
• Strictly increasing moves on a grid, so no cycle is possible

Process nodes in topological order (or DFS + memo) so each node's best value is final before anything reads it.

• "Shortest or cheapest path" with non-negative weights
• Minimise the maximum step on a path (minimax)
• Maximise a product of probabilities ≤ 1

With non-negative weights, a min-heap always settles the closest unsettled node next: O((V + E) log V).

• "At most k stops" or edges
• Negative edge weights
• Detect a negative cycle

Relax every edge V − 1 times (or k + 1 times for a limit on edges), reading from a copy of the previous round.

• Distances between every pair of nodes
• V up to a few hundred
• "Within a threshold distance" for every node

All-pairs shortest paths in O(V³): for each middle node k, try i → k → j for every pair.

• Moves are free or cost exactly 1
• "Minimum number of changes or removals" on a grid
• Dijkstra works, but O(V + E) is possible

When edges cost 0 or 1, a deque replaces the heap: push 0-cost moves to the front and 1-cost moves to the back.

• "Critical connections" in a network
• Single points of failure
• Removing one edge or node splits the graph

One DFS with discovery times and low-links finds every edge or node whose removal disconnects the graph.

• "Use every ticket, domino or pair exactly once"
• Rebuild one sequence from overlapping pieces
• In-degree and out-degree differ by at most 1

To use every edge exactly once, check the degrees, then walk until stuck and add each vertex when it runs out of edges; reverse that list.

• Connections arrive one at a time (online)
• "Same group?", "how many groups?", "which edge is redundant?"
• Equivalence rules like a == b

A parent array with path compression and union by size merges groups and answers "same group?" in near O(1).

• "Connect all points or cities at minimum cost"
• Edges that every (or some) MST must use
• A dense graph given as coordinates

Connect every node at the least total weight: sort edges and union them (Kruskal), or grow from one node with a heap (Prim).

• "All subsets" or "the power set"
• n ≤ 20, so 2ⁿ is allowed
• Duplicates in the input, but each answer must be unique

Every element is in or out: record the path at every node of the recursion tree. With duplicates, sort and skip equal siblings.

• "All orderings" or "arrangements"
• n ≤ 8–10, so n! is allowed
• Each element is used exactly once

Fill the positions one at a time from the unused elements (a used[] array or swapping), undoing each choice.

• "All combinations that sum to target"
• "All ways to cut a string into valid pieces"
• One choice per position (phone keypad letters)

Choose the next item (or the next cut point) from index start onward so each set is built once; prune as soon as the target is passed.

• Place items so none conflict (queens, sudoku)
• Generate only valid strings (balanced parentheses)
• Constraints you can check after each step

Place one piece at a time and only recurse while the partial state can still become valid; O(1) checks keep the tree small.

• "Does the word exist in the grid?" with no cell reused
• Find many words on one board
• A path must not revisit cells

DFS along a path from each cell: mark the cell on the way in and unmark it on the way out.

• One pass where a failure lets you restart past it (gas station)
• Always use the smallest available item first
• A rule must hold from both sides (two greedy passes)

Commit to the locally best move and never undo it — after convincing yourself (an exchange argument) that it can't hurt.

• "Can you reach the end?" or "minimum number of jumps"
• Cut a string so each letter lives in exactly one part
• Extend a segment while something inside it reaches further

Track the furthest index you can reach (or the current segment's end) and act when you arrive at it.

• "Merge overlapping intervals"
• Insert an interval into a sorted list
• The union of covered ranges

Sort by start; each interval either stretches the last merged one or starts a new one.

• "Fewest intervals to remove so none overlap"
• "Fewest arrows or points that hit every interval"
• Most meetings that fit without overlap

Sort by end and keep the interval that finishes first: it leaves the most room for the rest.

• "Maximum overlap" or rooms needed at the same time
• Capacity checks along a route
• Many range increments, then one read

Turn intervals into +1 / −1 events (or a difference array), process them in order, and track the running total.

• "Number of ways to reach step n"
• "Maximum sum with no two adjacent"
• Can the prefix be split or decoded validly?

dp[i] depends on a few earlier states (take or skip, a last step of 1 or 2, a word ending here); roll it down to O(1) variables.

• "Partition into two subsets with equal sums"
• Pick a subset that hits a target sum
• Each item: take it or leave it, once

Each item is used at most once: dp[s] = can we make sum s; loop the sums downward so an item is never reused.

• "Fewest coins" or "number of ways to make the amount"
• An unlimited supply of each item
• The order of choices doesn't matter

Items can repeat: loop the sums upward. Coins in the outer loop count combinations; amounts in the outer loop count orderings.

• "Longest strictly increasing subsequence"
• Chains or nesting (envelopes, pairs)
• Keep as many items as possible in sorted order

dp[i] = the longest run ending at i (O(n²)), or patience sorting: keep the smallest tail for each length and binary search it (O(n log n)).

• "Longest common subsequence"
• "Minimum edits to turn a into b"
• Two sequences compared character by character

dp[i][j] answers the question for the prefixes a[0..i) and b[0..j); each cell reads its left, top and diagonal neighbours.

• "Number of unique paths" in a grid
• "Minimum path sum" moving right or down
• Obstacles block some cells

Moving only right or down, each cell's answer comes from the cell above and the cell to the left; one row of memory is enough.

• Palindromic substrings or palindrome partitions
• "Burst, merge or remove — and the neighbours change"
• The answer for [l, r] splits at some k inside

dp[l][r] is built from smaller intervals inside it: fill by increasing length, or think about the last action inside the range.

• Buy and sell a stock with a cooldown or a fee
• "At most k transactions"
• At each step you're in one of a few modes

Track a few named states per step (holding, sold, cooling down) and write the transitions between them.

• "Every element appears twice except one"
• One number is missing from 0…n
• A duplicate or missing value with O(1) extra space

x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels the pairs and leaves the odd one out.

• Count or reverse the bits of a number
• "Power of two" or "add without +"
• "Every element appears three times except one"

Work one bit at a time with shifts and masks; n & (n − 1) clears the lowest set bit and n & −n isolates it.

• n ≤ 20 and you need every subset
• A small fixed alphabet (digits 1–9) to mark as seen
• Store a set of flags in one number

An int's bits form a set of up to 32 flags: enumerate subsets as 0…2ⁿ − 1, or mark seen digits in O(1).

• Range sums with point updates
• "Count smaller elements after self" (with coordinate compression)
• Running rank or count queries as values arrive

Prefix sums that survive updates: both update(i, delta) and prefixSum(i) take O(log n) using i & −i jumps.

• Range min, max or sum with updates
• Range updates (lazy propagation)
• The operation can't be undone by subtraction (min, max)

A tree over array ranges answers any associative range query (sum, min, max) and handles updates in O(log n).

• "Find the pattern in the text" in linear time
• The longest prefix that is also a suffix
• Is the string one block repeated?

pi[i] is the longest proper prefix of s[0..i] that is also a suffix; the match never moves backwards, so search is O(n + m).

• Compare many same-length substrings quickly
• "Longest duplicate (repeated) substring"
• Pairs well with binary search on the length

Hash every length-L substring in O(1) each by sliding: remove the leading character, add the trailing one, modulo a large prime.

• "LRU cache" with O(1) get and put
• Evict the least recently used item
• You need fast lookup and fast reordering together

The map finds a node in O(1); the list keeps recency order, so moving or evicting a node is O(1) too.

• "Insert, delete and getRandom in O(1)"
• Pick uniformly at random from a changing set
• Remove from the middle of an array in O(1)

An array holds the values and a map holds each value's index; delete by swapping with the last element.

• "Implement the X class" with a constructor and a few methods
• Each call changes a small counter, flag or list and returns a status
• Invalid calls must return false or -1 instead of throwing

Keep only the state the operations need, in private fields set by the constructor; each method checks its input, updates that state and returns the result.

• "Design a HashSet / HashMap" without the built-in hash libraries
• Keys come from a huge range but only a few are ever stored
• You must explain how hashCode and equals work together

An array of buckets: hash the key to an index with floorMod, keep a short linked chain per bucket, and compare keys only inside that one chain.