progress

Train until you beat the boss.

The gauntlet: tiny Python problems, back to back. Miss one and it comes back tomorrow, then in 3, 7 and 21 days, until it sticks.

Or beat this boss first: it's binary search. All 86 bosses →

Loading the fight…

From the Shorts

All 86 bosses →

World map

Each world is one topic: an animated guide that shows the idea running, then its problems. Worlds build on the ones to their left, and every road ends at the castle.

Game modes

Free. Progress saves in your browser from the first answer; sign in with your email to keep it everywhere.

01

Searching & scanning

Squeeze a linear scan down to one pass, or a search down to log n.

  1. Complexity analysis Estimate how the work grows with the input, and read the limits on n to know which approach will be fast enough. O(n)
  2. Sorting with custom keys Describe the order and let the library sort. Keys, tuples, stable sorts, comparators, and huge values squeezed into ranks 0..k−1. O(n log n)
  3. Binary search Find a value in a sorted array by halving the range on every look. A million elements take at most 20 looks. O(log n)
  4. Two pointers Find two values that add up to a target in a sorted array with one pass from both ends. O(n) time, no extra memory. O(n)
  5. Sliding window Find the best contiguous stretch of an array or string in one pass: grow a window on the right, shrink it from the left. O(n)
  6. Monotonic stack Find each element's nearest bigger (or smaller) neighbour in one pass, with a stack that stays sorted. O(n)
  7. Prefix sums Add up an array once, left to right. After that, the sum of any range is one subtraction. O(n)
  8. Binary search on the answer When you can check a guess but can't compute the answer directly, binary search over the guesses for the first one that works. O(n log m)
  9. Intervals Sort ranges by where they start, then sweep once: each range either joins the one before it or starts a new one. O(n log n)
  10. Greedy algorithms Make the choice that looks best right now and never undo it. Works when you can prove that choice is always safe. O(n log n)
02

Data structures

The containers that make the fast algorithms possible.

  1. Hash maps Store and find values by key in constant time on average. The workhorse behind counting, two sum and grouping. O(1)
  2. Stacks Last in, first out. A stack hands you the most recent unfinished thing in O(1): the tool for brackets, undo and postfix. O(1)
  3. Linked lists Reverse a linked list in place with three pointers, then reuse the same habits: a dummy head, and fast and slow pointers. O(n)
  4. Heaps (priority queues) Always know the smallest item, even while items keep arriving. Push and pop in O(log n), peek in O(1). O(log n)
  5. Scheduling with heaps Run a timeline event by event. One heap says which room frees up next; another picks which free room or job goes now. O(n log n)
  6. Trie (prefix tree) A tree of letters where words that share a start share nodes. Checking a word or a prefix takes one step per letter. O(L)
  7. Union-find Track which items belong together as you merge groups. Both merging and asking "same group?" take almost constant time. O(α(n))
  8. LRU cache A fixed-size cache that throws out whatever was used longest ago. A hash map plus a doubly linked list make get and put O(1). O(1)
  9. Sorted containers Keep keys in order while they change, and find the nearest key at or below any value in O(log n). O(log n)
03

Core techniques

Recursion, bits and grids: tools that turn up inside every other topic.

  1. Recursion & backtracking List every subset, ordering or combination by building one choice at a time, and undoing each choice before trying the next. O(2ⁿ · n)
  2. Bit manipulation Read a number as a row of on/off bits. AND, OR, XOR and shifts test, set, clear and count them in a step or two. O(1)
  3. Matrices in place Rotate, spiral through and mark a grid without a second copy. Each trick starts with a formula for where cell (r, c) goes. O(rows·cols)
  4. Concurrency Threads that share data can lose updates. Locks, condition variables and a bounded queue make them take turns safely. O(1)
04

Graphs

Grids, networks, dependencies: anything with things and links between them.

  1. Binary trees and traversals Visit every node of a binary tree in preorder, inorder, postorder or level order, with recursion, a stack or a queue. O(n)
  2. BFS and DFS The two ways to walk a graph. BFS spreads out in rings and finds fewest-edge paths; DFS dives down one path and backs up. O(V + E)
  3. Bipartite graphs (2-colouring) Can the nodes be split into two sides so every edge crosses between them? Colour them with BFS and watch for a clash. O(V + E)
  4. Cycle detection Find out whether a directed graph loops back on itself: DFS with three colours spots the edge that closes a cycle. O(V + E)
  5. Topological sort Put the nodes of a directed graph in an order where every edge points forward, or find out that a cycle makes it impossible. O(V + E)
  6. Dijkstra's algorithm Shortest paths from one source when edge weights are never negative. Always finish the closest unfinished node next. O((V + E) log V)
  7. Minimum spanning tree Connect every node of a weighted graph as cheaply as possible. Kruskal takes the lightest edges first and skips any that close a cycle. O(E log E)
05

Dynamic programming

Solve each subproblem once, remember it, build up the answer.

  1. Dynamic programming: the basics Solve each small subproblem once, store the answer, and build bigger answers from it. Learned here on House Robber. O(states × work per state)
  2. Grid paths The cheapest route across a grid when you can only move right or down: each cell takes the better of the cell above and the one to its left. O(rows·cols)
  3. 0/1 knapsack Pick items with the most total value that fit under a weight limit, each item at most once, by filling a table of item × capacity. O(n·W)
  4. Longest increasing subsequence The longest run of values that only go up, picked in order from an array. O(n²) with a simple DP, O(n log n) with binary search. O(n log n)
  5. Edit distance The fewest single-letter inserts, deletes and replacements that turn one word into another, from a table over prefix pairs. O(n·m)
  6. Interval DP Solve a problem for every substring or subarray, shortest first, so each range is built from the smaller ranges inside it. O(n²)
  7. Dynamic programming on trees Solve a tree children first: each node turns its children's answers into its own and hands one small summary up to its parent. O(n)
06

Practical systems

The build-it rounds: classes that grow over levels, simulations, parsers, caches and queues.

  1. Object-oriented design Build a class that survives new requirements: clear state, rules checked in one place, one method per operation. O(1)
  2. Simulation Follow the rules exactly, one step or one event at a time. A clock, a fixed order for ties, and rules kept apart from bookkeeping. O(steps)
  3. Iterators and generators Hand out items one at a time from nested data, merged streams or files, and save the position so a fresh iterator can resume it. O(1)
  4. Parsers and interpreters Turn text into tokens, tokens into structure, and structure into a value. One small function per grammar rule handles precedence and nesting. O(n)
  5. Rolling windows and rate counters Count what happened in the last N seconds, per key, in O(1) memory per second of window. The core of hit counters and rate limiters. O(1)
  6. AI infrastructure The plumbing around a model: batching requests, parsing streamed output, token budgets, rate limits, caches and sampling. Small systems with exact rules. O(1)
  7. Serialization and durability Turn data into bytes you can read back exactly, and keep a store correct across crashes with a write-ahead log that replays up to the last whole record. O(bytes)
  8. In-memory database Records of fields with scans, expiry, transactions and reads from the past. Keep every write, and answer everything through one lookup helper. O(log v)
  9. Time-travel key-value store Keep every version of every key, sorted by time, and answer "what was the value at time t" with one binary search. O(log v)
  10. Fault-tolerant work queue Hand tasks to workers with leases that run out, retry what failed, and give up on what keeps failing. A state machine plus a heap of deadlines. O(log n)
  11. In-memory file system Directories as nested maps, files as leaves. Split the path, walk one name at a time, and do every lookup through one helper. O(depth)
  12. Bank system Accounts, payments, effects that land later and balances at any past time. Validate first, drain what's due at the top of every call, and keep a history. O(log n)
  13. File deduplication Find identical files without reading most of them: group by size for free, then by the first bytes, and only then by a hash of the whole file. O(files)
  14. DNS resolver Follow aliases to an answer, detect loops with a seen set, and write each result back onto the whole chain so every name is looked up once. O(n)
07

Advanced & competitive

Competitive-programming structures. Rare in interviews, great for contests.

  1. Fenwick tree (binary indexed tree) Prefix sums that survive updates: change one element or sum any prefix in O(log n), with an array and ten lines of code. O(log n)
  2. Segment tree Answer range questions like "sum of a[l..r]" while the array keeps changing. Both updates and queries take O(log n). O(log n)
esc