Problem Solving
You have now completed the main DSA topics. Problem Solving is where everything comes together.
Knowing arrays, trees, graphs, DP, greedy, etc. is one thing. The real skill is:
Given a new problem, identify the right approach, choose the right data structure/algorithm, prove it works, and implement it efficiently.
1. What Is DSA Problem Solving?
Suppose you receive this problem:
Given an array of integers, find two numbers whose sum is equal to
target.
You could immediately write two loops:
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == target) return true; } }
This works.
But complexity is:
Time = O(n²) Space = O(1)
Now think:
Can I remember numbers I've already seen?
Yes.
Use a hash set:
unordered_set<int> seen; for (int x : arr) { int need = target - x; if (seen.count(need)) return true; seen.insert(x); }
Now:
Average Time = O(n) Space = O(n)
This transition from a working solution to an efficient solution is problem solving.
2. The Problem-Solving Process
A strong DSA problem-solving process looks like this:
PROBLEM ↓ Understand it ↓ Identify input/output ↓ Find constraints ↓ Try a simple solution ↓ Analyze complexity ↓ Find bottleneck / pattern ↓ Choose data structure ↓ Choose algorithm ↓ Implement ↓ Test edge cases ↓ Optimize if needed
Don't jump directly into coding.
3. Step 1 — Understand the Problem
Before writing code, ask:
What is given?
Example:
Array of integers
What do I need to find?
Maximum sum
What are the restrictions?
Can numbers be negative? Can the array be empty? How large can n be?
What should I return?
Maximum sum
This sounds simple, but misunderstanding the problem is one of the biggest causes of wrong answers.
4. Step 2 — Identify Input and Output
Suppose:
Given
nnumbers, find the largest element.
Input:
n = 5 arr = [4, 8, 2, 9, 1]
Output:
9
Represent it mentally as:
INPUT ↓ [4, 8, 2, 9, 1] ↓ PROCESS ↓ Maximum ↓ OUTPUT 9
5. Step 3 — Look at Constraints
Constraints are extremely important.
Suppose:
1 ≤ n ≤ 100
O(n²) might be completely fine.
But if:
1 ≤ n ≤ 100,000
then:
O(n²)
may be too slow.
If:
1 ≤ n ≤ 1,000,000
you probably need approximately:
O(n)
or perhaps:
O(n log n)
depending on the problem.
6. Complexity as a Decision Tool
A rough guideline:
n | Usually Consider |
|---|---|
n ≤ 10 | Brute force / exponential may work |
n ≤ 20 | O(2ⁿ) may work |
n ≤ 100 | O(n³) may sometimes work |
n ≤ 1,000 | O(n²) often works |
n ≤ 100,000 | O(n log n) / O(n) |
n ≤ 1,000,000 | Usually O(n) |
n very large | Often O(log n) or O(1) |
These aren't strict rules. Actual limits depend on the language, number of test cases, constants, and time limit.
7. Step 4 — Start With Brute Force
Brute force is not bad.
It's often the easiest way to understand the problem.
Suppose:
Find whether an array contains duplicate elements.
Brute force:
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] == arr[j]) return true; } } return false;
Complexity:
O(n²)
Now ask:
Can I do better?
8. Optimize Using Hashing
Use:
unordered_set<int> seen; for (int x : arr) { if (seen.count(x)) return true; seen.insert(x); } return false;
Average complexity:
Time = O(n) Space = O(n)
The important thinking process was:
Brute force ↓ Repeated comparison ↓ Need faster lookup ↓ Hash Set ↓ O(n)
9. The Most Important Question
Whenever your solution is slow, ask:
What operation am I repeatedly doing?
For example:
Repeated search ↓ Hashing / Binary Search / BST / Trie Repeated range sum ↓ Prefix Sum / Fenwick / Segment Tree Repeated minimum/maximum ↓ Heap / Deque / Segment Tree Repeated graph connectivity ↓ DSU Repeated substring/prefix search ↓ Trie / String algorithms
This is how you select data structures.
10. Pattern Recognition
Most DSA problems are not completely new.
They often belong to known patterns.
You should learn to recognize them.
11. Pattern 1 — Two Pointers
Common when:
- Array is sorted
- Need a pair
- Need to compare both ends
- Need to remove duplicates
- Need a subarray condition
Example:
[1, 2, 3, 4, 6]
Find two numbers whose sum is 6.
Use:
left → 1 right → 6
If sum is too small:
left++
If sum is too large:
right--
Complexity:
O(n)
12. Pattern 2 — Sliding Window
Use when the problem involves:
A contiguous subarray/substring.
Example:
Find the maximum sum of a subarray of size
k.
Instead of recalculating every window:
[1 2 3] [2 3 4] [3 4 5]
maintain a running sum.
int sum = 0; for (int i = 0; i < k; i++) sum += arr[i]; int ans = sum; for (int i = k; i < n; i++) { sum += arr[i]; sum -= arr[i - k]; ans = max(ans, sum); }
Complexity:
O(n)
13. Pattern 3 — Prefix Sum
Suppose:
arr = [2, 4, 1, 5, 3]
We need many range-sum queries.
Create:
prefix: [0, 2, 6, 7, 12, 15]
Then:
sum(l, r) = prefix[r + 1] - prefix[l]
After preprocessing:
Build = O(n) Query = O(1)
Use prefix sums when:
The array doesn't change and there are many range-sum queries.
14. Pattern 4 — Hashing
Think about hashing when you see:
frequency duplicate unique count pair lookup seen before
Example:
Count frequency of each number.
unordered_map<int, int> freq; for (int x : arr) freq[x]++;
15. Pattern 5 — Binary Search
Don't think binary search only means:
Search an element in a sorted array.
A more powerful pattern is:
Can I eliminate half of the possible answers?
Example:
Find the minimum speed needed to finish work within
Hhours.
Possible speeds:
1 2 3 4 5 ...
If speed 5 works, then speeds greater than 5 also work.
This creates a monotonic condition:
false false false true true true
Binary search can find the first true.
This is called:
Binary Search on Answer
16. Pattern 6 — Stack
Think stack when you see:
matching brackets undo previous/next nested structure expression monotonic
Example:
"{[()]}"
Use a stack to match opening and closing brackets.
17. Pattern 7 — Monotonic Stack
Think:
next greater next smaller previous greater previous smaller histogram
Example:
[2, 1, 5, 3, 4]
Find the next greater element.
A monotonic stack can solve it in:
O(n)
instead of:
O(n²)
18. Pattern 8 — Queue / BFS
Think BFS when:
level by level shortest path minimum number of moves unweighted graph grid movement
Example:
Find the minimum number of steps from
StoE.
Use:
BFS
because each move has equal cost.
19. Pattern 9 — DFS
Think DFS when:
explore all possibilities connected components islands cycle detection tree traversal backtracking-like exploration
Example:
Number of Islands
Each unvisited land cell can start a DFS.
20. Pattern 10 — Recursion
Think recursion when the problem naturally contains:
smaller version of itself tree structure divide into subproblems backtracking
Examples:
Factorial Tree traversal Merge Sort Quick Sort DFS Backtracking
21. Pattern 11 — Backtracking
Think:
choose explore undo
Common problems:
- Subsets
- Permutations
- N-Queens
- Sudoku
- Maze
- Combination Sum
Template:
void solve(...) { if (baseCase) { // answer return; } for (auto choice : choices) { makeChoice(); solve(...); undoChoice(); } }
22. Pattern 12 — Greedy
Ask:
Can I make a locally best choice and prove that it leads to an optimal solution?
Examples:
Activity Selection Fractional Knapsack Huffman Coding Kruskal Prim Dijkstra
But remember:
Greedy is not automatically correct.
You need a reason/proof that the local choice is safe.
23. Pattern 13 — Dynamic Programming
Think DP when you see:
same subproblem repeated choices maximize/minimize/count current answer depends on previous answers
Typical examples:
Fibonacci 0/1 Knapsack Coin Change LCS LIS Edit Distance Grid DP Partition problems
Basic DP process:
Define state ↓ Find transition ↓ Base case ↓ Compute/store answers
24. Pattern 14 — Divide and Conquer
Think:
Divide ↓ Solve smaller problems ↓ Combine
Examples:
Merge Sort Quick Sort Binary Search
Typical recurrence:
T(n) = 2T(n/2) + O(n)
which gives:
O(n log n)
25. Pattern 15 — Bit Manipulation
Think bit manipulation when you see:
XOR binary set bit toggle subset power of 2 unique number bitmask
Important tricks:
n & 1 n & (n - 1) n & -n 1 << i
26. Pattern 16 — Heap / Priority Queue
Think heap when you see:
largest smallest top K priority continually get minimum continually get maximum
Example:
Find the K largest elements.
A min-heap of size K can solve it in:
O(n log k)
27. Pattern 17 — Trie
Think Trie when you see:
prefix autocomplete dictionary starts with word search
For example:
car card care careful
A Trie efficiently shares:
car
as a common prefix.
28. Pattern 18 — DSU
Think DSU when you see:
connected components merge groups are these connected? dynamic connectivity Kruskal
Operations:
find(x) union(a, b)
29. Pattern 19 — Segment Tree / Fenwick Tree
Think these structures when you see:
many range queries + updates
For example:
update index query sum [L,R] update index query minimum [L,R] ...
Use:
Fenwick → mostly prefix/range sums Segment Tree → more flexible range queries
30. Choosing the Algorithm
A useful decision process:
PROBLEM │ ┌────────────┴────────────┐ │ │ Array/String Graph? │ │ ↓ ↓ Sorted? BFS / DFS / \ Yes No │ │ ↓ ↓ Binary Hashing? Search │ ↓ Hash Map/Set
But this is only a starting point.
The constraints and operations ultimately determine the solution.
31. Example Problem — Two Sum
Problem:
Given an array and target, find two numbers whose sum equals target.
Example:
arr = [2, 7, 11, 15] target = 9
Approach 1 — Brute Force
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] + arr[j] == target) { return true; } } }
Complexity:
O(n²)
Approach 2 — Hashing
For each number:
need = target - current
Example:
current = 2 need = 7
Store 2.
Next:
current = 7 need = 2
2 already exists.
Answer found.
unordered_set<int> seen; for (int x : arr) { int need = target - x; if (seen.count(need)) return true; seen.insert(x); } return false;
Average:
O(n)
32. Example — Maximum Subarray
Problem:
arr = [-2,1,-3,4,-1,2,1,-5,4]
Find maximum subarray sum.
Brute force could examine every subarray.
That's:
O(n²)
or worse depending on how sums are calculated.
But recognize:
This is the classic Kadane's Algorithm problem.
Maintain:
current sum maximum sum
int maxSubArray(vector<int>& nums) { int current = nums[0]; int best = nums[0]; for (int i = 1; i < nums.size(); i++) { current = max(nums[i], current + nums[i]); best = max(best, current); } return best; }
Complexity:
Time = O(n) Space = O(1)
The important skill was recognizing the pattern.
33. Example — Shortest Path
Suppose:
A -- B -- C | | D ------- E
If every edge costs the same:
BFS
is usually the right starting point.
If edges have non-negative different weights:
Dijkstra
If negative edges exist:
Bellman-Ford
For all-pairs shortest paths:
Floyd-Warshall
The problem statement tells you which tool fits.
34. Example — Grid Problems
Many grid problems are actually graph problems.
Suppose:
1 1 0 0 1 0 1 0 1
Each cell can be treated as a node.
Connections might be:
up down left right
Then:
Grid ↓ Graph ↓ BFS / DFS
This is a very important problem-solving transformation.
35. Transform the Problem
A strong DSA programmer learns to convert problems.
Grid → Graph
Maze ↓ Graph ↓ BFS/DFS
String → Frequency Array/Hash Map
Anagram ↓ Character counts
Array → Prefix Sum
Many range sums ↓ Prefix array
Array → Heap
Top K ↓ Priority Queue
Graph → DSU
Connectivity ↓ Union-Find
Set of choices → Bitmask
Subset ↓ Binary mask
This transformation skill is extremely valuable.
36. Edge Cases
Never test only the normal case.
For every problem, think about:
Empty input
[]
One element
[5]
All equal
[7,7,7,7]
Already sorted
[1,2,3,4,5]
Reverse sorted
[5,4,3,2,1]
Negative numbers
[-5,-2,-10]
Zero
[0,0,0]
Very large values
Potential:
integer overflow
Duplicate values
Always consider them.
37. Common Mistakes
Mistake 1 — Coding too quickly
Don't immediately write code.
First understand the problem.
Mistake 2 — Ignoring constraints
An O(n²) solution may pass for:
n = 100
but fail for:
n = 100000
Mistake 3 — Using the wrong data structure
If you repeatedly search:
O(n)
consider:
Hash Set BST Trie
depending on the problem.
Mistake 4 — Overcomplicating
Don't use a Segment Tree when a simple prefix sum solves the problem.
Prefer the simplest correct solution that meets the constraints.
Mistake 5 — Not proving the idea
Especially for:
Greedy Binary Search on Answer DP transitions
you should understand why the method is correct.
38. Debugging Strategy
When your code doesn't work:
Step 1
Test a tiny input.
n = 1
Step 2
Print important variables.
cout << left << " " << right << " " << mid << endl;
Step 3
Check loop boundaries.
Common errors:
i < n
vs
i <= n
Step 4
Check initialization.
Step 5
Check integer overflow.
Step 6
Test edge cases.
39. Brute Force → Optimize
This is one of the most important DSA habits.
Always think:
Can I solve it simply? ↓ What is the complexity? ↓ Why is it slow? ↓ What operation is expensive? ↓ Can a data structure reduce it? ↓ Can a mathematical observation reduce it? ↓ Can I eliminate unnecessary work?
Example:
O(n²) ↓ Hashing ↓ O(n)
or:
O(n²) ↓ Sorting + Two Pointers ↓ O(n log n)
or:
O(n) per query ↓ Prefix Sum ↓ O(1) per query
40. Important DSA Patterns to Master
If you're preparing for interviews or competitive programming, focus heavily on these:
1. Two Pointers 2. Sliding Window 3. Prefix Sum 4. Difference Array 5. Hashing 6. Binary Search 7. Binary Search on Answer 8. Fast/Slow Pointers 9. Stack 10. Monotonic Stack 11. Queue 12. Monotonic Queue 13. BFS 14. DFS 15. Backtracking 16. Greedy 17. Divide and Conquer 18. Dynamic Programming 19. Bit Manipulation 20. Heap / Priority Queue 21. DSU 22. Trie 23. Segment Tree 24. Fenwick Tree 25. Graph Algorithms
41. A Useful Pattern Table
| If you see... | Think... |
|---|---|
| Sorted array | Binary Search / Two Pointers |
| Pair with target | Hashing / Two Pointers |
| Contiguous subarray | Sliding Window / Prefix Sum |
| Many range sums | Prefix Sum |
| Range query + updates | Segment Tree / Fenwick |
| Frequency | Hash Map |
| Duplicate | Set / Hash Map |
| Top K | Heap |
| Next greater | Monotonic Stack |
| Sliding maximum | Monotonic Deque |
| Shortest unweighted path | BFS |
| Shortest weighted path | Dijkstra |
| Negative edges | Bellman-Ford |
| Connected components | DFS/BFS/DSU |
| Minimum spanning tree | Kruskal/Prim |
| Prefix | Trie |
| Repeated choices | DP |
| All combinations | Backtracking |
| Local optimal choice | Greedy |
| Divide into halves | Divide & Conquer |
| Subsets | Bitmask |
| Connectivity merging | DSU |
42. How to Practice DSA
Don't solve random problems without a plan.
Use this progression:
Easy ↓ Understand pattern ↓ Solve without looking ↓ Analyze complexity ↓ Try a better solution ↓ Medium ↓ Combine patterns ↓ Hard
For each problem, write down:
Problem: Pattern: Data Structure: Algorithm: Time Complexity: Space Complexity: Edge Cases:
This builds problem-solving ability much faster than simply memorizing solutions.
43. Don't Memorize Solutions
Suppose you memorize:
Kadane's Algorithm
That's useful.
But more important is understanding:
Why can I discard a previous negative contribution?
Then when a new problem appears, you may recognize the same idea even if the problem looks completely different.
The goal is:
Memorization ↓ Understanding ↓ Pattern Recognition ↓ Independent Problem Solving
44. Build Your Own Decision Tree
When you see a new problem, ask:
NEW PROBLEM │ What is required? │ ┌─────────────┼──────────────┐ ↓ ↓ ↓ Search Optimize Generate │ │ │ Binary/Hash DP/Greedy Backtracking │ │ │ └─────────────┼──────────────┘ ↓ What data structure? │ ┌────────────────┼─────────────────┐ ↓ ↓ ↓ Set/Map Heap Graph ↓ ↓ ↓ Fast lookup Top K BFS/DFS/DSU
This decision-making process becomes faster with practice.
45. From Beginner to Strong Problem Solver
Your progression should look like:
Level 1 Understand syntax ↓ Level 2 Understand data structures ↓ Level 3 Understand algorithms ↓ Level 4 Recognize patterns ↓ Level 5 Optimize brute force ↓ Level 6 Combine techniques ↓ Level 7 Solve unseen problems ↓ Level 8 Prove correctness + optimize
The last two levels are where strong problem-solving ability develops.
46. A Complete Example of the Thinking Process
Problem:
Given an array, find the length of the longest subarray containing no duplicate values.
Example:
[1, 2, 3, 1, 2]
Answer:
3
because:
[1, 2, 3]
Step 1 — Brute Force
Generate every subarray.
Potential complexity:
O(n²)
or worse if checking duplicates separately.
Step 2 — Recognize the Pattern
The phrase:
longest subarray
suggests:
Sliding Window
And:
no duplicates
suggests:
Set / Hash Map
Step 3 — Combine Them
Use:
Sliding Window + Hash Set
Step 4 — Code
int longestUniqueSubarray(vector<int>& arr) { unordered_set<int> seen; int left = 0; int answer = 0; for (int right = 0; right < arr.size(); right++) { while (seen.count(arr[right])) { seen.erase(arr[left]); left++; } seen.insert(arr[right]); answer = max( answer, right - left + 1 ); } return answer; }
Complexity:
Time = O(n) average Space = O(n)
The important part isn't the code.
It's:
"longest subarray" ↓ Sliding Window "no duplicates" ↓ Hash Set Combine ↓ O(n)