Patterns

Use hash maps and hash sets to trade space for time. Convert O(n²) lookups into O(n) by storing values you have seen. The foundation of almost every interview.

Maintain a window over a contiguous subarray or substring, expanding or shrinking it to satisfy a constraint. Avoids recomputing from scratch on every step.

Use two indices that move toward each other or in the same direction to solve problems on sorted arrays or when looking for pairs/triplets that satisfy a condition.

Floyd's cycle detection: one pointer moves twice as fast. They'll meet if there's a cycle, or fast will hit null if there isn't.

Sort intervals by start time, then greedily merge overlapping ones. The key insight: if sorted, you only ever need to compare with the last merged interval.

When numbers are in range [1, N], each number belongs at index (number - 1). Swap each number to its correct position in O(n).

Reverse a linked list or sublist by re-wiring next pointers in-place using prev, current, next variables. No extra space needed.

Process a tree level by level using a queue. At each level, snapshot the queue size so you know exactly how many nodes belong to that level.

Explore tree paths using recursion (or explicit stack). Three traversal orders: pre-, in-, post-order. Great for path sums and BST validation.

Maintain a max-heap for the lower half and a min-heap for the upper half of a stream. The median is always at their tops.

Build all subsets by starting with an empty set and for each element, creating new subsets by adding it to every existing subset (BFS-style expansion).

Classic binary search adapted: search in rotated arrays, answer-space binary search, or find a boundary condition instead of an exact match.

Maintain a stack that is always increasing or decreasing. When you push a new element, pop all elements that violate the order — those are the elements for which the current one is the answer.

Explore all possibilities via recursion, but prune branches that cannot lead to valid solutions. Build the solution incrementally and undo choices when they lead to dead ends.

A tree where each node represents a character. Enables O(m) prefix searches (m = word length) instead of O(n·m) linear scan through all words.

Order nodes in a DAG such that every directed edge goes from earlier to later. Use BFS (Kahn's algorithm) with in-degree tracking or DFS with a finish-time stack.

Traverse graphs using BFS (shortest path, level-by-level) or DFS (connected components, path existence). Always track visited nodes to avoid cycles.

Break a problem into overlapping subproblems. Memoize results (top-down) or fill a table bottom-up. Works when the problem has optimal substructure.

XOR is its own inverse: a ^ a = 0 and a ^ 0 = a. XOR-ing all elements cancels duplicates, leaving only the unique ones.

A heap gives you O(log n) insert and O(1) peek at the min or max. Essential for "Top K", streaming medians, scheduling, and merging sorted streams.

LIFO (Last In First Out) data structure. Perfect for parsing strings, evaluating expressions, or matching pairs like parentheses.

Solve two-player zero-sum games where both players play optimally. Generally solved by exploring all future game states using DP or recognizing a mathematical pattern.