DSA Pattern Recognition

🧠 Complete DSA Pattern Recognition Lesson

How to Identify the Right Approach (End-to-End Guide)

🎯 Lesson Objective

By the end of this lesson, you will be able to:

• Read a DSA problem and quickly identify its underlying pattern
• Map keywords → data structures → algorithms
• Eliminate brute force by instinctively choosing the right approach
• Explain why a solution works (not just code it)

This is the difference between knowing syntax and thinking like an engineer.

🔑 The Core Truth About DSA

Almost every DSA problem is a remix.

The hard part is not coding — it’s recognizing the pattern fast enough.

There are ~12–15 core patterns that appear over and over.
Once you can recognize them, most problems become straightforward.

🧭 How to Use This Lesson

For every problem, ask yourself:

1. What keywords stand out?
2. Is the data contiguous, sorted, or relational?
3. Am I optimizing, counting, searching, or generating?
4. Is the problem asking for one answer or all answers?

1️⃣ Arrays & Strings

🔑 Keywords

• subarray
• substring
• contiguous
• range
• window
• longest / shortest

🧠 What This Signals

• Sliding Window
• Two Pointers
• Prefix Sum

🛠 Typical Tools

• Index pointers
• Frequency hash
• Running sum

✅ Example

“Find the longest substring without repeating characters”

→ Sliding Window + Hash Map

2️⃣ Sliding Window (Very High Frequency)

🔑 Keywords

• longest / shortest
• at most k
• at least k
• contains all
• without repeating

🧠 Recognition Rule

If the problem asks for:

A contiguous segment + a condition

→ Sliding Window

🛠 Core Logic

1. Expand window (right)
2. Update state (counts, sum, etc.)
3. If invalid → shrink window (left)
4. Track best result

3️⃣ Two Pointers

🔑 Keywords

• sorted array
• pair
• triplet
• palindrome
• remove duplicates

🧠 Recognition Rule

If:

• The array is sorted
• You compare elements from both ends

→ Two Pointers

🛠 Pointer Patterns

• Opposite direction (left, right)
• Same direction (slow / fast)

4️⃣ Hash Map / Hash Set

🔑 Keywords

• frequency
• count
• duplicate
• unique
• seen before

🧠 Recognition Rule

If you need:

Fast lookup or counting

→ Hash Map / Hash Set

🛠 Often Combined With

• Sliding Window
• Prefix Sum
• Graph traversal

5️⃣ Prefix Sum

🔑 Keywords

• subarray sum
• range sum
• cumulative
• equals k

🧠 Recognition Rule

If the problem involves:

Multiple overlapping sum queries

→ Prefix Sum

🛠 Core Idea

Store running totals so range queries are O(1).

6️⃣ Stack

🔑 Keywords

• valid parentheses
• balanced
• next greater element
• previous smaller

🧠 Recognition Rule

If elements need:

Matching, undoing, or nearest comparison

→ Stack

🛠 Variants

• Monotonic Stack
• Expression evaluation

7️⃣ Queue / Deque

🔑 Keywords

• level order
• sliding window maximum
• stream
• first unique

🧠 Recognition Rule

If items are processed:

In the order they arrive

→ Queue / Deque

8️⃣ Heap / Priority Queue

🔑 Keywords

• top k
• k largest / k smallest
• most frequent
• closest
• merge k

🧠 Recognition Rule

If you need:

The best / worst element repeatedly

→ Heap

🛠 Common Uses

• Scheduling
• Streaming data
• Greedy optimizations

9️⃣ Binary Search

🔑 Keywords

• sorted
• search
• first / last occurrence
• minimum possible
• maximum possible

🧠 Recognition Rule

If:

• Input is sorted or
• The answer exists in a numeric range

→ Binary Search

🛠 Advanced Variant

Binary Search on Answer

Used when you search for the best feasible value.

🔟 Trees

🔑 Keywords

• binary tree
• depth
• height
• path
• ancestor
• BST

🧠 Recognition Rule

Tree problems almost always mean:

• DFS (recursion)
• BFS (level order)

1️⃣1️⃣ Graphs

🔑 Keywords

• connected
• path exists
• cycle
• islands
• dependencies

🧠 Recognition Rule

If the problem describes:

Relationships or networks

→ Graph

🛠 Techniques

• BFS / DFS
• Topological Sort
• Union Find

1️⃣2️⃣ Union Find (Disjoint Set)

🔑 Keywords

• connected components
• merge
• dynamic connectivity
• cycle detection

🧠 Recognition Rule

If you’re merging groups dynamically:
→ Union Find

1️⃣3️⃣ Dynamic Programming (DP)

🔑 Keywords

• maximum / minimum
• count ways
• optimal
• choices
• overlapping subproblems

🧠 Recognition Rule

If the problem:

• Has repeated subproblems
• Requires an optimal result

→ DP

1️⃣4️⃣ Greedy

🔑 Keywords

• minimum operations
• maximize profit
• earliest / latest
• best local choice

🧠 Recognition Rule

If a local optimal choice leads to a global solution:
→ Greedy

1️⃣5️⃣ Backtracking

🔑 Keywords

• all combinations
• all permutations
• generate
• explore

🧠 Recognition Rule

If the problem asks for:

All possible solutions

→ Backtracking

1️⃣6️⃣ Bit Manipulation (Bonus)

🔑 Keywords

• xor
• single number
• power of two
• bitmask

🧠 Recognition Rule

If the problem hints at binary logic:
→ Bit Manipulation

🚀 Final Interview Checklist

Ask yourself:

1. Is it contiguous? → Sliding Window
2. Is it sorted? → Binary Search / Two Pointers
3. Do I need fast lookup? → Hash Map
4. Am I choosing the best k items? → Heap
5. Is it all possibilities? → Backtracking / DP
6. Are there relationships? → Graph / Union Find

🧠 Final Thought

You don’t master DSA by memorizing solutions.

You master it by recognizing patterns instantly.

Once pattern recognition clicks,

the code becomes the easy part.