Common Problem-Solving Patterns

From Foundations to Paradigms

At the start of Course 06, we formulated the basic blueprint of computational problem solving:

We progressively learned how to calculate asymptotic bounds with Big-O; replace quadratic brute force with hash tables; perform logarithmic searches; sort data efficiently; divide problems recursively; make greedy local choices; optimize overlapping subproblems via DP tables; and traverse interconnected networks using BFS, DFS, and Dijkstra.

Behind thousands of real-world problems lie just 10 to 15 universal patterns. A seasoned software engineer does not view each problem as a blank slate; they look for the structural signature that reveals which reusable pattern can be applied.

Reusable Algorithmic Building Blocks

Simply defined:

“A Problem-Solving Pattern is a reusable high-level strategy or technique that can be systematically adapted to solve a broad family of related algorithmic challenges.”

A pattern is not necessarily a standalone algorithm; rather, it is a mental building block that guides how you explore data. Consider these recurring problem shapes:

Why Rote Learning Fails at Scale

If you memorize the exact code for 100 individual LeetCode problems, you will still freeze when confronted with problem #101. The wording will change, the domain narrative will differ, and your memorized lines of code will not apply directly.

Conversely, if you master 8 to 10 foundational patterns and learn to recognize their cues, you can solve hundreds of problems you have never seen before. The core goal of algorithmic fluency is not memorizing code:

Pruning Combinations on Ordered Data

Consider a sorted array of numbers:

We must find two numbers that sum exactly to 10.

The Brute Force Way: Run two nested loops checking every single pair (\(1+2, 1+4, 1+6, \dots\)). This requires \(O(n^2)\) time, which chokes under massive datasets.

The Two Pointers Way: Because the array is sorted, we place one pointer at the start (\(L\)) and another at the end (\(R\)):

Two Pointers Implementation

def two_sum_sorted(numbers, target):
    left = 0
    right = len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return (left, right)          # Pair located
        elif current_sum < target:
            left += 1                     # Sum too small -> move left rightward
        else:
            right -= 1                    # Sum too large -> move right leftward

    return None                           # No pair satisfies target

Common Use Cases: Sorted pair sum, Palindrome checking ("LEVEL" comparing inward from ends), in-place duplicate removal, merging two sorted arrays, 3Sum (\(O(n^2)\) instead of \(O(n^3)\)), and Container With Most Water.

Eliminating Redundancy in Contiguous Ranges

Consider the following array:

We need to answer: What is the maximum sum of any 3 consecutive elements?

A naive approach re-sums all 3 elements from scratch at every step: \(2+1+5=8\), then \(1+5+1=7\), then \(5+1+3=9\dots\) Re-adding overlapping elements that never changed is a huge waste of CPU cycles.

The Mechanics of Sliding

Initial window of size 3: [2, 1, 5] → sum = 8.
Now slide the window 1 step to the right: [1, 5, 1]. Notice that 1 and 5 were already in the previous window!

Instead of performing \(K\) additions, we perform exactly 1 subtraction and 1 addition—an \(O(1)\) constant-time update regardless of window size!

Fixed vs. Variable Sliding Windows

Common Applications: Maximum/minimum subarray averages, Longest Substring Without Repeating Characters, Minimum Window Substring, and "At most K distinct characters" constraints.

Instant \(O(1)\) Range Queries via Precomputation

Suppose you are given an array:

Users repeatedly query range sums: "What is the sum from index 1 to 3?" or "What is the sum from index 0 to 4?" Scanning the array for every single query costs \(O(n)\). By precomputing a cumulative Prefix Sum array, we resolve any range query in \(O(1)\).

Now, the sum of elements from index \(L\) to \(R\) is computed by a single subtraction:

For instance, the range from index 1 to 3 (\(5 + 2 + 7 = 14\)):
\(\text{prefix}[3] - \text{prefix}[0] = 17 - 3 = 14\). No loops, no scans, pure \(O(1)\) arithmetic.

Instant Lookups and State Tracking

Hash tables are the workhorse of modern software engineering because their lookups, insertions, and deletions execute in \(O(1)\) average time.

Floyd's Tortoise and Hare Cycle Detection

When evaluating sequential data structures such as singly linked lists without consuming auxiliary memory, Floyd's Cycle-Finding Algorithm provides an elegant, optimal solution.

Another Essential Application: Finding the Middle Node of a Linked List in a single pass without knowing the list length. When the Fast pointer hits the end, the Slow pointer rests precisely on the median node.

Tracking Preceding Context and Invariant Ordering

A Stack enforces Last In, First Out (LIFO) order. Whenever a problem requires matching nested structures (such as balanced parentheses ( [ { } ] )), opening symbols are pushed, and incoming closing symbols are matched and popped from the top of the stack.

The Power of the Monotonic Stack

Consider a classic challenge: “For each element, find the Next Greater Element to its right.”

Scanning rightward for every element takes \(O(n^2)\). But by maintaining a stack whose elements are strictly decreasing, incoming larger elements pop smaller candidates from the stack and record themselves as the Next Greater Element. Because every item is pushed and popped at most once, the entire array is resolved in \(O(n)\) linear time!

Pinpointing Monotonic Decision Boundaries

We already know Binary Search searches sorted arrays in \(O(\log n)\). But as a meta-problem-solving pattern, its power is far broader:

“If the feasible answer space exhibits a monotonic boolean property, you can use Binary Search to locate the transition boundary.”

Consider this problem: “What is the minimum machine capacity required to complete all production jobs within 5 days?” There is no sorted array in the input. However, the answer space itself is monotonic:

Once a capacity is large enough, any greater capacity is also guaranteed to work. We are searching for the boundary point where False flips to True. Binary Search converges on this boundary in logarithmic steps.

Matching Structural Cues to Patterns

Use this decision hierarchy to diagnose problems during technical problem-solving sessions:

Diagnose Before You Type

Never dive blindly into writing code. Inspect the problem statement with these 8 questions:

Structure Precedes Pattern

A frequent novice mistake is premature pattern fixation: “I see an array, so I must force a Two Pointers solution!” This leads to convoluted, buggy implementations.

Always remember: The pattern does not dictate the problem—the structure of the problem dictates the pattern.