Introduction

Hash Table

A key maps to a value in constant time, which removes the need for a full scan.

Prefix Sum

A running total is stored at each index, so the sum of any range is one subtraction.

Two Pointers

Two indices move through the data from different positions and meet at the answer.

Sliding Window

A range with a start and an end moves across the data, and the contents are updated at each step.

Binary Search

Half of a sorted range is removed at each step until the target is found.

Stack

Items are added and removed from one end, so the last item added is the first item removed.

Monotonic Stack

A stack keeps its items in sorted order, which finds the next larger or smaller item in one pass.

Linked List

Each node points to the next node, and the pointers give the path through the data.

Hybrid Structures

Two structures are combined, such as a hash map and a linked list, to get the best properties of each.

Matrix Index Math

A two-dimensional grid is read as a flat array through a formula, and the neighbors are found by arithmetic.

Tree DFS

Each branch is followed to its end before the next branch is examined.

Tree BFS

All nodes at one level are visited before the nodes at the next level.

Binary Search Tree

Each node holds a value that is larger than its left subtree and smaller than its right subtree.

Heap

The largest or smallest item is always at the top, and it is removed in logarithmic time.

Trie

Each node holds one character, and a path from the root spells a word.

Graph DFS

Each edge is followed to its end, and a visited set prevents a repeat visit.

Graph BFS

Nodes are visited in order of distance from the start, which gives the shortest path in an unweighted graph.

Topological Sort

Nodes are put in an order where each node comes after all nodes that point to it.

Union-Find

Two sets are merged and the set of any item is found in near-constant time.

Backtracking

Each choice makes a branch, and a branch is undone when it does not give a valid result.

1-D DP

The result for each state is stored in a list, and each new result is computed from the results before it.

Multi-D / Grid DP

The result for each state is stored in a table with two or more dimensions, and each cell is computed from its neighbors.

Greedy

The best local choice is made at each step and is not changed later.

Intervals

Ranges with a start and an end are sorted, and then merged, counted, or scheduled.