AlgoScope

Problem-Solving Patterns

The cues in a problem statement that point at a technique, and the check that confirms the technique fits.

20 topics19 lessons1 families

A pattern here is a pairing: a shape that questions keep taking, and the technique that fits it. A contiguous subarray of length k points at a sliding window. Many range sums over an array that never changes points at a prefix sum. Next greater element points at a monotonic stack, dependency order points at a topological sort. The techniques themselves live in their own categories; what this group adds is the recognition step.

Every cue comes with a condition to test before committing. A sliding window needs the running answer to be repairable when one element leaves and another arrives. Binary search on the answer needs feasibility to be monotonic, so that if x works then everything past x works too. Two pointers needs a rule under which neither index ever has to move back. Skip the condition and you write code that passes the samples and fails on the case the condition would have ruled out.

The payoff is nearly always a nested loop collapsed into a single pass, or an exponent halved. A frequency map turns 'have I seen this' from a scan into a lookup; a difference array turns m range updates plus one read from m * n into m + n; meet in the middle enumerates two halves at 2^(n/2) rather than one space at 2^n. None of it is new machinery, and all of it depends on noticing which cue is in front of you.

After this you can

  • Map a question's wording onto a candidate technique in a few seconds
  • State the condition a pattern requires and test it against the problem before writing code
  • Choose between two plausible patterns by what the data allows: sorted, static, small n
  • Read the constraints as a hint about which complexities are still on the table
  • Recognise when no pattern applies and brute force is the honest starting point
307112733495i

3 is not in the set. Add it and move on. 1 distinct so far.

Open in the player →or start at step 2

In this order

  1. Frequency Map / HashingRecognize it for counting, grouping, anagram and "seen before" questions.
  2. Two PointersReach for it when two indices moving under a rule can replace a nested loop.
  3. Sliding WindowReach for it when the question is about contiguous subarrays or substrings.
  4. Prefix SumReach for it when many range sums are asked about an array that does not change.
  5. Difference ArrayRecognize it when many range updates precede a single read.
  6. Fast and Slow PointersReach for it on linked lists for cycles, middles and the nth from the end.
  7. Monotonic StackRecognize it for "next greater or smaller" and span questions.
  8. Binary Search on AnswerRecognize it when 'is x feasible?' is monotonic in x; binary search the answer space with one feasibility check per probe.
  9. GreedyRecognize it when a local choice can be proven safe by an exchange argument.
  10. Divide and ConquerRecognize it when the problem splits into independent halves with a cheap combine.
  11. MemoizationRecognize it when a recursive solution repeats subproblems.
  12. TabulationRecognize it when the dependency order of states is clear and iteration avoids recursion depth.
  13. BacktrackingRecognize it for "all solutions" and constraint-satisfaction questions.
  14. BitmaskingRecognize it when subsets of at most about 20 items must be tracked; every mask from 0 to 2^n - 1 is one subset.
  15. Meet in the MiddleSplit the input in two, enumerate each half, combine with sorting or hashing; 2^(n/2) instead of 2^n.
  16. Union-FindRecognize it for dynamic connectivity and grouping questions.
  17. Topological SortRecognize it for dependency ordering and "can all tasks finish" questions.
  18. Sweep LineSort the endpoints as events and sweep once, tracking how many intervals are open.

Also in this category

Patterns

Where people go wrong

Matching the wording instead of the structure

The word subarray suggests a sliding window, but a window only works while the running answer can be repaired in O(1) as elements enter and leave. With negative numbers and a sum-at-least-k target, shrinking the window is no longer safe and the pattern does not apply.

Binary searching an answer that is not monotonic

The search needs feasible(x) to be false up to a threshold and true from there on. If a larger x can fail where a smaller one succeeded, each probe steers into the wrong half and you get a plausible wrong number rather than an error.

Choosing a pattern before reading the constraints

n up to 20 says subsets or a bitmask; n up to 10^5 rules out anything quadratic; values up to 10^9 rule out any table indexed by value. The constraints narrow the candidates faster than the prose does.

Or a different category

Algorithmic Paradigms

You want the shape of the solution and the condition that makes it correct, not the cue that suggested it.

Complexity Analysis

The question is what a candidate approach would cost at the given input size, before any of it is written.

Lessons that teach these