Ugenz Academy/Tutorial

Problemsolving

18 min read3,403 words

Reading progress

Keep learning

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 n numbers, 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:

nUsually Consider
n ≤ 10Brute force / exponential may work
n ≤ 20O(2ⁿ) may work
n ≤ 100O(n³) may sometimes work
n ≤ 1,000O(n²) often works
n ≤ 100,000O(n log n) / O(n)
n ≤ 1,000,000Usually O(n)
n very largeOften 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 H hours.

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 S to E.

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 arrayBinary Search / Two Pointers
Pair with targetHashing / Two Pointers
Contiguous subarraySliding Window / Prefix Sum
Many range sumsPrefix Sum
Range query + updatesSegment Tree / Fenwick
FrequencyHash Map
DuplicateSet / Hash Map
Top KHeap
Next greaterMonotonic Stack
Sliding maximumMonotonic Deque
Shortest unweighted pathBFS
Shortest weighted pathDijkstra
Negative edgesBellman-Ford
Connected componentsDFS/BFS/DSU
Minimum spanning treeKruskal/Prim
PrefixTrie
Repeated choicesDP
All combinationsBacktracking
Local optimal choiceGreedy
Divide into halvesDivide & Conquer
SubsetsBitmask
Connectivity mergingDSU

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)

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy