The pattern finder

Start one pointer at each end and move them towards each other, using a rule to decide which one moves.

Clues

• Sorted array or string
• Find a pair (or triple) with a target sum
• Palindrome checks
• "Container" or "area between two lines"

Time O(n) · Space O(1)

A fast pointer reads every element and a slow pointer marks where the next kept element should be written.

Clues

• Remove or move elements in place
• "Return the new length"
• Remove duplicates from a sorted array
• Move zeroes to the end

Time O(n) · Space O(1)

Keep a window of exactly k elements; add the element entering and remove the one leaving instead of recomputing.

Clues

• "Subarray or substring of size k"
• Maximum or average of every k-length window
• Anagram or permutation of a fixed-length pattern inside a string

Time O(n) · Space O(1) or O(alphabet)

Grow the window with the right pointer; when it breaks a rule, shrink it from the left until it's valid again.

Clues

• "Longest" or "shortest" substring or subarray with a condition
• "At most K distinct", "without repeating", "sum at least S"
• Contiguous range plus a constraint

Time O(n) · Space O(alphabet) or O(k)

Store running totals so the sum of any range is one subtraction: prefix[r + 1] - prefix[l].

Clues

• Many range-sum queries
• "Sum of subarray from i to j"
• Values don't change between queries
• Product or count over ranges

Time O(n) build, O(1) per query · Space O(n)

Apply many "add v to range [l, r]" updates in O(1) each by marking +v at l and -v at r + 1, then take a prefix sum once.

Clues

• Many range updates, then read the final array once
• Bookings, flights or seats over ranges of days
• "Add value to every element between i and j"

Time O(n + updates) · Space O(n)

Walk the input once and keep a few variables (best so far, minimum so far, a count) that summarise everything seen.

Clues

• "Maximum/minimum so far"
• Best profit from buying before selling
• Answer depends only on a summary of the past, not every past element
• O(n) time and O(1) space expected

Time O(n) · Space O(1)

Treat every index (and every gap between two indexes) as the middle of a palindrome and grow outwards while both sides match.

Clues

• Longest palindromic substring
• Count palindromic substrings
• Symmetry around a middle point
• n up to a few thousand (O(n²) is fine)

Time O(n²) · Space O(1)

Scan once, keeping the best sum of a subarray ending here: either extend the previous one or start fresh.

Clues

• Maximum (or minimum) subarray sum
• "Contiguous subarray" with the best total
• Best profit from one buy and one sell

Time O(n) · Space O(1)

Walk a 2D grid in a controlled order (rows, columns, spiral, diagonals) using boundaries or direction arrays.

Clues

• 2D array or grid input
• Spiral order
• Rotate an image
• Set rows/columns to zero

Time O(rows × cols) · Space O(1) extra

Count subarrays with a target sum by remembering how often each running total has appeared.

Clues

• "Number of subarrays with sum K"
• Negative numbers allowed (so sliding window fails)
• Subarray sum divisible by K
• Longest subarray with equal 0s and 1s

Time O(n) · Space O(n)

When values are in the range 1..n, put each value at its own index (or mark that index) to find missing or duplicate numbers in O(1) space.

Clues

• Numbers in the range 1..n or 0..n
• Find the missing, duplicate or first missing positive
• O(1) extra space and O(n) time

Time O(n) · Space O(1)

As you scan, store what you've seen; for each new element, ask in O(1) whether its partner was already seen.

Clues

• Find a pair with a sum or difference in an unsorted array
• "Have I seen this before?"
• Return indexes, so sorting isn't allowed
• Need O(n) time

Time O(n) · Space O(n)

Count how many times each value appears (with an int[26] or a HashMap), then answer from the counts.

Clues

• Anagrams
• "Most frequent", "first unique", "majority element"
• Compare the content of two strings ignoring order
• Group items by their letters

Time O(n) · Space O(alphabet) or O(n)

Move one pointer one step and another two steps; their meeting (or the fast one finishing) reveals cycles and middles.

Clues

• Linked list cycle
• Middle of a linked list
• "Happy number" or any repeated sequence
• Find the start of a cycle

Time O(n) · Space O(1)

Walk the list with prev, curr and next, turning each arrow around as you go.

Clues

• Reverse a list or part of it
• Reverse in groups of k
• Palindrome linked list
• Reorder list

Time O(n) · Space O(1)

Start with a fake node before the real head so building, merging and deleting never need special cases for the first node.

Clues

• Merge two sorted lists
• Delete nodes (the head might be deleted)
• Build a new list while scanning
• Partition a list

Time O(n + m) · Space O(1)

In sorted data, check the middle and throw away the half that can't contain the answer.

Clues

• Sorted array (even if rotated)
• "Find the first/last position"
• O(log n) required
• Search in a monotonic sequence

Time O(log n) · Space O(1)

When you can check "is answer x good enough?" and the check is monotonic, binary search over possible answers.

Clues

• "Minimum capacity/speed/time such that..."
• "Maximise the minimum" or "minimise the maximum"
• A yes/no feasibility check is easy to write
• Large answer range (up to 10^9)

Time O(log(range) × cost of check) · Space O(1)

Push openers and pop when the matching closer arrives; anything left over or mismatched is an error.

Clues

• Brackets or tags that must match
• Undo / backspace behaviour
• Evaluate expressions
• Nested structures

Time O(n) · Space O(n)

Keep a stack whose values only increase (or decrease); each element pops everything it beats, finding "next greater/smaller" in one pass.

Clues

• "Next greater" or "next smaller" element
• "How many days until a warmer temperature"
• Largest rectangle in a histogram
• Stock span

Time O(n) · Space O(n)

Keep a deque of candidates in decreasing order so the front is always the max of the current window.

Clues

• Maximum or minimum of every sliding window
• DP where you need the max of the last k states

Time O(n) · Space O(k)

Solve the problem by solving a smaller version of it, with a base case that stops the calls.

Clues

• The problem is defined in terms of itself (factorial, Fibonacci, trees)
• Nested structures
• Divide the input and combine results

Time Depends on the recursion tree · Space O(depth) for the call stack

Build a candidate one choice at a time; when a choice can't lead to an answer, undo it and try the next.

Clues

• "Generate all" subsets, permutations or combinations
• Constraint puzzles (N-Queens, Sudoku)
• Word search in a grid
• Small input size (n ≤ 20)

Time Exponential, e.g. O(2^n) or O(n!) · Space O(n) depth plus the output

Split the input into halves, solve each half recursively, and combine the results.

Clues

• Sorting
• Counting inversions
• The answer for a range can be built from its halves
• O(n log n) expected

Time O(n log n) typically · Space O(n) for merging, O(log n) stack

Recurse into the left and right children and combine what they return (height, sums, paths).

Clues

• Binary tree input
• Height, depth, diameter, path sums
• "Same tree", "symmetric", "invert"
• Answer depends on both subtrees

Time O(n) · Space O(h) where h is the tree height

Process the tree level by level with a queue, handling exactly one level per loop.

Clues

• "Level order", "by level", "zigzag"
• Right side view
• Minimum depth
• Anything per level (averages, max)

Time O(n) · Space O(width)

Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Clues

• Binary search tree input
• Kth smallest
• Validate a BST
• Search, insert or delete by value

Time O(h) for search, O(n) for full checks · Space O(h)

Store words character by character in a tree so every prefix is a path you can walk in O(length).

Clues

• Prefix search, autocomplete
• "Starts with"
• Many words checked against a grid or a stream
• Word dictionary with wildcards

Time O(word length) per operation · Space O(total characters)

Keep a heap of size k: a min-heap for the k largest, a max-heap for the k smallest.

Clues

• "K largest", "K smallest", "K most frequent", "K closest"
• Kth largest element
• Stream of data with a top-K query

Time O(n log k) · Space O(k)

Split values into a max-heap of the smaller half and a min-heap of the larger half to read the median instantly.

Clues

• Running median
• Median of a sliding window
• Balance two groups

Time O(log n) per add, O(1) per median · Space O(n)

Put the first element of each sorted list in a min-heap, repeatedly take the smallest, and push its successor.

Clues

• Merge k sorted lists or arrays
• Kth smallest in a sorted matrix
• Smallest range covering k lists

Time O(N log k) · Space O(k)

Explore from a start node in rings of increasing distance using a queue and a visited set.

Clues

• Shortest path with equal edge weights
• Minimum number of moves or steps
• Spread from several sources at once (rotting oranges)
• Word ladder

Time O(V + E) · Space O(V)

Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Clues

• Count islands or connected components
• Flood fill, surrounded regions
• Can you reach X from Y?
• Clone a graph

Time O(V + E) or O(rows × cols) · Space O(V) recursion depth

Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Clues

• Prerequisites or dependencies
• "Is it possible to finish all courses?"
• Build order, task scheduling
• Directed acyclic graph

Time O(V + E) · Space O(V + E)

Keep each group as a tree with a root; find the root to test membership and link roots to merge groups.

Clues

• "Are these connected?" asked many times
• Number of connected components as edges are added
• Detect a cycle in an undirected graph
• Group accounts or equations

Time Almost O(1) per operation (inverse Ackermann) · Space O(n)

Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Clues

• Shortest path with weighted edges
• Weights are non-negative
• Minimum cost or time to reach nodes
• Network delay

Time O((V + E) log V) · Space O(V + E)

Connect all nodes with the cheapest total edges: sort edges and add each one that doesn't form a cycle (Kruskal).

Clues

• Connect all points at minimum cost
• Weighted undirected graph
• No cycles in the result

Time O(E log E) · Space O(V)

Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Clues

• Count the ways
• Maximum or minimum over choices at each step
• "You can't take two adjacent"
• Recursion with repeated subproblems

Time O(n) · Space O(n), often O(1) with two variables

Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Clues

• Paths on a grid moving right/down
• Minimum path sum
• Obstacles on a grid
• Largest square of 1s

Time O(rows × cols) · Space O(rows × cols), or O(cols) with one row

For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Clues

• Choose a subset under a budget or capacity
• "Can these numbers sum to target?"
• Coin change (fewest coins or number of ways)
• Partition into equal sums

Time O(n × capacity) · Space O(capacity)

dp[i] is the longest increasing run ending at i; a patience-sorting version with binary search gets O(n log n).

Clues

• Longest increasing (or non-decreasing) subsequence
• Chains of pairs
• Russian doll envelopes
• Elements may be skipped but order kept

Time O(n log n) · Space O(n)

dp[i][j] answers the question for the first i characters of one string and the first j of the other.

Clues

• Two strings or sequences compared
• Longest common subsequence
• Edit distance (insert, delete, replace)
• Interleaving, distinct subsequences

Time O(m × n) · Space O(m × n), or O(n) with two rows

dp[i][j] is the answer for the range i..j, built from smaller ranges by trying every split point.

Clues

• Answer for a range depends on how you split it
• Burst balloons, matrix chain multiplication
• Palindromic substrings and partitions
• Merge stones

Time O(n³) typically · Space O(n²)

Represent which items are used as the bits of an integer, so dp[mask] covers every subset (n up to about 20).

Clues

• Small n (≤ 20) with "visit all" or "assign each"
• Travelling salesman
• Partition into k equal subsets
• Assignment problems

Time O(2^n × n²) · Space O(2^n × n)

Sort intervals by start; each one either overlaps the last merged interval (extend it) or starts a new one.

Clues

• Intervals, ranges, meetings, bookings
• Merge overlapping
• Insert an interval
• Minimum rooms or arrows

Time O(n log n) · Space O(n)

Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Clues

• "Minimum number of" with an obvious best next move
• Scheduling by earliest end time
• Jump game, gas station
• Sorting reveals the order to decide in

Time O(n log n) with sorting, O(n) without · Space O(1)

Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Clues

• "Every element appears twice except one"
• Count set bits
• Power of two
• Subsets as bit masks

Time O(n) or O(1) · Space O(1)

Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Clues

• "Design a class" with several operations
• Each operation has a required complexity, often O(1)
• LRU, LFU, time-based key-value store
• Min stack, randomised set

Time O(1) per operation for LRU · Space O(capacity)