DSA PATTERN IDENTIFICATION GUIDE Page 1

DSA Pattern
Identification Guide
Spot the right data structure · every time

Identifying the correct data structure for a problem is a learnable skill, not guesswork. This guide gives you
two angles of attack: reading the problem statement for trigger words, and recognising the shape of a
brute-force solution. Master the patterns here and the right approach will click instantly during interviews.

Two Pointer Sliding Window HashMap Binary Search Stack Linked List Tree Backtracking

Divide & Conquer Graph Heap Trie Dynamic Programming Greedy Sorting

■ Learn each data structure deeply before relying on these patterns.

1 Two Pointer

◆ CORE RULE
Sorted Array + pair/triplet + sum/target → Two Pointer (← →)

Trigger Pattern Pointer Direction

Sorted array + pair/triplet + sum/target ← → (opposite ends)

Sorted array + reverse / palindrome / compare both ends ← → (opposite ends)

Sorted array + duplicate removal / in-place modify → → (same direction)

Two sorted arrays + merge / intersect / common elements → → (same direction)

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 2

2 Sliding Window

◆ CORE RULE
Contiguous subarray/substring + count/max/min/avg → Sliding Window

Trigger Technique

Only max subarray sum, no window constraint Kadane's Algorithm

Fixed size window k given Sliding Window — Fixed

Condition given (≤ k, ≥ k, unique, distinct …) Sliding Window — Variable

Exact sum = k (including negatives) Prefix Sum + HashMap

Array Patterns — Decision Tree

Subarray / substring (contiguous)?
YES → Max subarray only? → Kadane's
YES → Fixed size k? → Sliding Window Fixed
YES → Condition (≤k, distinct…)? → Sliding Window Variable
YES → Exact sum = k? → Prefix Sum + HashMap
NO → Pair/triplet + sum? → Sorted? → Two Pointer | Unsorted? → HashMap
NO → Both-end compare? → Two Pointer ← →
NO → In-place modify? → Two Pointer → →
NO → Two arrays? → Two Pointer → →
NO → Otherwise → Stack / DP / Binary Search

3 HashMap

◆ CORE RULE
Unsorted + pair + sum → HashMap | Sorted + pair + sum → Two Pointer

Situation Use

Count / frequency / occurrences HashMap

Fast lookup O(1) — does X exist? HashMap

Duplicate / unique / distinct check HashMap

Replace O(n²) nested loop with O(n) HashMap

Subarray + exact sum = k Prefix Sum + HashMap

Grouping problems (anagrams, etc.) HashMap

Unsorted + pair complement — seen target−X? HashMap

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 3

4 Searching

◆ CORE RULE
Search space sorted OR monotonically reducible → Binary Search

Trigger Technique

Sorted array + find / index / target Binary Search (classic)

Answer in numeric range + isValid() check Binary Search on Answer

Unsorted but structured (peak/rotated sorted) Binary Search

First/last occurrence, sorted matrix Binary Search

Min/max satisfying a monotonic condition Binary Search on Answer

Linked list / no random access Linear Search

Unsorted, no special structure Linear Search

5 Stack

◆ CORE RULE
Order matters + need nearest / previous / next → Stack

Keyword Triggers
• Next / Previous / Nearest + Greater / Smaller → Monotonic Stack
• Balanced parentheses / pair matching → Stack
• Expression evaluation (infix / prefix / postfix) → Stack
• Largest rectangle / area under histogram → Monotonic Stack
• Undo / back / reverse-order operations → Stack
• Span / range problems (Stock Span, Daily Temperatures) → Monotonic Stack

Brute-Force Signal — Nested Loop Patterns

Brute-Force Pattern Stack Variant

Inner loop runs 0 → i Next Smaller Element (Left)

Inner loop runs i → 0 Next Greater Element (Left)

Inner loop runs i → n Next Greater Element (Right)

Inner loop runs n → i Next Smaller Element (Right)

6 Linked List

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 4

Trigger Technique

Reverse — full / k-group / in-place Linked List

Cycle detection / loop Fast-Slow Pointer

Find middle / nth from end Fast-Slow Pointer

Navigation back & forward / Undo-Redo Doubly Linked List

Merge sorted sequences / streams Linked List

Design LRU cache / browser history Linked List + HashMap

Array with frequent insert / delete / shift Linked List

◆ CORE RULE
Array + frequent insert/delete/shift → Linked List

7 Tree

◆ CORE RULE
Path / depth / subtree / recursion → DFS | Level / distance / nearest → BFS

DFS TRIGGERS BFS TRIGGERS

• Height / depth / diameter • Level-order traversal

• Root-to-leaf path / path sum • Zigzag / left-side / right-side view

• Subtree match / subtree sum • K-distance from node / nearest node

• LCA / ancestor tracking • Minimum depth

• Inorder / preorder / postorder • Connect next-right pointers

8 Backtracking

◆ CORE RULE
Try all possibilities + undo choices → Backtracking

Trigger Pattern

Generate all combinations / subsets Backtracking

Generate all permutations Backtracking

"All possible ways" / "print all" Backtracking

Decision at each step (pick/not pick) + ALL answers Backtracking

Constraint + validation (N-Queens, Sudoku, Word Search) Backtracking

High-Level Decision Guide

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 5

TRIGGER PATTERN

All subsets / permutations Backtracking

Count / max / min (optimisation only) DP / Greedy

Does a path exist? (single path) DFS / BFS

All paths Backtracking

9 Divide & Conquer

◆ CORE RULE
Divide → Solve → Combine → D&C | Overlapping subproblems → DP instead

Trigger Pattern

Split into left / right halves Divide & Conquer

Solve subproblems independently, combine results Divide & Conquer

Recursion on independent parts, no shared work Divide & Conquer

Sorting / searching / inversion-type problems Divide & Conquer

10 Graph

◆ CORE RULE
Connected components/reachable → BFS/DFS | Shortest unweighted → BFS | Dependencies → Topo Sort

Trigger Algorithm

Grid + connected components / count reachable BFS / DFS

Grid + shortest path, unweighted BFS

Grid + shortest path, weighted non-negative Dijkstra

Grid + minimum steps / moves BFS

Grid + all paths DFS

Grid + island counting / flood fill DFS

Cycle detection — undirected DFS / Union Find

Cycle detection — directed DFS / Topological Sort

Prerequisites / task scheduling / build order Topological Sort

Dynamically connecting components Union Find

Are X and Y connected? Union Find

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 6

11 Heap

◆ CORE RULE
Heap = smart selection (not full sorting). Need top-k / best? → Heap

Trigger Heap Type

Top K / Kth element Heap

Best element repeatedly (min or max) Heap

Priority queue / scheduling Heap (= Priority Queue)

Stream + maintain top-k elements Heap

Merge k sorted lists / arrays Min Heap

Median of a stream / running median Two Heaps (Min + Max)

Do NOT use Heap when …

✗ Need a fully sorted array → use sorting
✗ Need exact lookup → HashMap
✗ Need a range or window → Sliding Window

12 Trie

◆ CORE RULE
Prefix-based search / matching on strings → Trie

Trigger Pattern

Prefix queries / search / autocomplete Trie

Pattern matching with wildcards Trie

Dictionary-based lookup / replacement Trie

Search multiple words on same grid Trie + DFS

"Starts with" / count words with prefix Trie

Longest common prefix Trie (sorting also works)

Exact word lookup only HashMap

Single string search Sliding Window / KMP

13 Dynamic Programming

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 7

◆ CORE RULE
Overlapping subproblems + optimal substructure → DP | Need ALL answers → Backtracking

Two-Step Identification
Step 1 — Can the problem be defined by a STATE? NO → not DP. YES → Step 2.
Step 2 — Does the same STATE recur? NO → Divide & Conquer. YES → DP ✓

State Definition DP Type Classic Problems

Single index i Linear DP LIS, house robber, climbing stairs

(index, capacity/constraint) Knapsack DP 0/1 knapsack, coin change

Range (left, right) Interval DP Matrix chain, burst balloons

(row, col) grid coords Grid DP Unique paths, dungeon game

Tree node Tree DP Max path sum, diameter

Bitmask of choices Bitmask DP TSP, visit all nodes

Two sequences (i, j) String DP LCS, edit distance

DP vs Backtracking vs D&C;
TRIGGER PATTERN

Count / max / min / is-it-possible DP

All answers / print all combinations Backtracking

Independent subproblems, no overlap Divide & Conquer

Overlapping subproblems DP

Pick / not pick + ALL answers Backtracking

Pick / not pick + count / max / min DP (Knapsack)

14 Greedy

◆ CORE RULE
Locally best choice at each step, never undone → Greedy (else DP)

Trigger Pattern

Minimum coins / jumps / intervals (standard greedy works) Greedy

Activity selection / interval scheduling Greedy

Maximum events / tasks you can attend Greedy

Huffman coding / minimum cost tree Greedy

Always pick largest / smallest first Greedy

Job scheduling with deadlines Greedy

Minimum platforms / meeting rooms needed Greedy

Learn the pattern · Spot the signal · Code the solution

DSA PATTERN IDENTIFICATION GUIDE Page 8

Brute-force signal: Sort + pick best option at each step → Greedy

15 Sorting

Algorithm Use When Classic Example

Bubble Sort ■ Avoid —

Selection Sort ■ Avoid —

Insertion Sort Almost sorted / very small (n ≤ 20) Nearly ordered data

Merge Sort Stable sort + inversions + linked-list sort Stable, linked lists

Quick Sort General purpose, in-place, avg case Most arrays

Heap Sort In-place + worst case O(n log n) guarantee Memory-limited

Counting Sort Integers in small known range 0…k Digit frequencies

Radix Sort Large integers / fixed-digit numbers Phone numbers

Bucket Sort Uniformly distributed floats Normalised scores

One-line memory aid

■ Small / almost sorted → Insertion Sort
■ General purpose → Quick Sort
■ Stable / linked list / inversions → Merge Sort
■ Integer range known → Counting Sort or Radix Sort
■ Worst-case guarantee needed → Merge Sort

1. These patterns cover ~95% of interview problems. Exceptions exist but are rare.
2. Always master the underlying data structure before applying identification shortcuts.
3. When two patterns seem valid, consider time / space constraints to break the tie.

Happy Coding ■

Learn the pattern · Spot the signal · Code the solution