🧭 DSA Mental Models - How to Think¶

Most interview problems reuse a small set of patterns. The skill isn't memorizing solutions - it's recognizing which pattern a problem is asking for. This page is the thinking layer: decision flowcharts, trigger signals, and the mental web connecting structures to techniques.

Pair it with the Quick Lookup (keyword → pattern table) and the runnable Code Library.

The one habit that matters most

Before coding, spend 60 seconds on: What's the input shape? What do the constraints imply? What's the target complexity? Those three answers usually name the pattern for you.

1. The 4-step recognition loop¶

The framework every strong candidate runs, consciously or not (source: LeetCode pattern-identification discussion):

flowchart LR
    A["Read problem<br/>+ constraints"] --> B["Ask trigger<br/>questions"]
    B --> C["Identify the<br/>pattern"]
    C --> D["Apply the<br/>template"]
    D --> E{Works +<br/>optimal?}
    E -- no --> B
    E -- yes --> F["Code it"]

The loop matters: if the first pattern doesn't fit the constraints, go back to the trigger questions - don't force a template.

2. Master decision flowchart - "which pattern?"¶

Start from the input shape, then branch on the signal words. This covers the majority of interview problems.

flowchart TD
    START([New problem]) --> SHAPE{Input shape?}

    SHAPE -- Array / String --> ARR{Signal?}
    ARR -- "contiguous subarray / substring" --> SW[Sliding Window]
    ARR -- "sum / range sum, immutable" --> PS[Prefix Sum]
    ARR -- "sorted + find pair / triplet" --> TP[Two Pointers]
    ARR -- "max/min subarray sum" --> KAD[Kadane]
    ARR -- "next greater / smaller" --> MS[Monotonic Stack]

    SHAPE -- Sorted / search space --> BS{"Can I discard half?"}
    BS -- yes --> BSEARCH[Binary Search / Search on Answer]

    SHAPE -- Tree --> TR{Traversal need?}
    TR -- "level by level" --> BFS1[BFS]
    TR -- "path / subtree / recursion" --> DFS1[DFS]

    SHAPE -- Graph --> G{Signal?}
    G -- "shortest path, unweighted" --> BFS2[BFS]
    G -- "shortest path, weighted" --> DIJ[Dijkstra]
    G -- "connectivity / groups" --> UF[Union-Find]
    G -- "ordering / dependencies" --> TOPO[Topological Sort]

    SHAPE -- "Combinatorial (all X)" --> BT["all permutations / subsets / combinations"]
    BT --> BACK[Backtracking]

    SHAPE -- "Optimization / counting" --> DP{"Overlapping subproblems<br/>+ optimal substructure?"}
    DP -- yes --> DPP[Dynamic Programming]
    DP -- "greedy choice safe?" --> GR[Greedy]

    SHAPE -- "Top-K / streaming" --> HEAP[Heap / Priority Queue]

3. Signal → pattern (trigger questions)¶

When the flowchart isn't obvious, these phrase-level signals almost always point at one pattern:

If the problem says…	Reach for	Why
"contiguous subarray/substring" + optimize	Sliding Window	one pass with a moving range
"sum over many ranges", array fixed	Prefix Sum	precompute cumulative sums
"sorted" + "pair/triplet summing to X"	Two Pointers	converge from both ends
"kth largest/smallest", "top K", "stream"	Heap	keep only K in order
"sorted" or "monotonic answer space"	Binary Search	discard half each step
"all permutations/subsets/combinations"	Backtracking	build incrementally, prune
"shortest path", unweighted grid/graph	BFS	explores by distance
"shortest path", weighted (non-negative)	Dijkstra	greedy by min distance
"are these connected / how many groups"	Union-Find	merge + find sets
"order tasks with dependencies"	Topological Sort	DAG ordering
"next greater/smaller element"	Monotonic Stack	maintain ordered stack
"max/min/count ways", overlapping states	Dynamic Programming	memoize subproblems
"min coins / max profit", local optimum works	Greedy	prove exchange argument

Full keyword table: DSA Quick Lookup.

4. Constraints → target complexity¶

The constraint size tells you the complexity you're allowed - which narrows the pattern before you even think about the approach. This is one of the highest-leverage interview habits.

flowchart LR
    N["Input size n"] --> A["n ≤ ~12<br/>O(n!)"] --> A1["permutations, brute force"]
    N --> B["n ≤ ~20<br/>O(2ⁿ)"] --> B1["subsets, bitmask DP, backtracking"]
    N --> C["n ≤ ~500<br/>O(n³)"] --> C1["Floyd-Warshall, 3 nested loops, interval DP"]
    N --> D["n ≤ ~5000<br/>O(n²)"] --> D1["DP tables, nested loops"]
    N --> E["n ≤ 10⁶<br/>O(n log n)"] --> E1["sort, heap, binary search"]
    N --> F["n ≤ 10⁸<br/>O(n)"] --> F1["two pointers, sliding window, hashing"]

n up to	Allowed complexity	Typical techniques
~12	O(n!)	permutations, brute force
~20	O(2ⁿ)	subsets, bitmask DP, backtracking
~500	O(n³)	Floyd-Warshall, interval DP
~5,000	O(n²)	DP tables, nested loops
~10⁶	O(n log n)	sorting, heap, binary search
~10⁸	O(n) or O(log n)	two pointers, sliding window, hashing

Numbers are rough (assume ~10⁸ simple ops/sec). The point is direction, not precision.

5. The mental web - how it all connects¶

Patterns aren't isolated; they grow out of a few core structures and ideas. Seeing the web helps you derive a pattern when you can't recall it.

flowchart TD
    REC["Recursion"] --> DFS["DFS"]
    REC --> BT["Backtracking"]
    REC --> DP["Dynamic Programming"]
    DFS --> BT
    BT --> DP

    ARR["Array / String"] --> TP["Two Pointers"]
    ARR --> SW["Sliding Window"]
    ARR --> PS["Prefix Sum"]
    ARR --> BSEARCH["Binary Search"]

    STACK["Stack"] --> MONO["Monotonic Stack"]
    QUEUE["Queue"] --> BFS["BFS"]
    HEAP["Heap"] --> TOPK["Top-K / scheduling"]

    GRAPH["Graph"] --> DFS
    GRAPH --> BFS
    GRAPH --> DIJ["Dijkstra"]
    GRAPH --> UF["Union-Find"]
    GRAPH --> TOPO["Topological Sort"]
    HEAP --> DIJ

    TREE["Tree"] --> DFS
    TREE --> BFS
    TRIE["Trie"] --> ARR

Read it as "X is built from / leads to Y." For example: backtracking is DFS with undo, and DP is backtracking with memoization - if you can write the brute-force recursion, you can usually optimize it into DP.

6. Per-family mini decision trees¶

Dynamic Programming - "is it DP, and what's the state?"¶

flowchart TD
    Q1{"Asks for max/min/count<br/>of ways?"} -- no --> NOTDP["Probably not DP"]
    Q1 -- yes --> Q2{"Do choices overlap<br/>(same subproblem repeats)?"}
    Q2 -- no --> GR["Greedy? Divide & conquer?"]
    Q2 -- yes --> STATE["Define STATE = what varies<br/>(index, remaining, last choice)"]
    STATE --> TRANS["Write TRANSITION<br/>(recurrence from smaller states)"]
    TRANS --> BASE["Base cases + order<br/>(top-down memo or bottom-up)"]

Graph - "which traversal / algorithm?"¶

flowchart TD
    G{"What am I asked?"}
    G -- "reachable / components" --> DFSBFS["DFS or BFS / Union-Find"]
    G -- "shortest path, unweighted" --> BFS["BFS"]
    G -- "shortest path, weighted ≥0" --> DIJ["Dijkstra"]
    G -- "shortest path, negative edges" --> BF["Bellman-Ford"]
    G -- "all-pairs shortest path" --> FW["Floyd-Warshall"]
    G -- "order with dependencies" --> TOPO["Topological Sort"]
    G -- "min spanning tree" --> MST["Kruskal / Prim"]

Array / String - "which linear technique?"¶

flowchart TD
    A{"What's the ask?"}
    A -- "best contiguous window" --> SW["Sliding Window"]
    A -- "pair/triplet in sorted" --> TP["Two Pointers"]
    A -- "many range-sum queries" --> PS["Prefix Sum"]
    A -- "find in sorted / on answer" --> BS["Binary Search"]
    A -- "next greater/smaller" --> MONO["Monotonic Stack"]
    A -- "max subarray sum" --> KAD["Kadane"]

7. Worked examples - the loop in action¶

Watch the recognition process, not just the answer. In each, the signal does the work.

Longest substring without repeating characters

Shape/constraints: a string; asks for the longest contiguous substring with a property.
Signal: "longest contiguous substring + a constraint" → this is the canonical Sliding Window cue.
Why: expand the window while valid, shrink from the left when a repeat appears - one pass, O(n). A brute-force check of all substrings would be O(n²).
Pattern: Sliding Window.

Kth largest element in a stream

Shape/constraints: numbers arriving over time; need the Kth largest at any point.
Signal: "Kth largest" + "stream" → Heap. The "stream" word rules out sorting once.
Why: keep a min-heap of size K; the top is the Kth largest. Each insert is O(log K), far better than re-sorting O(n log n) each query.
Pattern: Heap / Priority Queue.

Course schedule (can you finish all courses given prerequisites?)

Shape/constraints: courses with dependency pairs → a graph; asks if a valid order exists.
Signal: "order with dependencies" / "detect if ordering possible" → Topological Sort (and cycle detection - a cycle means impossible).
Why: a DAG has a topological order; if you can't produce one (a cycle exists), you can't finish. Kahn's algorithm (BFS on in-degrees) or DFS with a visiting-state.
Pattern: Topological Sort.

Coin change (fewest coins to make an amount)

Shape/constraints: asks for the minimum count of ways to reach a target; the same sub-amounts recur across choices.
Signal: "min/max/count" + overlapping subproblems → Dynamic Programming. (A greedy "take the biggest coin" fails for arbitrary denominations - a classic trap.)
Why: dp[amount] = 1 + min(dp[amount - coin]) over coins. Define state (remaining amount), transition (try each coin), base case (dp[0]=0).
Pattern: Dynamic Programming.

The meta-lesson

In all four, the phrase ("longest contiguous", "Kth in a stream", "dependencies", "min count") pointed at the pattern before any coding. Training that phrase→pattern reflex is the whole game - see the signal table.

How to practice with this¶

For each new problem, say the input shape and constraints out loud before anything else.
Run the 4-step loop - resist jumping straight to code.
When stuck, walk the master flowchart and the signal table.
After solving, note which signal pointed at the pattern - that's what builds recognition.

Keyword → pattern table → DSA Quick Lookup
Intuition + when-to-use per pattern → DSA Complete Guide
Runnable implementations → Code Library