problem solving

The Puzzle Where You Can Only Push

A friendly look at Push the Boxes, a game where you can only push, never pull, and why planning ahead makes it hard for people and computers.

The River Puzzle That Teaches Computers to Think

Row a wolf, a goat, and a cabbage across a river without disaster, and discover the simple idea that helps computers solve puzzles too.

The River Puzzle That Hides a Big Idea

Ferry everyone across a river while keeping both banks safe, and meet constraint satisfaction, the friendly idea behind timetables and Sudoku.

How a Sliding Puzzle Teaches You to Plan

Slide numbered tiles into order and learn how planning works, why a step back can help, and why only half of all shuffles can be solved.

Memory: Why the Array Wins Even When the Step Count Says Otherwise

Big-O counts steps and assumes every step costs the same. It does not. A cache miss costs a hundred steps, and that is why a linked list loses to an array.

Problem Solving From Zero21

Fenwick Trees and Segment Trees: When Updates and Queries Interleave

Prefix sums break the moment an element changes. Two structures answer range questions and point updates in logarithmic time, and one of them is twenty lines.

Problem Solving From Zero19

Strings: Hashing, KMP, and the Z-Function

Where does this pattern occur? Three answers in linear time, each with a different trade: one is easy and probabilistic, two are exact and need a table.

Problem Solving From Zero18

The Number Theory You Actually Need

Sieves, greatest common divisors, modular arithmetic and inverses. Five tools, each about ten lines, that cover almost every number theory problem you will meet.

Problem Solving From Zero17

Game Theory: Nim, Losing Positions, and the Grundy Number

Two players, perfect information, no luck. Who wins? The answer comes from labelling positions, and one theorem collapses any such game into a single number.

Problem Solving From Zero16

Disjoint Sets, and the Cheapest Way to Connect Everything

Twelve lines of code, two operations, and a running time so close to constant that nobody bothers with the difference. Then minimum spanning trees for free.

Problem Solving From Zero15

Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall

Three algorithms, three different jobs. Which one to reach for depends on negative edges, on how many sources you have, and on nothing else.

Problem Solving From Zero14

Depth-First Search: Cycles, Components, and Topological Order

BFS goes wide, DFS goes deep, and the difference is not stylistic. DFS answers questions about structure that a queue simply cannot see.

Problem Solving From Zero13

Graphs: How to Store One, and Breadth-First Search

Half of all algorithm problems are graph problems in disguise. Here is how to represent a graph, and the search that finds shortest paths for free.

Problem Solving From Zero12

The Knapsack Family, and When the State Is a Set

Knapsack is one recurrence with a dozen disguises. Learn the family, then learn to put a set of items in the state with a bitmask when n is small.

Problem Solving From Zero11

Dynamic Programming Is a Table You Fill In

Four questions turn a problem into a dynamic program: what is the state, what is the answer for a state, what is the base, and in what order do you fill it.

Problem Solving From Zero10

Memoisation: Paying Once for an Answer

The cheapest optimisation in programming: remember what you already worked out. One dictionary turns an exponential recursion into a linear one.

Problem Solving From Zero09

Recursion and Backtracking: Trusting a Function You Have Not Finished Writing

Recursion is hard because everyone traces it. The habit that makes it mechanical: write the contract, trust the smaller call, never trace the stack.

Problem Solving From Zero08

Greedy: When Taking the Best Now Is Provably Right

A greedy rule that passes the samples and fails the tests is the most common way to lose a contest. Here is how to tell a correct greedy rule from a plausible one.

Problem Solving From Zero07

Binary Search, and Binary Search on the Answer

Searching a sorted array is the easy half. The useful half is guessing the answer and asking a monotone yes-or-no question, with no array in sight.

Problem Solving From Zero06

Pointers and Linked Lists: Addresses, and the Data Structure Made of Them

A pointer is the address of a box, not the box. Once that clicks, dynamic memory, references and the linked list all fall out of the same idea. In C and C++.

Problem Solving From Zero05

Sorting: What to Know, What to Call, and What to Sort By

You will almost never write a sort. You will constantly decide what to sort by, and that decision is where the problems are actually solved.

Problem Solving From Zero04

Prefix Sums and Two Pointers: The Array Tricks You Will Use Forever

Two techniques that turn a quadratic loop into a linear one, on the humblest data structure there is. Range sums in constant time, and the sliding window.

Problem Solving From Zero03

Big-O Without the Maths: Naming the Shape of a Curve

Big-O is not a speed and not a stopwatch. It is a claim about the shape of a curve. Six shapes, where each one comes from, and the four rules for reading them.

Problem Solving From Zero02

Counting the Steps: What Your Loop Actually Costs

Before any algorithm makes sense you need one habit: counting how many times a line runs. Here is that habit, built from four small C++ programs and a stopwatch.

Problem Solving From Zero01