# DSA & Implementation

> Fast, clean implementation ability: arrays, graphs, trees, dynamic programming, and the core algorithmic patterns.

Canonical: https://learn.significanthobbies.com/curriculum/tracks/dsa

Fast, clean implementation ability: arrays, graphs, trees, dynamic programming, and the core algorithmic patterns.

This track contains 27 connected concepts. Mastery means explaining each
mechanism, predicting its failure modes, and supporting decisions with code,
measurements, or a reviewable design artifact.

## Roadmaps

- [DSA Practice](https://learn.significanthobbies.com/curriculum/roadmaps/dsa-practice) — Solve canonical patterns from scratch — no references, explain the invariant, add one edge-case test.

## Concepts

- [Arrays & Hashing](https://learn.significanthobbies.com/curriculum/concepts/array-hashing) (intro) — Hash maps, sets, frequency counting.
- [Two Pointers](https://learn.significanthobbies.com/curriculum/concepts/two-pointers) (core) — Converging/diverging pointer scans.
- [Sliding Window](https://learn.significanthobbies.com/curriculum/concepts/sliding-window) (core) — Variable/fixed window over sequences.
- [Stack](https://learn.significanthobbies.com/curriculum/concepts/stack) (intro) — LIFO, parsing, monotonic stack.
- [Binary Search](https://learn.significanthobbies.com/curriculum/concepts/binary-search) (core) — Halving sorted search space, predicate search.
- [Linked List](https://learn.significanthobbies.com/curriculum/concepts/linked-list) (intro) — Pointer manipulation, fast/slow, reversal.
- [Trees](https://learn.significanthobbies.com/curriculum/concepts/trees) (core) — Binary trees, BSTs, DFS/BFS.
- [Trie](https://learn.significanthobbies.com/curriculum/concepts/tries) (core) — Prefix trees.
- [Heap / Priority Queue](https://learn.significanthobbies.com/curriculum/concepts/heap) (core) — Top-k, k-way merge, scheduling.
- [Backtracking](https://learn.significanthobbies.com/curriculum/concepts/backtracking) (advanced) — DFS with state restoration, pruning.
- [Graphs](https://learn.significanthobbies.com/curriculum/concepts/graphs) (advanced) — BFS/DFS, topo sort, union-find.
- [Shortest Path](https://learn.significanthobbies.com/curriculum/concepts/shortest-path) (advanced) — Dijkstra, Bellman-Ford, A*.
- [Union-Find](https://learn.significanthobbies.com/curriculum/concepts/union-find) (core) — Disjoint set, path compression.
- [1D DP](https://learn.significanthobbies.com/curriculum/concepts/dp-1d) (advanced) — Linear state recurrences.
- [2D DP](https://learn.significanthobbies.com/curriculum/concepts/dp-2d) (advanced) — Grid DP, edit distance, knapsack.
- [Greedy](https://learn.significanthobbies.com/curriculum/concepts/greedy) (core) — Local-optimal-as-global proofs.
- [Intervals](https://learn.significanthobbies.com/curriculum/concepts/intervals) (core) — Merge, overlap, sweep line.
- [Math & Geometry](https://learn.significanthobbies.com/curriculum/concepts/math-geometry) (core) — Number theory, modular, geometry.
- [Bit Manipulation](https://learn.significanthobbies.com/curriculum/concepts/bit-manipulation) (core) — Bitwise ops, masks, XOR tricks.
- [Complexity Analysis](https://learn.significanthobbies.com/curriculum/concepts/complexity-analysis) (intro) — Big-O, amortised cost, and space complexity — how to argue a bound before writing code.
- [Sorting](https://learn.significanthobbies.com/curriculum/concepts/sorting) (core) — Comparison sorts, stability, in-place versus extra space, and when a linear-time sort is available.
- [Prefix Sums](https://learn.significanthobbies.com/curriculum/concepts/prefix-sums) (core) — Precomputed cumulative arrays that turn repeated range queries into O(1) lookups.
- [Monotonic Stack](https://learn.significanthobbies.com/curriculum/concepts/monotonic-stack) (core) — A stack kept sorted so each element is pushed and popped once, answering next-greater questions in O(n).
- [String Matching](https://learn.significanthobbies.com/curriculum/concepts/string-matching) (core) — Finding a pattern in text in linear time — KMP's failure function and Rabin-Karp's rolling hash.
- [Minimum Spanning Tree](https://learn.significanthobbies.com/curriculum/concepts/minimum-spanning-tree) (core) — Kruskal and Prim — connecting every node at least total cost.
- [Recursion & Induction](https://learn.significanthobbies.com/curriculum/concepts/recursion-and-induction) (intro) — Writing recursion you can trust, and solving the recurrence it produces.
- [Quickselect](https://learn.significanthobbies.com/curriculum/concepts/quickselect) (core) — Finding the k-th smallest in expected O(n) by recursing into only one partition.