Back to DSAGroundworkDSA

Step 2 of 2 · your path

DSA, Advanced

Advanced DP, union-find, shortest paths, spanning trees, SCC and bridges, segment trees and sparse tables — plus the interview strategy that turns pattern knowledge into offers.

Start reading Change levelAll chapters

Your progress

0 / 14 done

Up next

Advanced DP

42 min read · 15 exercises

The way14 chapters

The order I'd read them in

About 9 h 55 min of reading. Tick off what you've read, it is remembered on this device.

  1. Advanced DPOnce you can design the state, every "impossible" DP is just a normal DP over a stranger index.
    42 min read15 exercises
    Mark as read
    15 exercises
  2. Union-Find (Disjoint Set)Twenty lines that answer "are these two connected?" in effectively constant time — forever.
    29 min read14 exercises
    Mark as read
    14 exercises
  3. Advanced graph algorithmsBFS is shortest path when every edge costs 1 — here is what to do when they don't.
    34 min read14 exercises
    Mark as read
    14 exercises
  4. Minimum Spanning TreeThe cheapest wiring that reaches every node — greedy is provably optimal here, and there are exactly two ways to be greedy.
    28 min read9 exercises
    Mark as read
    9 exercises
  5. Advanced graphs: SCC, bridges, Euler paths, LCAOne DFS that stamps each vertex with the time it was reached answers questions that look like they need a search per vertex.
    40 min read13 exercises
    Mark as read
    13 exercises
  6. Segment trees & Fenwick treesPrefix sums die the moment the array can change — these two structures buy back updates for a log factor.
    33 min read13 exercises
    Mark as read
    13 exercises
  7. Sparse tables and range tricksPay O(n log n) once on an array that never changes and a range minimum costs one comparison. Doubling, blocks and reordered queries cover what a table cannot.
    38 min read12 exercises
    Mark as read
    12 exercises
  8. String algorithmsPreprocess the pattern once, and you never have to look backward in the text again.
    33 min read13 exercises
    Mark as read
    13 exercises
  9. Design problemsThe interface is the spec — pick the data structure combo that meets the complexity contract before you write a line of code.
    36 min read13 exercises
    Mark as read
    13 exercises
  10. Advanced backtrackingSame three lines as before — the advanced part is saying "no" earlier and storing state in bits.
    45 min read12 exercises
    Mark as read
    12 exercises
  11. Game theory and probability DPWhen the other side is an opponent, take the worst case; when it is chance, take the average. Either way the answer is a table over positions.
    73 min read15 exercises
    Mark as read
    15 exercises
  12. Ordered sets without a TreeMapFloor, ceiling, rank and range counts over a set that keeps changing, built from a treap, buckets or a Fenwick tree, and the problems that need them.
    63 min read17 exercises
    Mark as read
    17 exercises
  13. Sweep line, offline queries and geometrySort the moments when something changes, keep a summary of what is active, and skylines, offline queries and most geometry questions become one pass.
    56 min read17 exercises
    Mark as read
    17 exercises
  14. Interview strategyThe algorithm is half the score — the other half is everything you say before, during and after writing it.
    45 min read7 exercises
    Mark as read
    7 exercises

Practice159 exercises

Practice at this level

Every exercise opens in the editor with tests you can run.