DSA Pattern Recognition Guide¶

Difficulty: All levels | Pattern Type: Meta / Synthesis

← Dynamic Programming | DSA Overview

Why This Page Exists¶

Problem: You're 90 seconds into reading an unfamiliar interview problem. It doesn't scream "this is a sliding window problem" the way a textbook chapter title would.

Brute force approach: Try coding something, usually nested loops, and hope a pattern emerges as you go. - Unpredictable time to a working solution - Often locks you into the wrong data structure before you've thought it through

Insight: Every pattern on this site answers a specific shape of question, and that shape is visible in the problem's keywords, input shape, and constraints before you write any code. "Pattern recognition" isn't memorizing 200 problems — it's memorizing the ~15 signals below and practicing spotting them fast.

Result: A 30-60 second triage step that gets you to the right family of technique before you commit to code, which is exactly what staff-level interviewers are evaluating when they watch your first few minutes.

Mental Model¶

Think of pattern recognition as narrowing a funnel: constraints eliminate whole complexity classes, then keywords select the specific technique within what's left.

                     Read the problem statement
                              |
              +---------------+----------------+
              |                                 |
      constraints (n, bounds)          input shape (array/string/
              |                         tree/graph/matrix/stream)
              v                                 v
       eliminates complexity           eliminates technique FAMILIES
       classes (see foundations.md)    (tree traversal vs array scan
              |                         vs graph search, etc.)
              +---------------+----------------+
                              |
                        keyword match
                     (see table below)
                              |
                              v
                     candidate pattern(s)
                              |
                    confirm: does the problem have the
                    STRUCTURAL property the pattern needs?
                    (sorted? monotonic? overlapping subproblems?)
                              |
                              v
                         commit + code

The "confirm" step matters — matching a keyword isn't enough. "Longest" appears in both sliding window problems (longest substring) and DP problems (longest increasing subsequence) — the difference is whether the answer region must be contiguous (sliding window) or can skip elements (DP).

Master Clue Table¶

Constraint-Driven Decision Table¶

Use n (or the relevant size bound) as a fast filter before keyword-matching:

Cross-reference with foundations.md for the full Big-O-to-pattern mapping and the general 6-step problem-solving process.

Worked Example: End-to-End Reasoning¶

Problem: "You are given an array of integers weights representing package weights, and an integer days. Packages must be shipped in order (you cannot reorder them), and each day's shipment cannot exceed the ship's capacity. Find the minimum capacity needed to ship all packages within days days."

Step 1 — clarify constraints: Say weights.length up to 5×10^4, weights up to 500 each. That's large enough to rule out anything above roughly O(n log(range)).

Step 2 — input shape: A 1D array, values must stay in original order (no sorting/reordering allowed) — this immediately rules out sorting-based array techniques and two pointers (which typically need reordering flexibility or a sorted precondition).

Step 3 — keyword scan: "minimum capacity... such that all ship within days days." That's the "minimize X such that a feasibility condition holds" phrasing — a strong signal for binary search on the answer, not a direct DP or greedy formula.

Step 4 — confirm the structural property: Is feasible(capacity) monotonic? If capacity C works (all packages fit within days days), does any capacity > C also work? Yes — more capacity can only reduce or maintain the number of days needed. Monotonic confirmed.

Step 5 — define search space: Minimum possible capacity = max(weights) (must fit the heaviest single package). Maximum possible capacity = sum(weights) (ship everything in one day). This is our [lo, hi] range.

Step 6 — define the feasibility check: days_needed(capacity) — greedily pack each day until adding the next package would exceed capacity, then start a new day. This is O(n) per check.

Step 7 — combine: Binary search over [lo, hi], calling the O(n) days_needed check at each step → O(n log(sum(weights))) total. This satisfies the constraint bound from Step 1.

Step 8 — code, test, restate complexity: (full solution in binary-search.md) — "This runs in O(n log(sum(weights))) time because we binary search over a bounded capacity range, and each feasibility check is a single O(n) linear scan. Space is O(1) beyond the input."

This is the reasoning chain interviewers want to see out loud, not just the final code.

Multi-Pattern Problems¶

Some problems combine two patterns — recognizing the combination is itself a signal of seniority:

Interview Follow-ups¶

1. "How do you handle a problem that doesn't match any pattern you know?" — Fall back to the foundations.md process: state brute force + complexity, then look for any structural property (sorted? monotonic? small state space?) you can exploit, even partially.
2. "What if two patterns both seem to fit?" — Pick whichever has the tighter proven complexity for the given constraints, and mention the alternative to show you considered tradeoffs.
3. "How do you avoid pattern-matching on a coincidental keyword?" — Always confirm the structural precondition (e.g., sortedness for two pointers, monotonicity for binary search on the answer) — don't commit on keyword alone.
4. "Staff-level follow-up: how would you generalize this pattern to a related problem?" — Practice articulating the invariant your technique relies on (e.g., "the window sum only needs O(1) updates because add/remove are both O(1)") — that's what transfers to novel problems.

Key Takeaways¶