🔎 Pattern Recognition — DSA

Read a problem, spot the signal, pick the technique — your triage map for DSA.

How to use this guide: read the problem statement, scan for the signals below (they are literal words and shapes that appear in prompts), and jump to the technique they point at. Most problems announce their pattern in one or two phrases. Match the loudest signal first, then confirm with the constraints (sortedness, "in place", "contiguous", input size).

SIGNAL → TECHNIQUE MAPPINGS

1. Words about contiguity and ranges

• "contiguous subarray / substring" + best (max/min/longest/shortest) or a count → Sliding Window. The word "contiguous" is the loudest tell; it rules out subsequence problems. Fixed k given ("every k-length window") → fixed window with a running aggregate. "Longest/shortest such that <condition>" → variable window that grows/shrinks on the condition.
• "running / prefix / cumulative sum", "sum left of i vs right of i", or repeated range-sum queries → Arrays (prefix sums). Precompute total, carry a left running sum, derive rightSum = total − left − a[i].
• "max/min so far while scanning" → single-pass running extreme (Arrays); no extra structure needed.
• O(1) access to the i-th element of "an array of integers" or a string → the Array itself is the structure; no conversion.

2. Words about pairs, order, and sortedness

• "sorted array" (or sortable) + "find two/three that sum to target", "pair with given difference", "count pairs/triplets" → Two Pointers from opposite ends (left/right): move left up to raise the sum, right down to lower it.
• "sort 0s/1s/2s", "move all zeros to end", "partition by pivot", "O(1) space / no extra space" → in-place Two Pointers sweep (Dutch National Flag: low/mid/high).
• answer depends on relative rank (k-th largest, median, closest values) or on adjacent/grouped elements (intervals, nearby diffs) → Sorting first — it turns a global search into a local neighbor scan.
• "intervals" + "merge / max concurrent / scheduling" → Sorting by start, then sweep end times (often with a min-heap). "Most non-overlapping intervals" / "longest chain of pairs" → Greedy (activity selection): sort by end, take a pair whose start beats the last end.
• "sorted output" with a bounded value range or explicit reference order → counting sort / bucketing (Company Practice), not a comparison sort.

3. Words about search and monotonic answer spaces

• "sorted" (or monotonic) + "find / does it exist" with an O(log n) feel → Binary Search (Searching).
• "minimize the maximum", "maximize the minimum", "smallest value satisfying a condition" → Binary Search on the answer (parametric search) over the value range with a monotonic feasible(x) predicate.

4. Words about lookup, counting, and grouping

• "have I seen this before", dedupe, membership while scanning → HashSet (Hashing).
• "most frequent", "appears k times", "anagram", "can A be built from B", "make equal / common characters" → HashMap of element→count, or a int[26] when the domain is bounded (Hashing / Advanced Patterns / Company Practice).
• "group items sharing a property" → build a signature key (sorted string or 26-count tuple), map key→list (Hashing).
• each input is an interval and you want the point of maximum overlap → difference array / line sweep (+1 at start, −1 just past end), not a per-point tally (Advanced Patterns).

5. Words about prefixes and strings of strings

• "starts with", "common prefix", "autocomplete", "suggest as user types", or many words with shared stems → Trie. A hash set gives exact match but cannot answer "starts-with"; a Trie searches in O(L) regardless of dictionary size.
• "search with . matching any char" / wildcard match → Trie with branching at the wildcard.

6. Words about LIFO / FIFO ordering

• "most recent / last seen / undo / reverse", matching nested pairs (parentheses, brackets, tags), expression evaluation (postfix/RPN), path normalization → Stack (LIFO). Push openers, pop on closers and check the match.
• "process in arrival order", "first come first served", "oldest first" → Queue (FIFO).
• "shortest path / minimum steps in an unweighted graph or grid", "level by level", flood fill, word-ladder → BFS with a Queue (highest-frequency queue pattern).
• "max/min of every length-k window" → monotonic deque (Queues), not a heap.

7. Words about "top K" and K sorted sources

• "top K", "K largest/smallest", "K-th largest" → Heap of size K. For K largest, keep a min-heap of size K and pop the root when size exceeds K. O(n log K), beats full sort when K ≪ n.
• "merge K sorted lists/arrays", "smallest range across K lists", "K-th smallest in a sorted matrix" → K-way merge with a min-heap holding one frontier element per source.

8. Words about hierarchy and relationships

• "hierarchical, one root, no cycles" (file system, org chart, expression) → Tree. "Answer at a node depends on its subtrees" (height, diameter, subtree sums, validation) → DFS bottom-up. "Process level by level" → BFS.
• "connected", "depends on / prerequisite", "reachable", "network", pairwise relationships → Graph (vertices + edges). A 2D grid asking about reachability/distance/flood-fill (rotting oranges, walls/gates) is a graph in disguise: cell = node, 4/8 neighbors = edges. Shortest path in an unweighted graph → BFS.

9. Words about a 2D grid you transform

• grid[m][n], board, or image to traverse/transform/aggregate → Matrix iteration with explicit (row, col) indexing.
• n x n + "in place / O(1) extra" (Rotate Image, Set Matrix Zeroes) → index-swap tricks: layer-by-layer rotation, transpose-then-reverse, or row0/col0 as marker storage.
• "spiral / boundary order" → four shrinking pointers (top/bottom/left/right).

10. Words about relinking nodes

• "reverse / reorder a sublist in place" (reverse whole list, swap adjacent pairs, reverse m..n, reverse in k-groups) → Linked List pointer relinking — rewire next, never copy values.
• "split / regroup by structure then re-splice" (odd/even by index parity, partition around a pivot) → run multiple building pointers, then join the chains.

11. Words about enumeration and constrained choices

• "find ALL / enumerate every valid", "return every way to...", all permutations/combinations/subsets/partitions → Backtracking. You build a candidate one choice at a time and prune partial candidates that violate a constraint.
• "count the number of ways", "min cost / max sum / can we reach target" over a sequence of choices, especially where greedy fails → Dynamic Programming. Confirm optimal substructure + overlapping subproblems. "Take or skip each item under a capacity/target" → 0/1 Knapsack DP.
• "locally optimal choice never needs to be undone", balance/counter sweep over a string (min add to make parens valid) → Greedy.

12. Words about splitting and self-similarity

• "answer for the full range = combine answers on disjoint sub-ranges", split at mid, or left/right/cross decomposition → Divide & Conquer. Also: "sort without random access" (linked-list merge sort), "count inversions", "k-th element" (quickselect), "merge k sorted things".
• "defined in terms of a smaller copy of itself", tree/nested-structure walks → Recursion. State the recurrence first; the recurrence is the function body.

13. Words about cost and growth (meta-signal)

• "time/space complexity?", "make this faster" → Foundations (asymptotic analysis). Nested loops over the same input ⇒ suspect O(n²); single pass ⇒ O(n); halving each step ⇒ O(log n); O(n) work done log n times ⇒ O(n log n). Recursion ⇒ write a recurrence T(n)=aT(n/b)+f(n) and solve via recursion-tree / Master Theorem.

TRIAGE ORDER (try in this sequence)

1. Read the literal trigger words first. "contiguous" → Sliding Window; "all / every way" → Backtracking; "top K / K-th" → Heap; "starts-with / prefix" → Trie; "most recent / nested pairs" → Stack; "arrival order / level by level" → Queue/BFS. These near-uniquely name the pattern.
2. Check sortedness. Sorted (or sortable) + pair/triplet/target → Two Pointers. Sorted + find/exist → Binary Search. "Minimize the max / maximize the min" → Binary Search on the answer.
3. Check for O(1) lookup or counting needs. Membership/dedupe → HashSet; frequency/anagram/"make equal" → HashMap or int[26]; interval overlap counting → difference array.
4. Identify the structure. grid → Matrix or grid-BFS; relationships/reachability/prerequisites → Graph; hierarchy/one root → Tree; relink-in-place nodes → Linked List.
5. If it is "best/count over a sequence of decisions": try Greedy first (cheaper); if a locally optimal choice can be wrong, fall back to Dynamic Programming (confirm optimal substructure + overlapping subproblems).
6. If you must enumerate every solution: Backtracking (with pruning).
7. If the problem decomposes into sub-ranges/halves: Divide & Conquer / Recursion; write the recurrence.
8. Always sanity-check the complexity against the input size (Foundations): if n is up to ~10⁵–10⁶ you need O(n) or O(n log n), which often rules a pattern in or out before you write any code.