Choosing a Pattern: Decision Guide and Worked Examples
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Once you can read the limits and the wording, you need a repeatable way to pick one pattern. A short decision guide does that, and worked examples show where each branch breaks.
Four questions, asked in order
A decision guide is a short list of questions that leads from the wording and limits of a problem to a pattern. It does not solve the problem. It tells you which template to try first.
Most problems fall to one of a few patterns. Ask the same four questions every time, from the strongest clue to the weakest.
def choose(sorted_data, threshold, consecutive, every_result): if every_result: return "backtracking" if threshold: return "binary search on the answer" if consecutive: return "window or prefix sums" if sorted_data: return "two pointers or binary search" return "hashing, bits or maths"
print(choose(False, False, True, False))Example 1 · Apply the guide to five problems
def choose(sorted_data, threshold, consecutive, every_result): if every_result: return "backtracking" if threshold: return "binary search on the answer" if consecutive: return "window or prefix sums" if sorted_data: return "two pointers or binary search" return "hashing, bits or maths"
problems = { "all arrangements of 5 tags": (False, False, False, True), "least capacity within D days": (False, True, False, False), "best total of k consecutive days": (False, False, True, False), "pair with a sum in a sorted list": (True, False, False, False), "the number that has no partner": (False, False, False, False),}for name, flags in problems.items(): print(name, "->", choose(*flags))all arrangements of 5 tags -> backtracking least capacity within D days -> binary search on the answer best total of k consecutive days -> window or prefix sums pair with a sum in a sorted list -> two pointers or binary search the number that has no partner -> hashing, bits or maths
What this code does
- Each problem is reduced to four yes or no answers.
- The last problem has no strong clue, so it falls to hashing, bits or maths. XOR is the bit answer.
The order matters: a request for every result already settles the pattern, however the data looks. The picture shows the same questions as a chart.
Worked example: positive numbers
A condition is monotonic if, once it becomes true as a value grows, it stays true. Monotonic conditions allow sliding windows and binary search on the answer.
Find the shortest run of orders that reaches a target total. All values are positive, so a longer run never has a smaller total.
def shortest(orders, target): left = total = 0 best = len(orders) + 1 for right, v in enumerate(orders): total += v while total >= target: best = min(best, right - left + 1) total -= orders[left] left += 1 return best if best <= len(orders) else 0
print(shortest([2, 3, 1, 2, 4, 3], 7))Example 2 · Brute force, then the window
orders = [2, 3, 1, 2, 4, 3]target = 7
brute = 0for start in range(len(orders)): total = 0 for end in range(start, len(orders)): total += orders[end] if total >= target: length = end - start + 1 if brute == 0 or length < brute: brute = length break
left = total = 0best = len(orders) + 1for right, v in enumerate(orders): total += v while total >= target: best = min(best, right - left + 1) total -= orders[left] left += 1
print(brute, best)2 2
What this code does
- Brute force tries every start and extends until the target is reached, which can cost n times n steps.
- The window moves each end forward only, so it takes about 2n steps and O(1) extra space.
Growing the run only raises the total, and shrinking only lowers it. That one-way behaviour is what makes a window correct.
Worked example: negative numbers
A prefix sum is the total of all values up to and including a position. The total of any range is one prefix sum minus another, which turns range questions into lookups.
Now the values may be negative and the total must be exact. A longer run can have a smaller total, so a window no longer works. Prefix sums with a dictionary do.
from collections import defaultdict
def count_exact(values, k): seen = defaultdict(int) seen[0] = 1 total = count = 0 for v in values: total += v count += seen[total - k] seen[total] += 1 return count
print(count_exact([1, -1, 0], 0))Example 3 · Prefix sums with a dictionary
from collections import defaultdict
values = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
brute = sum(1 for i in range(len(values)) for j in range(i, len(values)) if sum(values[i:j + 1]) == k)
seen = defaultdict(int)seen[0] = 1total = fast = 0for v in values: total += v fast += seen[total - k] seen[total] += 1
print(brute, fast)4 4
What this code does
- The brute force sums each range from scratch, about n cubed steps in the worst case.
- The dictionary version does one pass and uses O(n) space for the totals.
Example 4 · Binary search on the answer
weights = [3, 2, 2, 4, 1, 4]days = 3
def needed(cap): count, load = 1, 0 for w in weights: if load + w > cap: count += 1 load = 0 load += w return count
brute = next(c for c in range(max(weights), sum(weights) + 1) if needed(c) <= days)
lo, hi = max(weights), sum(weights)while lo < hi: mid = (lo + hi) // 2 if needed(mid) <= days: hi = mid else: lo = mid + 1
print(brute, lo)6 6
What this code does
- Trying each capacity in turn is the brute force. More capacity never needs more days, so the test is monotonic.
- Halving the range takes about log of the total weight tests instead of up to the total.
Two equal prefix totals mean the numbers between them add to zero. The dictionary counts how many earlier totals match.
Next step
Check your understanding
10 quick questions