Problem-Solving Patterns

A repeatable method

Strong problem solvers are not faster thinkers; they waste less time. They follow roughly the same steps every time, so they never start coding before they understand the problem, and never optimize before they have a correct baseline.

1. Understand. Restate the problem in your own words. Pin down inputs (types, sizes, ranges, sorted? duplicates? negatives?), the exact output, and what to do with invalid or empty input. Ask questions.
2. Examples. Work two or three by hand, including a tiny one and a tricky one. Hand-solving is where patterns appear: "I kept looking back for the last smaller value…" is a monotonic stack waiting to happen.
3. Brute force. State the simplest correct algorithm and its complexity, even if it is hopeless. It proves you understand the problem and becomes your test oracle.
4. Optimize. Find the bottleneck in the brute force and ask which pattern removes it (the catalogue below). Use the input size to target a complexity: n ≤ 20 allows O(2ⁿ); n ≤ 10³ allows O(n²); n ≤ 10⁵–10⁶ needs O(n log n) or O(n).
5. Code. Write clean code with good names. Small helpers beat clever one-liners.
6. Test. Run your examples, then edge cases, then (when possible) random inputs against the brute force.
7. Analyze. State time and space complexity and justify them. Mention trade-offs.

The size-to-complexity table is worth memorizing, because Python executes roughly 10⁷ simple operations per second:

The pattern catalogue

Most problems are variations on a dozen patterns. The skill is reading the signals in the statement.

A decision flowchart

flowchart TD
  A[Read the problem: input size, output, constraints] --> B{Enumerate all
arrangements or subsets?}
  B -- yes --> BT[Backtracking with pruning
bitmasks if n ≤ 20]
  B -- no --> C{Graph, grid, or
relationships?}
  C -- "shortest steps" --> BFS[BFS]
  C -- "weighted shortest" --> DJ[Dijkstra / A*]
  C -- "groups / connectivity" --> UF[Union-find or DFS]
  C -- no --> D{Contiguous subarray
or substring?}
  D -- yes --> SW[Sliding window or prefix sums]
  D -- no --> E{Sorted input or
sortable without losing info?}
  E -- "pairs / partition" --> TP[Two pointers]
  E -- "find a value" --> BS[Binary search]
  E -- no --> F{Monotone feasibility:
if x works, x+1 works?}
  F -- yes --> BA[Binary search on the answer]
  F -- no --> G{Count ways or optimize
over sequential choices?}
  G -- yes --> H{Greedy choice
provable?}
  H -- yes --> GR[Greedy]
  H -- no --> DP[Dynamic programming]
  G -- no --> I{Top k, or repeatedly
extract the best?}
  I -- yes --> HP[Heap]
  I -- no --> J{Next greater or smaller
for each element?}
  J -- yes --> MS[Monotonic stack]
  J -- no --> HS[Hashing for O(1) lookups
then revisit the brute force]
    

Walkthrough 1: two sum (hashing)

Problem. Given a list of integers and a target, return the indexes of two different elements that sum to the target (assume exactly one answer).

Brute force: check every pair, O(n²). Bottleneck: for each x we scan the whole list looking for target - x. Pattern: "have I seen the complement?" is a set or dict lookup. One pass, storing each value's index after checking, so an element never pairs with itself.

Analysis: O(n) expected time, O(n) space. If the input were sorted, two pointers would give O(n) time and O(1) space; trading space for time is a choice worth saying out loud.

Walkthrough 2: longest substring without repeats (sliding window)

Problem. Return the length of the longest substring with no repeated characters.

Brute force: check all O(n²) substrings, each in O(n): O(n³). Bottleneck: neighboring substrings share almost everything. Pattern: "contiguous" + "longest with a constraint" = sliding window. Grow the right edge; when the constraint breaks, move the left edge past the previous occurrence of the repeated character. Each index enters and leaves the window at most once: O(n).

Walkthrough 3: ship within D days (binary search on the answer)

Problem. Packages with weights must ship in order over at most D days. Find the minimum ship capacity that makes it possible.

Brute force: try every capacity from max(weights) up to sum(weights), simulating each: O(n · sum). Signal: feasibility is monotone: if capacity c works, every larger capacity works too. A monotone yes/no predicate over a range is exactly what binary search needs (M30), even though we are searching over answers, not an array.

Analysis: O(n log(sum)) time, O(1) space. The template (find the smallest x where feasible(x) is true) solves a whole family: minimum eating speed, smallest divisor, splitting arrays, placing routers.

Walkthrough 4: rotting oranges (multi-source BFS)

Problem. In a grid, 2 = rotten orange, 1 = fresh, 0 = empty. Each minute, rotten oranges rot their four neighbors. Return the minutes until no fresh orange remains, or −1 if some never rot.

Brute force: simulate minute by minute, scanning the whole grid each time: O((rows·cols)²). Signal: grid + "minimum time/steps" = BFS. Start the queue with all rotten oranges at once (multi-source BFS); BFS layers are minutes. Each cell enters the queue once: O(rows·cols).

Walkthrough 5: k most frequent words (heap)

Problem. Return the k most frequent words, ties broken alphabetically.

Brute force: count, then sort all distinct words: O(u log u) for u distinct words. That is often fine! Signal: "top k" with k much smaller than u suggests a heap of size k: O(u log k). heapq.nsmallest does this for you with a key.

Walkthrough 6: daily temperatures (monotonic stack)

Problem. For each day, how many days until a warmer temperature? (0 if never.)

Brute force: for each day scan forward: O(n²) on a decreasing list. Signal: "next greater element" for every position. Keep a stack of indexes whose answer is still unknown; their temperatures are decreasing from bottom to top (that is the monotonic invariant). A new warmer day resolves every cooler day on top. Each index is pushed and popped once: O(n).

Testing edge cases

Most wrong answers come from a handful of input shapes. Run through this list for every problem:

The most powerful technique is differential testing: compare the optimized solution with the brute force on thousands of small random inputs. When they disagree, you have a minimal failing case for free.

Communicating complexity

Whether in an interview, a design document, or a code review, a complexity claim should be precise and justified.

• Name your variables. "O(n + m) where n is the text length and m the pattern length", not "O(n)". For graphs, use V and E; for grids, rows·cols.
• State time and space separately, and say whether space counts the output.
• Say which case. Worst, average/expected (hashing, quickselect), or amortized (list append, monotonic stack, union-find).
• Justify in one sentence. "Each index is pushed and popped at most once, so the while loop runs at most n times in total."
• Mention hidden costs. Slicing and string concatenation copy (O(k)); x in list is O(n); list.pop(0) is O(n), use collections.deque.
• Connect to the constraints. "n ≤ 10⁵, so O(n log n) is about 2 million steps: comfortably fast."

How to practice

Patterns become automatic through deliberate, spaced practice, not marathon sessions.

Practice

Six problems, six different patterns, deliberately unlabeled in their titles. Before coding, write down which signal you notice and which technique it suggests.

from collections import Counter

def count_pairs_with_diff(nums: list[int], k: int) -> int:
    counts = Counter(nums)
    if k == 0:
        return sum(1 for c in counts.values() if c > 1)
    return sum(1 for v in counts if v + k in counts)

def shortest_subarray(nums: list[int], target: int) -> int:
    best = len(nums) + 1
    left = window = 0
    for right, x in enumerate(nums):
        window += x
        while window >= target:
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == len(nums) + 1 else best

def min_speed(piles: list[int], h: int) -> int:
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        hours = sum(-(-p // mid) for p in piles)
        if hours <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

def count_islands(grid: list[str]) -> int:
    seen: set[tuple[int, int]] = set()
    islands = 0
    for r, row in enumerate(grid):
        for c, cell in enumerate(row):
            if cell != "#" or (r, c) in seen:
                continue
            islands += 1
            stack = [(r, c)]
            seen.add((r, c))
            while stack:
                cr, cc = stack.pop()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < len(grid) and 0 <= nc < len(grid[nr]) and grid[nr][nc] == "#" and (nr, nc) not in seen:
                        seen.add((nr, nc))
                        stack.append((nr, nc))
    return islands

def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    stack: list[int] = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            answer[stack.pop()] = x
        stack.append(i)
    return answer

def earliest_all_connected(n: int, logs: list[tuple[int, int, int]]) -> int:
    parent = list(range(n))
    size = [1] * n
    groups = n

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]      # path halving
            x = parent[x]
        return x

    if groups == 1:
        return 0
    for time, a, b in sorted(logs):
        ra, rb = find(a), find(b)
        if ra == rb:
            continue
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra                         # union by size
        size[ra] += size[rb]
        groups -= 1
        if groups == 1:
            return time
    return -1

Mini-project

pixi init practice && cd practice
pixi add python pytest
mkdir -p problems tests
pixi run pytest -q                  # run everything
pixi run pytest -q -k sliding       # run one pattern

practice/
  pixi.toml
  JOURNAL.md                  # one entry per attempt
  problems/
    p01_two_sum.py            # each file: docstring statement, brute(), solve()
    ...
  tests/
    test_p01_two_sum.py       # examples + edge cases + random brute-vs-solve check

Quiz

Recap

• Method: understand → examples → brute force → optimize → code → test → analyze.
• Use the input size to pick a target complexity before designing.
• Read signals: complement lookup → hashing; contiguous + constraint → sliding window; monotone feasibility → binary search on the answer; grid steps → BFS; top k → heap; count/optimize choices → DP or provable greedy; all arrangements → backtracking; merging groups → union-find; next greater → monotonic stack.
• Test edge cases from a checklist and use the brute force as an oracle.
• Communicate complexity with named variables, separate time and space, and a one-sentence justification.
• Practice with a journal, spaced re-solving, timed sessions, and interleaved topics.

Going further

• collections: Counter, deque, defaultdict
• heapq and bisect
• timeit: measure execution time
• Python wiki: time complexity of built-in operations
• Put it all together: Project 4: Puzzle Solver Suite. Then continue to Part 5 · M36 Metaprogramming.