DEV Community

Dev Cookies
Dev Cookies

Posted on

🧠 How to Identify Which DSA Approach Solves Which Problem

A guide to matching problems with techniques like Recursion, DP, Greedy, Backtracking, Heap, Graphs & more

📝 Introduction

In DSA (Data Structures & Algorithms), knowing which technique to apply is often more important than knowing how to implement it. This blog provides a pattern-matching guide that helps you choose the right approach when solving problems.

🔧 Common DSA Techniques at a Glance

Technique Use When You See Problems With...
Recursion Divide-and-conquer, tree/graph traversal, combinations
Backtracking All combinations/permutations, constraints, paths
Dynamic Programming (DP) Optimal substructure, overlapping subproblems
Greedy Local choices → global optimum, sorting & selection
Heap (Priority Queue) k-largest/smallest, scheduling, streaming
Graph Algorithms Connectivity, shortest path, cycles, components
Sliding Window Contiguous subarrays, fixed/moving window
Two Pointers Sorted arrays, pairs/triplets, palindromes
Binary Search Sorted data, search in range/array/matrix
Hashing Fast lookup, frequency count, duplicates
Stack/Queue Parentheses, spans, previous/next greater, BFS

🔁 1. Recursion

✅ When to Use:

  • The problem can be broken into smaller subproblems of the same type
  • Tree/graph traversal
  • Combinations/subsets/permutations

🧠 Identify By:

  • “Return all combinations”
  • “Explore all paths”
  • “Generate all permutations/subsets”
  • Problem involves depth

💡 Examples:

  • Tree Traversals (Pre/In/Post Order)
  • Generate all subsets → Power Set
  • Factorial, Fibonacci (naive)
  • Maze path finding (without memory)

🎯 2. Backtracking

✅ When to Use:

  • You need to explore all configurations with constraints
  • Problems mention "find all valid permutations/combinations"
  • You need to undo decisions (i.e., backtrack)

🧠 Identify By:

  • “Find all solutions” with some pruning
  • “If solution found, backtrack”
  • "Constraints on element placement"

💡 Examples:

  • N-Queens
  • Sudoku Solver
  • Word Search in Grid
  • Combination Sum
  • Palindrome Partitioning

💰 3. Dynamic Programming (DP)

✅ When to Use:

  • Optimal substructure (can break into subproblems)
  • Overlapping subproblems (same subproblem appears multiple times)

🧠 Identify By:

  • “Find the maximum/minimum/longest/shortest…”
  • Recursive solution exists but is inefficient
  • Subproblems with multiple choices

💡 Examples:

  • 0/1 Knapsack
  • Longest Common Subsequence (LCS)
  • Longest Increasing Subsequence (LIS)
  • Coin Change, Climbing Stairs
  • Edit Distance

⚡️ 4. Greedy

✅ When to Use:

  • You can make a locally optimal choice and it leads to global optimum
  • Sorting + picking strategy
  • No need for “backtracking” or “memoization”

🧠 Identify By:

  • “Find minimum number of …”
  • "Choose best available option at each step"
  • Activity selection, intervals, coin problems

💡 Examples:

  • Activity Selection
  • Huffman Encoding
  • Fractional Knapsack
  • Jump Game
  • Gas Station

🧮 5. Heap (Priority Queue)

✅ When to Use:

  • You need quick access to largest/smallest element
  • "k-th largest/smallest", "real-time ranking", "merge sorted arrays"

🧠 Identify By:

  • “K largest/smallest elements”
  • “Real-time selection”
  • “Efficient sorting with top elements”

💡 Examples:

  • Merge K Sorted Lists
  • Top K Frequent Elements
  • Median in Data Stream
  • Dijkstra’s Algorithm

🌉 6. Graph Algorithms

✅ When to Use:

  • Problems mention nodes, edges, paths, connections
  • Need to find shortest path, cycles, or connected components

🧠 Identify By:

  • “Find if X is connected to Y”
  • “Find shortest path”
  • “Detect cycle”
  • “Components in a graph”

💡 Examples:

  • BFS/DFS
  • Dijkstra / Bellman-Ford
  • Topological Sorting
  • Union-Find (DSU)
  • Number of Islands

🚪 7. Sliding Window

✅ When to Use:

  • Contiguous subarrays with fixed or variable size
  • Optimizing sum/count over subarray

🧠 Identify By:

  • “Find max/min/average/count of subarray of length k”
  • “Longest/shortest subarray with constraint”

💡 Examples:

  • Max Sum Subarray of size K
  • Longest Substring Without Repeating Characters
  • Minimum Window Substring
  • Permutation in String

🧍 8. Two Pointers

✅ When to Use:

  • Sorted arrays or strings
  • Need to move inwards or compare two ends
  • Finding pairs/triplets/duplicates

🧠 Identify By:

  • “Find if there’s a pair with sum X”
  • “Check if array is a palindrome”
  • “Remove duplicates in-place”

💡 Examples:

  • Two Sum (Sorted)
  • 3Sum
  • Container With Most Water
  • Reverse Words in String

🔍 9. Binary Search

✅ When to Use:

  • Problem involves sorted array or search space
  • Need to find first/last/any occurrence
  • Answer lies in a range

🧠 Identify By:

  • “Find minimum/maximum such that…”
  • “Is this value possible?”
  • Monotonic property exists

💡 Examples:

  • Search in Rotated Sorted Array
  • Median of Two Sorted Arrays
  • Koko Eating Bananas
  • Find Peak Element

⚖️ 10. Hashing

✅ When to Use:

  • Fast lookup, frequency count
  • Detect duplicates
  • Count/map/group elements

🔥 Extended DSA Patterns – And When to Use Them

Let’s cover 15+ more patterns, how to identify them, what problems they solve, and which approach to use.

🔁 1. Matrix Traversal Pattern

✅ When:

  • Input is a 2D grid or matrix
  • Movement is in directions (up, down, left, right, diagonal)

🧠 Keywords:

  • “Find islands”, “Count regions”, “Path in grid”

🧰 Approach:

  • DFS / BFS / Union-Find / DP / Backtracking

🔍 Problems:

  • Number of Islands
  • Word Search
  • Flood Fill
  • Shortest Path in Maze

🧊 2. Monotonic Stack / Queue

✅ When:

  • You need to maintain increasing/decreasing order
  • Looking for "next greater", "next smaller", etc.

🧠 Keywords:

  • “Next greater element”, “Stock span”, “Histogram”

🧰 Approach:

  • Stack with condition checks

🔍 Problems:

  • Largest Rectangle in Histogram
  • Daily Temperatures
  • Trapping Rain Water

🧊 3. Bit Manipulation Pattern

✅ When:

  • Constraints are very tight (n ≤ 10^6)
  • Involves toggling states, sets, subsets efficiently

🧠 Keywords:

  • “Find unique element”, “Check/set/unset bit”, “Subsets of N elements”

🧰 Approach:

  • AND, OR, XOR, SHIFT operators

🔍 Problems:

  • Subsets using bits
  • Single Number (XOR)
  • Count Set Bits

🧬 4. Union-Find / Disjoint Set Union (DSU)

✅ When:

  • Dynamic connectivity among nodes
  • Grouping components or detecting cycles in undirected graph

🧠 Keywords:

  • “Find connected components”
  • “Merge sets”

🧰 Approach:

  • Union by Rank + Path Compression

🔍 Problems:

  • Accounts Merge
  • Number of Connected Components
  • Detect Cycle in Graph

🔃 5. Topological Sorting (Graph + DFS)

✅ When:

  • Directed Acyclic Graph (DAG)
  • Task/Job Scheduling

🧠 Keywords:

  • “Order of tasks”, “Prerequisites”, “Dependencies”

🧰 Approach:

  • DFS-based topo sort
  • Kahn's Algorithm (BFS with in-degree)

🔍 Problems:

  • Course Schedule
  • Alien Dictionary
  • Task Scheduling

🕹 6. Trie-Based Pattern (Prefix Tree)

✅ When:

  • Involves prefixes, autocomplete, dictionary lookups

🧠 Keywords:

  • “Starts with”, “Prefix match”, “Search word”

🧰 Approach:

  • Implement Trie Node class

🔍 Problems:

  • Word Dictionary
  • Replace Words
  • Maximum XOR of two numbers

🏦 7. Interval Merging & Scheduling

✅ When:

  • Intervals, ranges, meetings, overlaps
  • Merge, insert, or schedule intervals

🧠 Keywords:

  • “Merge intervals”, “Max overlapping”, “Min rooms required”

🧰 Approach:

  • Sort + Greedy + Heap (often)

🔍 Problems:

  • Merge Intervals
  • Meeting Rooms I & II
  • Minimum Number of Arrows

🪤 8. Two Heaps (Min + Max Heap)

✅ When:

  • Need median or balance two sides dynamically

🧠 Keywords:

  • “Running median”, “Balance left & right sides”

🧰 Approach:

  • Maintain two heaps: max-left, min-right

🔍 Problems:

  • Median of Data Stream
  • Sliding Window Median

🛤 9. Prefix Sum / Difference Array

✅ When:

  • Sum/range queries on array or matrix
  • Multiple updates/queries efficiently

🧠 Keywords:

  • “Sum of subarray”, “Multiple queries”

🧰 Approach:

  • Prefix sum array
  • 2D prefix sum
  • Difference array for range update

🔍 Problems:

  • Subarray Sum Equals K
  • Range Sum Query
  • Matrix Block Sum

🎯 10. Kadane’s Algorithm (Max Subarray Sum)

✅ When:

  • Find largest sum in contiguous subarray

🧠 Keywords:

  • “Maximum sum”, “Contiguous subarray”

🧰 Approach:

  • Dynamic scan, keep current and global max

🔍 Problems:

  • Maximum Subarray (Leetcode 53)
  • Circular Subarray Sum
  • Maximum Product Subarray

🧭 11. Meet in the Middle

✅ When:

  • Constraints are high (N ≤ 40)
  • Too large for brute force, but small enough for half & merge

🧠 Keywords:

  • “Find all subset sums”

🧰 Approach:

  • Split array in half, compute all subset sums, binary search or hash for pairs

🔍 Problems:

  • Subset Sum Problem
  • Count of subsets with given sum

📐 12. Mathematical Patterns

✅ When:

  • Modulo, primes, combinatorics, number theory

🧠 Keywords:

  • “Find GCD/LCM”, “Divisible by X”, “Count primes”

🧰 Approach:

  • Euclid’s GCD, Sieve of Eratosthenes, Fermat’s Little Theorem

🔍 Problems:

  • GCD of Array
  • Count Primes
  • Modular Exponentiation

🪟 13. Difference Between “All Paths” vs “Any Path”

🧠 Rule of Thumb:

  • All valid paths → Backtracking
  • Any valid path → DFS or BFS
  • Shortest path → BFS (Unweighted) or Dijkstra (Weighted)

🧠 Ultimate Strategy – DSA Pattern Recognition Flow

  1. Input Structure?
  • Array → use Sliding Window, Two Pointers, Prefix Sum
  • Grid → Matrix Traversal, DFS/BFS
  • Tree → Recursion, DFS, BFS
  • Graph → BFS, DFS, Union-Find, Dijkstra
  1. Goal Type?
  • Count, Min/Max, Length → DP or Greedy
  • All combinations → Backtracking
  • Order of tasks → Topological Sort
  • Real-time ranking → Heap
  • Range sum/query → Prefix Sum / Segment Tree
  1. Constraints Check?
  • Small N (<15) → Brute-force or Backtracking
  • Large N (10^5+) → Optimized DP, Hashing, Binary Search

🧠 Identify By:

  • “Return true if... exists in array”
  • “Find duplicate/unique elements”
  • “Group similar elements”

💡 Examples:

  • Two Sum (Unsorted)
  • Longest Consecutive Sequence
  • Group Anagrams
  • Subarray Sum Equals K

📚 Summary Table

Problem Keyword Approach
All combinations/permutations Recursion, Backtracking
Constraints and Valid Configs Backtracking
Maximum/Minimum/Count/Length DP, Greedy
Sorted Input / Search Space Binary Search, Two Pointers
Shortest Path / Connectivity Graph (BFS/DFS/Dijkstra)
K-th element or real-time data Heap, Binary Search
Contiguous Subarray Sliding Window
Duplicates / Frequency Hashing
Tree/Graph Traversal Recursion, DFS/BFS

🎯 Final Tips

  • Try brute force first — then optimize.
  • Ask: Does the problem require all solutions or just the best?
  • Ask: Are there overlapping subproblems?
  • Learn to translate problem statements into patterns.
  • Practice pattern recognition via LeetCode Tags.

🔗 Further Reading

Top comments (0)