Skip to content
Ashish's Engineering Lab
16 min readPerformance

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:

  1. The array is sorted, or
  2. The answer has a monotonic property

For example:

False False False True True True

If 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        right

If 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:

  1. Overlapping subproblems
  2. 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 it

This 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
↓
Undo
void 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 + Intervals

For example:

Unsorted → difficult
Sorted   → structure appears

The Most Important Pattern Recognition Cheat Sheet

Problem clueThink about
Fast lookupHashMap / HashSet
Frequency countingHashMap
Duplicate detectionHashSet
Sorted arrayBinary Search / Two Pointers
Divide search spaceBinary Search
Contiguous subarray/substringSliding Window
Many range sumsPrefix Sum
Pair from sorted arrayTwo Pointers
Next Greater/SmallerStack
Balanced bracketsStack
Minimum stepsBFS
Explore connected componentsDFS
Top K / Kth largestHeap
Every possible combinationBacktracking
Best possible answer with repeated statesDP
Local optimal choice can be proven safeGreedy
IntervalsSort + Greedy / Two Pointers
Repeated min/max extractionHeap

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 <= 20

Brute force may work.

n <= 10^5

O(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
→ DP

Step 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
    ↓
Greedy

The 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.


Keep Reading