How to IDENTIFY Which DSA Pattern to Use In Question || Pattern + Templates + keywords

3920

Dynamic Programming Career Feedback DSA Interview DSA Resources

How to IDENTIFY Which DSA Pattern to Use — Decision Guide + C++ Templates (Read This Before Grinding More Problems)

Stop memorizing solutions. Start recognizing patterns.
This guide answers the one question nobody properly answers: "I see a new problem — how do I know WHICH pattern to apply?"

I've seen hundreds of posts listing DSA patterns. None of them teach you how to recognize which one fits a problem you've never seen. That's the actual skill interviews test. This post fixes that.

📌 The Core Problem With How Most People Study DSA

Most people do this:

See problem → look at tags → learn solution → move on

This is why you blank out on problems you "know." You memorized a solution, not a pattern.

The correct approach:

See problem → read constraints → ask trigger questions → identify pattern → apply template

This post gives you the trigger questions and templates for every major pattern.

🗺️ Master Decision Tree — Read This First

When you open a new problem, ask these questions in order:

Q1. Does the problem involve a CONTIGUOUS subarray or substring?
    └── YES → Sliding Window or Prefix Sum (see Pattern 1 & 2)

Q2. Is the input SORTED (or can I sort it)?
    └── YES + looking for pair/triplet → Two Pointers (Pattern 3)
    └── YES + looking for index/value → Binary Search (Pattern 4)

Q3. Does the problem involve a LINKED LIST?
    └── Detect cycle / find middle → Fast & Slow Pointers (Pattern 5)
    └── Reverse / merge → Standard LL operations (Pattern 6)

Q4. Does the problem involve a TREE or GRAPH?
    └── Level-by-level / shortest path → BFS (Pattern 7)
    └── Explore all paths / connected components → DFS (Pattern 8)
    └── Dependencies / ordering → Topological Sort (Pattern 9)

Q5. Does the problem ask for ALL combinations / subsets / permutations?
    └── → Backtracking (Pattern 10)

Q6. Does the problem ask for OPTIMAL value (min/max/count)?
    └── Overlapping subproblems → DP (Pattern 11)
    └── Greedy choice works → Greedy (Pattern 12)

Q7. Does the problem involve a STACK-shaped structure?
    └── Matching brackets / next greater element → Monotonic Stack (Pattern 13)

Pattern 1 — Sliding Window

🔍 How to identify:

Problem says "subarray", "substring", "window of size k"
You need max/min/count within a contiguous range
O(n²) brute force involves nested loops on same array

🚦 Trigger keywords:

longest, shortest, maximum sum, at most k, exactly k, contiguous

✅ C++ Template — Fixed Window:

int maxSumSubarray(vector<int>& nums, int k) {
    int windowSum = 0, maxSum = 0;
    
    // Build first window
    for (int i = 0; i < k; i++) windowSum += nums[i];
    maxSum = windowSum;
    
    // Slide
    for (int i = k; i < nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

✅ C++ Template — Variable Window:

int longestSubstring(string s, int k) {
    unordered_map<char, int> freq;
    int left = 0, result = 0;
    
    for (int right = 0; right < s.size(); right++) {
        freq[s[right]]++;
        
        // Shrink window when condition violated
        while (/* condition violated */) {
            freq[s[left]]--;
            if (freq[s[left]] == 0) freq.erase(s[left]);
            left++;
        }
        
        result = max(result, right - left + 1);
    }
    return result;
}

📝 Practice problems:

Pattern 2 — Prefix Sum

🔍 How to identify:

Multiple queries on subarray sums
"Subarray sum equals k" type problems
Need cumulative info from index 0 to i

🚦 Trigger keywords:

sum of subarray, range sum query, number of subarrays with sum

✅ C++ Template:

// Build prefix sum
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++)
    prefix[i + 1] = prefix[i] + nums[i];

// Query sum of nums[l..r] in O(1)
int rangeSum = prefix[r + 1] - prefix[l];

// --- Subarray Sum Equals K variant ---
int subarraySumEqualsK(vector<int>& nums, int k) {
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1;
    int sum = 0, count = 0;
    
    for (int num : nums) {
        sum += num;
        count += prefixCount[sum - k];
        prefixCount[sum]++;
    }
    return count;
}

📝 Practice problems:

Pattern 3 — Two Pointers

🔍 How to identify:

Array is sorted (or can be sorted)
Looking for a pair / triplet with target sum
Comparing elements from both ends
In-place partitioning (like Dutch National Flag)

🚦 Trigger keywords:

sorted array, pair with sum, move in-place, two elements

✅ C++ Template — Opposite Direction:

// Classic Two Sum in sorted array
int left = 0, right = nums.size() - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return {left, right};
    else if (sum < target) left++;
    else right--;
}

✅ C++ Template — Same Direction (Fast/Slow):

// Remove duplicates / partition
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
    if (nums[fast] != nums[slow]) {
        slow++;
        nums[slow] = nums[fast];
    }
}

📝 Practice problems:

Pattern 4 — Binary Search

🔍 How to identify:

Input is sorted OR answer space is monotonic (can binary search on the answer)
O(log n) is expected
"Find minimum value that satisfies condition"

🚦 Trigger keywords:

sorted, rotated sorted, find position, minimum/maximum feasible value, kth element

✅ C++ Template — Classic:

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

✅ C++ Template — Binary Search on Answer:

// "Find minimum X such that condition(X) is true"
int left = minPossible, right = maxPossible;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (condition(mid)) right = mid;
    else left = mid + 1;
}
return left;

📝 Practice problems:

#704 Binary Search
#33 Search in Rotated Sorted Array
#153 Find Minimum in Rotated Sorted Array
#875 Koko Eating Bananas ← Binary Search on Answer

Pattern 5 — Fast & Slow Pointers

🔍 How to identify:

Linked list problem involving a cycle
Finding the middle of a linked list
Problem involves two objects moving at different speeds

🚦 Trigger keywords:

cycle, middle, linked list, tortoise and hare

✅ C++ Template:

// Detect cycle
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;  // Cycle detected
}
return false;

// Find middle
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow is now at the middle

📝 Practice problems:

Pattern 6 — BFS (Breadth First Search)

🔍 How to identify:

Shortest path in unweighted graph/grid
Level-by-level traversal of tree
"Minimum steps to reach X"
Multi-source spreading (like rotting oranges)

🚦 Trigger keywords:

shortest path, minimum distance, level order, nearest, minimum steps

✅ C++ Template:

void bfs(int start, vector<vector<int>>& graph) {
    queue<int> q;
    unordered_set<int> visited;
    
    q.push(start);
    visited.insert(start);
    int level = 0;
    
    while (!q.empty()) {
        int size = q.size();  // Process level by level
        for (int i = 0; i < size; i++) {
            int node = q.front(); q.pop();
            // Process node
            for (int neighbor : graph[node]) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
        level++;
    }
}

// Grid BFS Template
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void bfsGrid(vector<vector<int>>& grid, int sr, int sc) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    q.push({sr, sc});
    grid[sr][sc] = 0; // Mark visited
    
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (auto& d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                grid[nr][nc] = 0;
                q.push({nr, nc});
            }
        }
    }
}

📝 Practice problems:

Pattern 7 — DFS (Depth First Search)

🔍 How to identify:

Explore ALL paths (not just shortest)
Connected components in a graph
Tree problems (most of them)
"Count all X that satisfy condition"

🚦 Trigger keywords:

all paths, connected, explore, count, exists a path

✅ C++ Template — Graph DFS:

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    // Process node
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

✅ C++ Template — Tree DFS:

// Most tree problems follow this shape
int dfs(TreeNode* root) {
    if (!root) return 0;  // Base case
    
    int left = dfs(root->left);
    int right = dfs(root->right);
    
    // Combine results
    return 1 + max(left, right);  // Example: max depth
}

📝 Practice problems:

Pattern 8 — Topological Sort

🔍 How to identify:

Problem involves dependencies (do A before B)
Directed Acyclic Graph (DAG)
"Is there a valid ordering?"
Course prerequisites type problems

🚦 Trigger keywords:

prerequisites, ordering, dependency, before, schedule

✅ C++ Template — Kahn's Algorithm (BFS based):

vector<int> topoSort(int n, vector<vector<int>>& edges) {
    vector<int> indegree(n, 0);
    vector<vector<int>> graph(n);
    
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }
    
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);
    
    vector<int> order;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        order.push_back(node);
        for (int neighbor : graph[node]) {
            if (--indegree[neighbor] == 0)
                q.push(neighbor);
        }
    }
    
    return order.size() == n ? order : vector<int>{}; // Empty = cycle exists
}

📝 Practice problems:

Pattern 9 — Backtracking

🔍 How to identify:

Need ALL possible solutions (not just one)
Building combinations / permutations / subsets
Problem has a "constraint" that prunes branches

🚦 Trigger keywords:

all combinations, generate all, permutations, subsets, valid arrangements

✅ C++ Template:

void backtrack(vector<int>& current, vector<vector<int>>& result, 
               vector<int>& nums, int start) {
    // 1. Base case — record result
    result.push_back(current);
    
    for (int i = start; i < nums.size(); i++) {
        // 2. Make a choice
        current.push_back(nums[i]);
        
        // 3. Recurse
        backtrack(current, result, nums, i + 1);
        
        // 4. UNDO the choice (backtrack)
        current.pop_back();
    }
}

💡 Key insight: The only difference between subsets, combinations, and permutations is whether you pass i+1 or 0 in the recursive call, and whether you skip duplicates.

📝 Practice problems:

Pattern 10 — Dynamic Programming

🔍 How to identify:

Problem asks for optimal value (min/max/count/true-false)
Has overlapping subproblems (same subproblem solved multiple times)
Has optimal substructure (optimal solution built from optimal sub-solutions)
Recursive brute force gives TLE

🚦 Trigger keywords:

minimum cost, maximum profit, number of ways, can you reach, longest, fewest

🧪 Quick test: Can you write a recurrence?

If you can define dp[i] in terms of dp[i-1] or dp[j] where j < i → it's DP.

✅ C++ Template — 1D DP:

// General 1D DP (e.g. House Robber)
int dp[n];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

for (int i = 2; i < n; i++)
    dp[i] = max(dp[i-1], dp[i-2] + nums[i]);

return dp[n-1];

✅ C++ Template — 2D DP:

// General 2D DP (e.g. Unique Paths, Edit Distance)
vector<vector<int>> dp(m, vector<int>(n, 0));
// Initialize base cases
dp[0][0] = 1;

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (i > 0) dp[i][j] += dp[i-1][j];
        if (j > 0) dp[i][j] += dp[i][j-1];
    }
}
return dp[m-1][n-1];

📝 Practice problems (in order of difficulty):

Pattern 11 — Monotonic Stack

🔍 How to identify:

"Next greater element" / "Previous smaller element"
Histogram problems
Problems where you need to maintain elements in sorted order as you scan

🚦 Trigger keywords:

next greater, previous smaller, temperatures, histogram, stock span

✅ C++ Template:

// Next Greater Element (Monotonic Decreasing Stack)
vector<int> nextGreater(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st; // stores indices
    
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

📝 Practice problems:

🎯 Quick Reference Cheat Sheet

If you see...	Think...
Contiguous subarray + max/min/count	Sliding Window
Subarray sum = k	Prefix Sum + HashMap
Sorted array + pair/triplet	Two Pointers
Sorted array + find element	Binary Search
"Minimum X such that condition"	Binary Search on Answer
Linked list + cycle	Fast & Slow Pointers
Shortest path / level order	BFS
All paths / connected components	DFS
Dependencies / prerequisites	Topological Sort
All combinations / permutations	Backtracking
Min/Max with overlapping subproblems	Dynamic Programming
Next greater / previous smaller	Monotonic Stack
Matching brackets	Stack
Top K elements	Heap / QuickSelect

⚠️ The 3 Most Common Mistakes

1. Jumping to code without identifying the pattern
Read the problem → identify constraints → ask trigger questions → THEN code.

2. Not knowing when to use BFS vs DFS

Need SHORTEST path? → BFS always
Need to explore ALL paths? → DFS
Both work for connectivity? → DFS is simpler to write

3. Treating DP as magic
DP is just recursion + memoization. Always write the recursive solution first, then add a memo table, then convert to bottom-up.

Recursion (TLE) → Memoization (Top-down DP) → Tabulation (Bottom-up DP)

💡 How to Actually Use This Guide

Open a new problem
Don't look at tags
Run through the Master Decision Tree at the top
Match to a pattern, apply the template structure
Adapt the template to the specific problem
Only check the tag AFTER you've committed to an approach

Do this for 30 problems and pattern recognition becomes automatic.

This post is part of my placement prep journey. If it helped you, drop an upvote — it helps others find it. Open to feedback in the comments.

Comments (2)