Problem-Solving Patterns

📖 Introduction

After studying dozens of algorithms and data structures, the real skill is knowing which tool to reach for when facing a new problem. This final article synthesizes everything we've learned into a practical framework for problem-solving.

Over the years, I've noticed that most problems follow recognizable patterns. Once you learn to identify these patterns, what seemed like hundreds of unique problems becomes a handful of techniques applied in different contexts.

---

🎯 The Problem-Solving Framework

Step-by-Step Approach

1. Understand the Problem

• Read carefully: What are the inputs? Outputs? Constraints?

• Identify the goal: Optimization? Counting? Feasibility?

• Note constraints: n ≤ 10⁵ suggests O(n log n), n ≤ 20 suggests exponential is okay

2. Work Through Examples

• Start with simple cases

• Try edge cases (empty, single element, duplicates)

• Trace through by hand before coding

3. Identify the Pattern

• What data structure fits naturally?

• Does it resemble a known problem type?

• Can you break it into subproblems?

4. Plan Before Coding

• Outline the approach in comments

• Consider time/space complexity upfront

• Think about edge cases

---

📊 Pattern Recognition Guide

Quick Reference Table

Pattern	Key Signal	Example Problems
Two Pointers	Sorted array, find pairs	Two Sum II, Container with Water
Sliding Window	Contiguous subarray/substring	Max sum subarray, longest substring
Binary Search	Sorted data, search space	Search in rotated, Koko eating
BFS	Shortest path, level-order	Word ladder, rotting oranges
DFS	Explore all paths, backtrack	Permutations, word search
Dynamic Programming	Overlapping subproblems	Coin change, LCS
Greedy	Local optimal → global	Activity selection, jump game
Hash Map	O(1) lookup, counting	Two sum, anagrams
Stack	Matching, monotonic	Valid parentheses, daily temps
Heap	Top K, stream median	Kth largest, merge K lists
Union-Find	Connectivity, components	Number of islands, redundant edge
Topological Sort	Dependencies, ordering	Course schedule, alien dict

---

🔍 Pattern Deep Dives

Pattern 1: Two Pointers

When to use: Sorted arrays, finding pairs, partition

# Template: Opposite directions
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []


# Template: Same direction (fast/slow)
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1

Classic problems:

• Container With Most Water

• 3Sum, 4Sum

• Remove duplicates

• Merge sorted arrays

---

Pattern 2: Sliding Window

When to use: Contiguous subarray/substring with constraint

# Template: Variable size window
def longest_substring_k_distinct(s: str, k: int) -> int:
    from collections import defaultdict
    
    count = defaultdict(int)
    left = max_len = 0
    
    for right in range(len(s)):
        count[s[right]] += 1
        
        while len(count) > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len


# Template: Fixed size window
def max_sum_subarray_size_k(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

Classic problems:

• Maximum sum subarray of size K

• Longest substring without repeating

• Minimum window substring

• Permutation in string

---

Pattern 3: Binary Search Variations

When to use: Sorted data, monotonic property, search space

# Template: Find exact match
def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


# Template: Search on answer
def minimum_capacity(weights: list[int], days: int) -> int:
    def can_ship(capacity):
        day_count = 1
        current_weight = 0
        for w in weights:
            if current_weight + w > capacity:
                day_count += 1
                current_weight = w
            else:
                current_weight += w
        return day_count <= days
    
    left, right = max(weights), sum(weights)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

Classic problems:

• Search in rotated array

• Find first/last position

• Square root

• Koko eating bananas

---

Pattern 4: BFS Level-Order

When to use: Shortest path (unweighted), level-by-level processing

from collections import deque

# Template: Shortest path
def shortest_path(graph, start, end):
    queue = deque([(start, 0)])
    visited = {start}
    
    while queue:
        node, dist = queue.popleft()
        
        if node == end:
            return dist
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1


# Template: Level-by-level
def level_order(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

Classic problems:

• Word ladder

• Rotting oranges

• Binary tree level order

• Walls and gates

---

Pattern 5: DFS & Backtracking

When to use: Explore all paths, generate combinations/permutations

# Template: Backtracking
def backtrack(path, choices, result):
    if is_solution(path):
        result.append(path[:])
        return
    
    for choice in choices:
        if is_valid(choice, path):
            path.append(choice)
            backtrack(path, remaining_choices, result)
            path.pop()


# Template: Grid DFS
def dfs_grid(grid, row, col, visited):
    if (row < 0 or row >= len(grid) or 
        col < 0 or col >= len(grid[0]) or
        (row, col) in visited or
        grid[row][col] == 0):
        return
    
    visited.add((row, col))
    
    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        dfs_grid(grid, row + dr, col + dc, visited)

Classic problems:

• Subsets, permutations, combinations

• Word search

• N-Queens

• Number of islands

---

Pattern 6: Dynamic Programming

When to use: Overlapping subproblems, optimal substructure

# Template: 1D DP
def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]


# Template: 2D DP
def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

Classic problems:

• House robber

• Coin change

• Longest increasing subsequence

• Edit distance

---

Pattern 7: Monotonic Stack

When to use: Next greater/smaller element, histogram

# Template: Next greater element
def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []  # indices
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result


# Template: Largest rectangle in histogram
def largest_rectangle(heights: list[int]) -> int:
    stack = []
    max_area = 0
    
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    
    return max_area

Classic problems:

• Daily temperatures

• Largest rectangle in histogram

• Trapping rain water

• Stock span

---

Pattern 8: Heap / Priority Queue

When to use: Top K, stream processing, scheduling

import heapq

# Template: Kth largest
def find_kth_largest(nums: list[int], k: int) -> int:
    heap = nums[:k]
    heapq.heapify(heap)
    
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)
    
    return heap[0]


# Template: Merge K sorted
def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    
    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    
    return result

Classic problems:

• Top K frequent elements

• Find median from data stream

• Merge K sorted lists

• Meeting rooms II

---

🧠 Problem-Type Decision Tree

Optimization Problems

Is it about minimum/maximum?
├── Can you verify solution quickly? → Binary Search on Answer
├── Greedy choice works? → Greedy
├── Overlapping subproblems? → Dynamic Programming
└── Need to explore all options? → Backtracking

Counting Problems

Count ways/combinations?
├── Fixed constraint? → Combinatorics / DP
├── Need exact enumeration? → Backtracking
└── Count properties? → Hash Map + iteration

Existence/Feasibility

Can X be done?
├── Graph connectivity? → BFS/DFS/Union-Find
├── Sequence reachable? → DP / Greedy
└── Target achievable? → Binary Search / DP

---

📋 Common Pitfalls

Off-by-One Errors

# Common mistakes:
# - len(arr) vs len(arr) - 1
# - range(n) vs range(n + 1)
# - left <= right vs left < right

# Tip: Always trace through edge cases
# - Empty input
# - Single element
# - Two elements

Integer Overflow

# Python handles big integers, but for mid calculation:
mid = left + (right - left) // 2  # Not (left + right) // 2

Modifying While Iterating

# Wrong:
for item in my_list:
    if condition:
        my_list.remove(item)

# Right:
my_list = [item for item in my_list if not condition]

Reference vs Copy

# Wrong: Adding reference
result.append(path)

# Right: Adding copy
result.append(path[:])
result.append(list(path))

---

⏱️ Complexity Quick Reference

By Constraint

n limit	Acceptable Complexity
n ≤ 10	O(n!), O(2^n)
n ≤ 20	O(2^n), O(n^2 * 2^n)
n ≤ 500	O(n³)
n ≤ 10⁴	O(n²)
n ≤ 10⁶	O(n log n)
n ≤ 10⁸	O(n)
n > 10⁸	O(log n), O(1)

By Pattern

Pattern	Time	Space
Two Pointers	O(n)	O(1)
Sliding Window	O(n)	O(k)
Binary Search	O(log n)	O(1)
BFS/DFS	O(V + E)	O(V)
Sorting	O(n log n)	O(n)
Heap operations	O(log n)	O(n)
DP (2D table)	O(n * m)	O(n * m)

---

🎯 Practice Strategy

Deliberate Practice

1. Learn one pattern at a time

   • Study the template

   • Solve 5-10 similar problems

   • Review and internalize

2. Spaced repetition

   • Revisit problems after 1, 3, 7 days

   • Try solving without looking at solution

3. Time yourself

   • Easy: 15-20 minutes

   • Medium: 25-35 minutes

   • Hard: 40-50 minutes

4. Review mistakes

   • Why did you miss it?

   • What pattern did you overlook?

   • Add to your pattern library

Recommended Order

1. Arrays & Strings (Two Pointers, Sliding Window)
2. Hash Tables (Counting, Lookup)
3. Binary Search
4. Trees (DFS, BFS)
5. Stacks & Queues (Monotonic Stack)
6. Graphs (BFS, DFS, Union-Find)
7. Dynamic Programming
8. Greedy & Backtracking
9. Advanced (Segment Trees, Tries, etc.)

---

📝 Quick Checklist

Before submitting:

• Handled empty/null input?

• Handled single element?

• Handled duplicates correctly?

• Checked off-by-one errors?

• Verified complexity meets constraints?

• Tested with examples from problem?

• Tested with edge cases?

---

🎉 Series Summary

Congratulations on completing the DSA 101 series! Here's what we covered:

Phase	Topics
Foundation	Complexity analysis, recursion
Linear Structures	Arrays, strings, linked lists, stacks, queues, hash tables
Non-Linear Structures	Trees, heaps, graphs
Algorithms	Sorting, searching, DP, greedy, backtracking
Advanced	Graph algorithms, problem-solving patterns

Key Principles

1. Understand before coding

2. Pattern recognition is key

3. Start simple, optimize later

4. Practice consistently

5. Learn from mistakes

---

📚 Resources for Continued Learning

Books

• "Introduction to Algorithms" (CLRS)

• "Algorithm Design Manual" (Skiena)

• "Elements of Programming Interviews"

Online Platforms

• LeetCode (patterns and practice)

• Codeforces (competitive)

• HackerRank (fundamentals)

Communities

• r/leetcode

• Competitive programming Discord servers

• Study groups

---

🙏 Final Thoughts

Data structures and algorithms aren't just interview topics—they're tools that help you build better software. The patterns you've learned here will serve you throughout your career, whether you're optimizing database queries, designing system architectures, or building user-facing applications.

Keep practicing, stay curious, and remember: every expert was once a beginner.

Happy coding! 🚀