The DSA learning path

Concepts in prerequisite order - each stage says why it comes where it does. Watch the verified trace first, answer its predictions, then solve.

1. Arrays and binary search

The window-shrinking argument behind binary search is the first proof-carrying loop most people meet - everything later reuses its shape.

  • Binary Search (Easy) — The canonical divide-and-conquer search. Maintain a window and halve it each probe, discarding the half that cannot hold the target.

2. Hash maps

Trading memory for O(1) lookups is the single most common interview transformation - Two Sum is its purest form.

Builds on: Arrays and binary search

  • Two Sum (Easy) — Store each value's index in a map and look up the complement. Trades space for O(n) time.

3. Stacks and queues

Last-in-first-out and first-in-first-out are the two disciplines every later structure specializes.

Builds on: Arrays and binary search

  • Valid Parentheses (Easy) — The canonical stack problem. The top of the stack is always the bracket that must close next; the string is valid only if the stack empties.
  • Number of Recent Calls (Easy) — A FIFO queue of timestamps; evict from the front anything outside the window. Shows how a queue tracks a sliding time range.
  • Design Circular Queue (Medium) — A fixed-capacity buffer with head/rear indices that wrap around. Enqueue and dequeue in O(1) without shifting.

4. Prefix sums

Precompute once, answer forever - the simplest example of paying upfront for O(1) queries.

Builds on: Arrays and binary search

  • Range Sum Query (Easy) — Precompute cumulative sums so any range sum is a single subtraction. Turns O(n) queries into O(1).

5. Matrix traversal

Boundary management on a 2D grid - the spiral is careful index bookkeeping made visible.

Builds on: Arrays and binary search

  • Spiral Matrix (Medium) — Walk a 2D grid in spiral order by shrinking four boundaries inward. Teaches careful boundary management on a matrix.

6. Linked lists

Pointer rewiring without losing the rest of the list - the fundamental in-place manipulation.

Builds on: Arrays and binary search

  • Reverse Linked List (Easy) — Flip every next-pointer in one pass. The fundamental pointer-rewiring exercise.

7. Recursion

Watching fib(5) explode into a call tree is the fastest cure for treating recursion as magic - and the setup for trees and DP.

Builds on: Arrays and binary search

  • Fibonacci (Recursion Tree) (Easy) — Naive fib(n) - the call tree is the lesson: exponential repeated work that memoization later collapses.

8. Monotonic deques

A queue that throws away everything that can never matter - the hardest of the linear structures, worth meeting after plain queues.

Builds on: Stacks and queues

  • Sliding Window Maximum (Hard) — A deque of indices kept decreasing; the front is always the window max. The definitive monotonic-deque problem.

9. Trees

Recursion given a shape: inorder traversal shows why a BST visits values in sorted order.

Builds on: Recursion

  • Binary Tree Inorder (Easy) — Inorder traversal of a BST visits values in sorted order. Shows how recursion threads left, node, right.

10. Dynamic programming

Recursion's repeated work, cached into a table: unique-paths is the 2D recurrence at its most visual.

Builds on: Recursion, Matrix traversal

  • Unique Paths (Medium) — Fill a DP table where each cell is the sum of the cell above and to the left. The classic 2D DP recurrence.

11. Heaps

A tree flattened into an array - sift-up makes the parent-child arithmetic physical.

Builds on: Trees

  • Build a Min-Heap (Medium) — Insert values one by one, sifting each up until the parent is smaller. The heap array is a complete binary tree.

12. Tries

Shared prefixes share nodes: the structure IS the compression.

Builds on: Trees

  • Implement Trie (Medium) — Insert words into a prefix tree, then test a prefix by walking character edges. Shared prefixes share nodes.

13. Union-find

A forest wearing an array costume - watching the parent array during merges is what makes the mechanism click.

Builds on: Trees

  • Connected Components (Medium) — Merge elements into disjoint sets and count the roots. Near-constant per operation with path compression.

14. Graphs and BFS

BFS is the frontier queue - which is why queues come long before graphs on this path.

Builds on: Stacks and queues, Trees

  • Breadth-First Search (Medium) — Explore a graph in layers using a frontier queue. Visits nodes in non-decreasing distance from the source.