DSA Problem-Solving Guide: When to Use Which Concept
A practical DSA pattern-recognition guide for knowing when to use HashMap, Binary Search, Two Pointers, Sliding Window, Prefix Sum, Stack, BFS, DFS, Greedy, DP, Heap, and Backtracking.
One of the biggest mistakes we make in DSA is trying to memorize solutions instead of recognizing patterns.
You do not need to remember hundreds of problems. You need to look at a problem and ask:
What property of this problem suggests a particular data structure or algorithm?
This guide covers the most common patterns and the clues that tell you when to use them.
1. HashMap / HashSet
When should you think about it?
Use a HashMap (unordered_map) or HashSet (unordered_set) when you need:
- Fast lookup
- Frequency counting
- Checking whether something already exists
- Finding duplicates
- Mapping one value to another
Typical time complexity:
Average: O(1) lookup/insert
Common problem clues
Look for phrases like:
- "find duplicates"
- "frequency of each element"
- "two numbers whose sum is X"
- "have we seen this before?"
- "count occurrences"
unordered_map<int, int> freq;
for (int x : arr) {
freq[x]++;
}Two Sum:
unordered_map<int, int> mp;
for (int i = 0; i < arr.size(); i++) {
int need = target - arr[i];
if (mp.count(need)) {
return {mp[need], i};
}
mp[arr[i]] = i;
}2. Binary Search
Binary search is not only for finding an element in a sorted array.
The bigger pattern is:
Can I repeatedly divide the search space into two halves?
Use it when:
- The array is sorted, or
- The answer has a monotonic property
For example:
False False False True True TrueIf once the condition becomes True, it stays True, binary search may work.
Common clues
- Sorted array
- Minimum possible answer
- Maximum possible answer
- "Find the first/last occurrence"
- "Minimum capacity required"
- "Can we finish within X days?"
- "What is the smallest X such that..."
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}3. Two Pointers
Two pointers usually work when you're dealing with:
- Arrays
- Strings
- Sorted data
- Pairs of elements
- Moving from both ends
Instead of using nested loops O(n²), two pointers can often reduce the problem to O(n).
Example: Two Sum in a Sorted Array
[1, 2, 4, 6, 9]
↑ ↑
left rightIf the sum is too small, move left.
If the sum is too large, move right.
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return {left, right};
if (sum < target)
left++;
else
right--;
}4. Sliding Window
Sliding Window is useful when the problem involves a contiguous subarray or substring.
This is one of the most important patterns in array/string problems.
Look for:
- Longest substring
- Shortest subarray
- Maximum/minimum sum
- At most
K - Exactly
K - Continuous segment
- Subarray / substring
Instead of recalculating every window:
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]we move the window and update the result incrementally.
Fixed-size window
Example:
Find the maximum sum of a subarray of size
k.
int sum = 0;
int ans = INT_MIN;
for (int i = 0; i < arr.size(); i++) {
sum += arr[i];
if (i >= k)
sum -= arr[i - k];
if (i >= k - 1)
ans = max(ans, sum);
}Variable-size window
Example:
Longest substring without repeating characters.
unordered_set<char> seen;
int left = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
while (seen.count(s[right])) {
seen.erase(s[left]);
left++;
}
seen.insert(s[right]);
ans = max(ans, right - left + 1);
}5. Prefix Sum
Prefix Sum is useful when you repeatedly need the sum of a range.
Example:
arr = [2, 4, 1, 3, 5]
prefix = [2, 6, 7, 10, 15]Then:
sum(l...r) = prefix[r] - prefix[l-1]When to use it?
Look for:
- Range sum queries
- Subarray sum
- Repeated sum calculations
- "sum from index L to R"
vector<int> prefix(n);
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}6. Stack
Think about a stack when the problem has a last-in-first-out relationship.
Common examples:
- Balanced parentheses
- Undo operations
- Next Greater Element
- Previous Smaller Element
- Expression evaluation
- Monotonic stack problems
Example: Valid Parentheses
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
}
else {
if (st.empty())
return false;
if ((c == ')' && st.top() != '(') ||
(c == ']' && st.top() != '[') ||
(c == '}' && st.top() != '{')) {
return false;
}
st.pop();
}
}
return st.empty();7. Queue / BFS
Use a queue when you need to process things in the order they arrive.
For graphs and trees, queue + BFS is especially useful when you need:
- Minimum number of steps
- Level-order traversal
- Shortest path in an unweighted graph
- Processing nodes layer by layer
queue<int> q;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int next : graph[node]) {
q.push(next);
}
}8. DFS
DFS is useful when you need to explore an entire branch before coming back.
Common problems:
- Tree traversal
- Graph traversal
- Connected components
- Number of islands
- Backtracking foundations
- Detecting paths/cycles
void dfs(int node, vector<vector<int>>& graph,
vector<bool>& visited) {
visited[node] = true;
for (int next : graph[node]) {
if (!visited[next]) {
dfs(next, graph, visited);
}
}
}9. Greedy
Greedy means:
Make the best-looking choice right now and never reconsider it.
But be careful.
You cannot use greedy simply because it seems faster.
You need a reason that the local optimal choice leads to a global optimal solution.
Common examples:
- Activity selection
- Interval scheduling
- Fractional Knapsack
- Minimum number of platforms
- Some interval problems
If you cannot prove it, don't blindly use greedy.
10. Dynamic Programming
Use DP when the problem has:
- Overlapping subproblems
- Optimal substructure
Usually you can recognize DP from questions like:
- Maximum/minimum possible result
- Number of ways
- Can we achieve X?
- Choose / skip
- Take / not take
- Best answer up to index
i
Example
At every element:
Take it
OR
Skip itThis often suggests a DP state.
vector<int> dp(n);
dp[0] = arr[0];
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i - 1], arr[i]);
}11. Heap / Priority Queue
Use a heap when you repeatedly need:
- Minimum element
- Maximum element
- Top
K - Kth largest/smallest
- Scheduling based on priority
priority_queue<int> maxHeap;
maxHeap.push(10);
maxHeap.push(5);
cout << maxHeap.top();Min heap:
priority_queue<int, vector<int>, greater<int>> minHeap;12. Backtracking
Backtracking is useful when you need to generate all possible choices.
Typical problems:
- Subsets
- Permutations
- Combinations
- N-Queens
- Sudoku
- Generate valid parentheses
Think:
Choose
↓
Explore
↓
Undovoid backtrack(int index, vector<int>& curr) {
if (index == n) {
result.push_back(curr);
return;
}
// Choose
curr.push_back(arr[index]);
backtrack(index + 1, curr);
// Undo
curr.pop_back();
// Skip
backtrack(index + 1, curr);
}13. Sorting + Another Pattern
A surprisingly useful technique is:
Sort first, then apply another algorithm.
Sorting can make these patterns possible:
Sorting + Two Pointers
Sorting + Greedy
Sorting + Binary Search
Sorting + IntervalsFor example:
Unsorted → difficult
Sorted → structure appearsThe Most Important Pattern Recognition Cheat Sheet
| Problem clue | Think about |
|---|---|
| Fast lookup | HashMap / HashSet |
| Frequency counting | HashMap |
| Duplicate detection | HashSet |
| Sorted array | Binary Search / Two Pointers |
| Divide search space | Binary Search |
| Contiguous subarray/substring | Sliding Window |
| Many range sums | Prefix Sum |
| Pair from sorted array | Two Pointers |
| Next Greater/Smaller | Stack |
| Balanced brackets | Stack |
| Minimum steps | BFS |
| Explore connected components | DFS |
| Top K / Kth largest | Heap |
| Every possible combination | Backtracking |
| Best possible answer with repeated states | DP |
| Local optimal choice can be proven safe | Greedy |
| Intervals | Sort + Greedy / Two Pointers |
| Repeated min/max extraction | Heap |
A Better Way to Think During an Interview
Don't start coding immediately.
Use this sequence:
Step 1 — Understand the input
Ask:
Array?
String?
Tree?
Graph?
Matrix?Step 2 — Look for constraints
Constraints often tell you the expected complexity.
For example:
n <= 20Brute force may work.
n <= 10^5O(n²) is probably too slow.
Step 3 — Look for keywords
Ask:
Sorted?
Contiguous?
Frequency?
Pair?
Shortest path?
Top K?
All possibilities?
Maximum/minimum?Step 4 — Identify the pattern
Examples:
Contiguous + longest
→ Sliding Window
Sorted + pair
→ Two Pointers
Fast lookup
→ HashMap
Sorted + search
→ Binary Search
Shortest path + unweighted graph
→ BFS
All possible choices
→ Backtracking
Repeated subproblems
→ DPStep 5 — Estimate complexity
Before coding, ask:
Can I do O(n)?
O(n log n)?
O(n²)?Don't write an algorithm without knowing why its complexity is acceptable.
Final Mental Model
You can remember DSA patterns like this:
FAST LOOKUP
↓
HashMap / HashSet
SORTED DATA
↓
Binary Search / Two Pointers
CONTIGUOUS RANGE
↓
Sliding Window / Prefix Sum
LIFO RELATIONSHIP
↓
Stack
FIFO / MINIMUM STEPS
↓
Queue / BFS
EXPLORE EVERYTHING
↓
DFS
TOP K / MIN-MAX
↓
Heap
ALL POSSIBILITIES
↓
Backtracking
REPEATED SUBPROBLEMS
↓
Dynamic Programming
LOCAL BEST CHOICE
↓
GreedyThe goal is not to memorize this table.
The goal is to reach a point where you read a new problem and naturally think:
"What structure is hidden in this problem?"
That is the real DSA skill.