Algorithms

How to get from a slow solution to a fast one. Most speedups come from one of three moves: stop repeating work, rule out candidates safely, or look at the problem a different way.

Stop repeating work

• Looking the same thing up again and again? Remember what you've seen in a hash map.
• Adding up overlapping ranges? With prefix sums, any range sum takes one subtraction. With a sliding window, you update a running total as the window moves.
• Solving the same subproblem from different starting points? Solve each one once and store the answer: that's dynamic programming.

Rule out candidates safely

• Looking for a pair in sorted input? Two pointers skip most pairs. After each move, you should be able to say why the skipped pairs can't be the answer.
• Is the answer "yes" up to some value and "no" after it? Binary search finds the boundary. The hard part is usually the yes-or-no check, not the search.
• Is one candidate never better than another, now or later? Drop it. This idea drives monotonic stacks and deques, many greedy proofs, and smaller DP states. Check that the comparison holds for every possible future before you drop anything.

Look at the problem a different way

• Treat each legal move as an edge, and the problem becomes graph search.
• Treat prerequisites as a dependency graph.
• In problems about splitting a range, the last action often divides it into independent parts: that's interval DP.
• When there's no shortcut, try every option with backtracking, and cut off branches that can't lead to a valid or better answer.

Practice choosing the technique

Knowing techniques isn't enough; you have to pick the right one for a new problem. These pages help:

• Moves that unlock problems and a map of useful observations
• Problems that look alike but need different methods
• Transfer exercises, which don't tell you the topic

Before you read a solution, write down five things: the slow solution, what makes it slow, the observation that fixes it, why the fix is correct, and an input that breaks your first idea.

More advanced topics, such as network flow, binary lifting, digit DP, and geometry, are listed in advanced techniques and when you need them. That page points you to further study rather than teaching them.