Problem-Solving Patterns & Techniques: A Complete Guide

Introduction

You've learned Big O notation and can analyze algorithm complexity. But when you face a new coding problem, how do you actually solve it?

The secret is that most coding problems follow recurring patterns. Once you recognize the pattern, the solution becomes clear. Expert problem solvers don't invent new algorithms for every problem — they match problems to known patterns and adapt.

"Every problem you solve gives you a tool for solving the next one."
— The key insight behind pattern-based problem solving.

In this post, we'll cover the most important problem-solving patterns used in coding interviews and real-world development, with a systematic framework you can apply to any problem.

What You'll Learn

✅ Apply a systematic problem-solving framework to any coding challenge
✅ Master Two Pointers for array and string problems
✅ Use Sliding Window for subarray/substring optimization
✅ Leverage Hash Maps for O(1) lookups and frequency counting
✅ Apply Prefix Sum for efficient range queries
✅ Understand Divide and Conquer for recursive problem decomposition
✅ Use Recursion and Backtracking for exhaustive search
✅ Recognize which pattern fits which problem type
✅ Solve coding interview problems with confidence

Prerequisites

Understanding of Big O Notation & Complexity Analysis
Basic programming knowledge (arrays, loops, functions)
Familiarity with TypeScript OR Python

1. The Problem-Solving Framework

Before diving into patterns, let's establish a systematic approach for tackling any problem.

The UMPIRE Method

U — Understand the problem

Read the problem carefully (twice!)
Identify inputs and outputs
Clarify constraints (size, range, duplicates?)
Ask questions: "Can the array be empty?", "Are values sorted?"

M — Match to known patterns

Does this look like a Two Pointers problem?
Is there a subarray/substring involved? → Sliding Window
Do I need fast lookups? → Hash Map
Can I divide this into smaller subproblems? → Divide and Conquer

P — Plan your approach

Write pseudocode before real code
Define your data structures
Walk through an example by hand

I — Implement the solution

Translate pseudocode to code
Name variables clearly
Handle edge cases

R — Review your code

Trace through with examples
Check edge cases (empty input, single element, duplicates)

E — Evaluate complexity

State time and space complexity
Can you optimize further?

Example: Applying the Framework

Problem: Given a sorted array, find two numbers that add up to a target.

Input: [2, 4, 6, 10, 15], target = 14
Output: [1, 3] (indices of 4 and 10)

Understand: Sorted array, find pair summing to target, return indices
Match: Sorted array + pair → Two Pointers pattern
Plan: Left pointer at start, right at end, move based on sum comparison
Implement: Write the code (we'll see this in the Two Pointers section)
Review: Test with examples, check empty array
Evaluate: O(n) time, O(1) space — optimal for this problem

2. Two Pointers

When to use: Working with sorted arrays, finding pairs, comparing elements from both ends, or partitioning data.

How It Works

Use two pointers (indices) that move toward each other or in the same direction, reducing the search space at each step.

Common variants:

Opposite direction: Start from both ends, move inward
Same direction: Fast and slow pointers, or a read/write pointer

Pattern 1: Pair Sum in Sorted Array

TypeScript:

// Find two numbers in sorted array that sum to target
// Time: O(n), Space: O(1)
function twoSumSorted(nums: number[], target: number): [number, number] {
    let left = 0;
    let right = nums.length - 1;
 
    while (left < right) {
        const sum = nums[left] + nums[right];
 
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;   // Need larger sum → move left pointer right
        } else {
            right--;  // Need smaller sum → move right pointer left
        }
    }
 
    return [-1, -1]; // No pair found
}
 
console.log(twoSumSorted([2, 4, 6, 10, 15], 14));  // [1, 3]
console.log(twoSumSorted([2, 4, 6, 8], 10));       // [0, 3]

Python:

# Find two numbers in sorted array that sum to target
# Time: O(n), Space: O(1)
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, 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 (-1, -1)
 
print(two_sum_sorted([2, 4, 6, 10, 15], 14))  # (1, 3)
print(two_sum_sorted([2, 4, 6, 8], 10))       # (0, 3)

Why it works: Since the array is sorted, moving the left pointer increases the sum, and moving the right pointer decreases it. We systematically narrow down to the answer.

Pattern 2: Remove Duplicates In-Place

TypeScript:

// Remove duplicates from sorted array in-place
// Time: O(n), Space: O(1)
function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0;
 
    let write = 1; // Write pointer (slow)
 
    for (let read = 1; read < nums.length; read++) { // Read pointer (fast)
        if (nums[read] !== nums[read - 1]) {
            nums[write] = nums[read];
            write++;
        }
    }
 
    return write; // New length
}
 
const arr = [1, 1, 2, 2, 3, 4, 4, 5];
const newLength = removeDuplicates(arr);
console.log(arr.slice(0, newLength)); // [1, 2, 3, 4, 5]

Python:

# Remove duplicates from sorted array in-place
# Time: O(n), Space: O(1)
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
 
    write = 1
 
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
 
    return write
 
arr = [1, 1, 2, 2, 3, 4, 4, 5]
new_length = remove_duplicates(arr)
print(arr[:new_length])  # [1, 2, 3, 4, 5]

Pattern 3: Palindrome Check

TypeScript:

// Check if string is a palindrome (ignoring non-alphanumeric)
// Time: O(n), Space: O(1)
function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;
 
    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !isAlphanumeric(s[left])) left++;
        while (left < right && !isAlphanumeric(s[right])) right--;
 
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
 
        left++;
        right--;
    }
 
    return true;
}
 
function isAlphanumeric(char: string): boolean {
    return /[a-zA-Z0-9]/.test(char);
}
 
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("hello"));                           // false

Python:

# Check if string is a palindrome (ignoring non-alphanumeric)
# Time: O(n), Space: O(1)
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
 
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
 
        if s[left].lower() != s[right].lower():
            return False
 
        left += 1
        right -= 1
 
    return True
 
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("hello"))                             # False

When to Recognize Two Pointers

Signal	Example Problem
Sorted array + finding pairs	Two sum, pair with target difference
In-place modification	Remove duplicates, move zeros
Palindrome check	Valid palindrome, longest palindrome
Merging two sorted arrays	Merge sorted arrays
Partitioning	Dutch national flag, sort colors

3. Sliding Window

When to use: Finding an optimal subarray or substring of a specific size or with certain properties.

How It Works

Maintain a "window" (contiguous subarray/substring) that slides through the data. Instead of recalculating everything from scratch, update the window by adding/removing one element at a time.

Two types:

Fixed window: Window size is constant (e.g., max sum of k elements)
Variable window: Window size changes based on conditions (e.g., smallest subarray with sum ≥ target)

Pattern 1: Maximum Sum of k Consecutive Elements (Fixed Window)

TypeScript:

// Find maximum sum of k consecutive elements
// Time: O(n), Space: O(1)
function maxSumSubarray(nums: number[], k: number): number {
    if (nums.length < k) return -1;
 
    // Calculate sum of first window
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];
    }
 
    let maxSum = windowSum;
 
    // Slide the window: add right element, remove left element
    for (let i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k]; // Add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
 
    return maxSum;
}
 
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)
console.log(maxSumSubarray([1, 9, 2, 8, 3, 7], 2)); // 11 (9+2)

Python:

# Find maximum sum of k consecutive elements
# Time: O(n), Space: O(1)
def max_sum_subarray(nums: list[int], k: int) -> int:
    if len(nums) < k:
        return -1
 
    # Calculate sum of first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
 
    # Slide the window
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9
print(max_sum_subarray([1, 9, 2, 8, 3, 7], 2))  # 11

Without sliding window: O(n × k) — recalculate sum for every position With sliding window: O(n) — just add one and remove one element each step

Pattern 2: Longest Substring Without Repeating Characters (Variable Window)

TypeScript:

// Find length of longest substring without repeating characters
// Time: O(n), Space: O(min(n, alphabet_size))
function lengthOfLongestSubstring(s: string): number {
    const charIndex = new Map<string, number>();
    let maxLength = 0;
    let left = 0;
 
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
 
        // If character was seen and is within current window, shrink window
        if (charIndex.has(char) && charIndex.get(char)! >= left) {
            left = charIndex.get(char)! + 1;
        }
 
        charIndex.set(char, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
 
    return maxLength;
}
 
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb"));    // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew"));   // 3 ("wke")

Python:

# Find length of longest substring without repeating characters
# Time: O(n), Space: O(min(n, alphabet_size))
def length_of_longest_substring(s: str) -> int:
    char_index: dict[str, int] = {}
    max_length = 0
    left = 0
 
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
 
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))      # 1
print(length_of_longest_substring("pwwkew"))     # 3

Pattern 3: Smallest Subarray with Sum ≥ Target (Variable Window)

TypeScript:

// Find minimum length subarray with sum >= target
// Time: O(n), Space: O(1)
function minSubArrayLen(target: number, nums: number[]): number {
    let minLength = Infinity;
    let windowSum = 0;
    let left = 0;
 
    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];
 
        // Shrink window while condition is met
        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
 
    return minLength === Infinity ? 0 : minLength;
}
 
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3])); // 2 ([4, 3])
console.log(minSubArrayLen(11, [1, 1, 1, 1, 1]));    // 0 (impossible)

Python:

# Find minimum length subarray with sum >= target
# Time: O(n), Space: O(1)
def min_sub_array_len(target: int, nums: list[int]) -> int:
    min_length = float("inf")
    window_sum = 0
    left = 0
 
    for right in range(len(nums)):
        window_sum += nums[right]
 
        while window_sum >= target:
            min_length = min(min_length, right - left + 1)
            window_sum -= nums[left]
            left += 1
 
    return 0 if min_length == float("inf") else min_length
 
print(min_sub_array_len(7, [2, 3, 1, 2, 4, 3]))  # 2
print(min_sub_array_len(11, [1, 1, 1, 1, 1]))      # 0

When to Recognize Sliding Window

Signal	Example Problem
Contiguous subarray/substring	Max sum subarray, min window substring
"k consecutive elements"	Max average of k elements
"Longest/shortest with condition"	Longest substring without repeats
Optimization over all subarrays	Smallest subarray with sum ≥ target

4. Hash Maps for Fast Lookups

When to use: Need O(1) lookups, counting frequencies, checking for duplicates, or grouping elements.

How It Works

Hash Maps (objects, dictionaries) provide O(1) average lookup time. They're the most versatile tool for converting O(n²) brute-force solutions into O(n).

Pattern 1: Two Sum (Unsorted Array)

The classic interview problem — find two numbers that add to a target.

TypeScript:

// Two Sum using hash map
// Time: O(n), Space: O(n)
function twoSum(nums: number[], target: number): [number, number] {
    const seen = new Map<number, number>(); // value → index
 
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
 
        if (seen.has(complement)) {
            return [seen.get(complement)!, i];
        }
 
        seen.set(nums[i], i);
    }
 
    return [-1, -1];
}
 
console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]
console.log(twoSum([3, 2, 4], 6));       // [1, 2]

Python:

# Two Sum using hash map
# Time: O(n), Space: O(n)
def two_sum(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}  # value → index
 
    for i, num in enumerate(nums):
        complement = target - num
 
        if complement in seen:
            return (seen[complement], i)
 
        seen[num] = i
 
    return (-1, -1)
 
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)
print(two_sum([3, 2, 4], 6))       # (1, 2)

Pattern 2: Frequency Counting

TypeScript:

// Check if two strings are anagrams
// Time: O(n), Space: O(k) where k = unique characters
function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) return false;
 
    const freq = new Map<string, number>();
 
    // Count characters in first string
    for (const char of s) {
        freq.set(char, (freq.get(char) || 0) + 1);
    }
 
    // Subtract characters in second string
    for (const char of t) {
        const count = freq.get(char);
        if (!count) return false;  // Character not found or count is 0
        freq.set(char, count - 1);
    }
 
    return true;
}
 
console.log(isAnagram("anagram", "nagaram")); // true
console.log(isAnagram("rat", "car"));         // false
 
// Find most frequent element
// Time: O(n), Space: O(n)
function mostFrequent(nums: number[]): number {
    const freq = new Map<number, number>();
    let maxCount = 0;
    let result = nums[0];
 
    for (const num of nums) {
        const count = (freq.get(num) || 0) + 1;
        freq.set(num, count);
 
        if (count > maxCount) {
            maxCount = count;
            result = num;
        }
    }
 
    return result;
}
 
console.log(mostFrequent([1, 3, 2, 1, 4, 1, 3])); // 1

Python:

from collections import Counter
 
# Check if two strings are anagrams
# Time: O(n), Space: O(k) where k = unique characters
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)
 
print(is_anagram("anagram", "nagaram"))  # True
print(is_anagram("rat", "car"))          # False
 
# Find most frequent element
# Time: O(n), Space: O(n)
def most_frequent(nums: list[int]) -> int:
    return Counter(nums).most_common(1)[0][0]
 
print(most_frequent([1, 3, 2, 1, 4, 1, 3]))  # 1

Pattern 3: Group By Property

TypeScript:

// Group anagrams together
// Time: O(n * k log k), Space: O(n * k)  where k = max string length
function groupAnagrams(strs: string[]): string[][] {
    const groups = new Map<string, string[]>();
 
    for (const str of strs) {
        // Sort characters to create a key for the anagram group
        const key = str.split("").sort().join("");
 
        if (!groups.has(key)) {
            groups.set(key, []);
        }
        groups.get(key)!.push(str);
    }
 
    return Array.from(groups.values());
}
 
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Python:

from collections import defaultdict
 
# Group anagrams together
# Time: O(n * k log k), Space: O(n * k)
def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
 
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
 
    return list(groups.values())
 
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

When to Recognize Hash Map

Signal	Example Problem
"Find if exists"	Two sum, contains duplicate
Counting occurrences	Anagram check, majority element
Grouping elements	Group anagrams, group by category
O(n²) → O(n) optimization	Replace nested loop with lookup
"First unique"	First non-repeating character

5. Prefix Sum

When to use: Computing range sums efficiently, especially when you need to query multiple ranges.

How It Works

Build an array where each element stores the cumulative sum up to that index. Then any range sum can be computed in O(1) using subtraction.

Array:      [2, 4, 1, 3, 5]
Prefix Sum: [0, 2, 6, 7, 10, 15]
 
Sum of elements from index 1 to 3:
= prefix[4] - prefix[1]
= 10 - 2
= 8  (which is 4 + 1 + 3)

Pattern 1: Range Sum Query

TypeScript:

// Build prefix sum for efficient range queries
// Preprocessing: O(n), Each query: O(1)
class PrefixSum {
    private prefix: number[];
 
    constructor(nums: number[]) {
        this.prefix = new Array(nums.length + 1).fill(0);
        for (let i = 0; i < nums.length; i++) {
            this.prefix[i + 1] = this.prefix[i] + nums[i];
        }
    }
 
    // Sum of elements from index left to right (inclusive)
    rangeSum(left: number, right: number): number {
        return this.prefix[right + 1] - this.prefix[left];
    }
}
 
const ps = new PrefixSum([2, 4, 1, 3, 5]);
console.log(ps.rangeSum(1, 3)); // 8 (4 + 1 + 3)
console.log(ps.rangeSum(0, 4)); // 15 (entire array)
console.log(ps.rangeSum(2, 2)); // 1 (single element)

Python:

# Build prefix sum for efficient range queries
# Preprocessing: O(n), Each query: O(1)
class PrefixSum:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]
 
    def range_sum(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]
 
ps = PrefixSum([2, 4, 1, 3, 5])
print(ps.range_sum(1, 3))  # 8
print(ps.range_sum(0, 4))  # 15
print(ps.range_sum(2, 2))  # 1

Pattern 2: Subarray Sum Equals K

TypeScript:

// Count subarrays with sum equal to k
// Time: O(n), Space: O(n)
function subarraySum(nums: number[], k: number): number {
    const prefixCount = new Map<number, number>();
    prefixCount.set(0, 1); // Empty prefix has sum 0
    let count = 0;
    let currentSum = 0;
 
    for (const num of nums) {
        currentSum += num;
 
        // If (currentSum - k) exists in prefix sums,
        // we found a subarray summing to k
        if (prefixCount.has(currentSum - k)) {
            count += prefixCount.get(currentSum - k)!;
        }
 
        prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
    }
 
    return count;
}
 
console.log(subarraySum([1, 1, 1], 2));     // 2 ([1,1] at index 0-1 and 1-2)
console.log(subarraySum([1, 2, 3], 3));     // 2 ([1,2] and [3])
console.log(subarraySum([1, -1, 1, 1], 2)); // 2

Python:

# Count subarrays with sum equal to k
# Time: O(n), Space: O(n)
def subarray_sum(nums: list[int], k: int) -> int:
    prefix_count: dict[int, int] = {0: 1}
    count = 0
    current_sum = 0
 
    for num in nums:
        current_sum += num
 
        if current_sum - k in prefix_count:
            count += prefix_count[current_sum - k]
 
        prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
 
    return count
 
print(subarray_sum([1, 1, 1], 2))      # 2
print(subarray_sum([1, 2, 3], 3))      # 2
print(subarray_sum([1, -1, 1, 1], 2))  # 2

Key insight: Prefix sum + hash map is a powerful combination. Instead of checking all O(n²) subarrays, we use a hash map to find complements in O(1).

When to Recognize Prefix Sum

Signal	Example Problem
Range sum queries	Sum of elements between indices
"Subarray with sum k"	Count/find subarrays with target sum
Running total	Product of all elements except self
Multiple range queries	Answer many sum queries efficiently

6. Divide and Conquer

When to use: Problem can be broken into smaller subproblems of the same type, solved independently, and combined.

How It Works

Divide: Split the problem into smaller subproblems
Conquer: Solve each subproblem recursively
Combine: Merge the solutions

Pattern 1: Merge Sort

The classic divide-and-conquer algorithm.

TypeScript:

// Merge sort - divide and conquer
// Time: O(n log n), Space: O(n)
function mergeSort(arr: number[]): number[] {
    // Base case: single element is already sorted
    if (arr.length <= 1) return arr;
 
    // DIVIDE: split into halves
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
 
    // COMBINE: merge sorted halves
    return merge(left, right);
}
 
function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
 
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
 
    return result.concat(left.slice(i), right.slice(j));
}
 
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Python:

# Merge sort - divide and conquer
# Time: O(n log n), Space: O(n)
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
 
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
 
    return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
    return result
 
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

Pattern 2: Maximum Subarray (Kadane's vs Divide and Conquer)

TypeScript:

// Maximum subarray sum using divide and conquer
// Time: O(n log n), Space: O(log n)
function maxSubArrayDC(nums: number[]): number {
    return helper(nums, 0, nums.length - 1);
}
 
function helper(nums: number[], left: number, right: number): number {
    if (left === right) return nums[left];
 
    const mid = Math.floor((left + right) / 2);
 
    // Maximum in left half, right half, or crossing the middle
    const leftMax = helper(nums, left, mid);
    const rightMax = helper(nums, mid + 1, right);
    const crossMax = maxCrossingSum(nums, left, mid, right);
 
    return Math.max(leftMax, rightMax, crossMax);
}
 
function maxCrossingSum(
    nums: number[], left: number, mid: number, right: number
): number {
    // Extend left from mid
    let leftSum = -Infinity, sum = 0;
    for (let i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }
 
    // Extend right from mid+1
    let rightSum = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }
 
    return leftSum + rightSum;
}
 
console.log(maxSubArrayDC([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
 
// Note: Kadane's algorithm solves this in O(n) — see section 7

Python:

# Maximum subarray sum using divide and conquer
# Time: O(n log n), Space: O(log n)
def max_sub_array_dc(nums: list[int]) -> int:
    def helper(left: int, right: int) -> int:
        if left == right:
            return nums[left]
 
        mid = (left + right) // 2
        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)
        cross_max = max_crossing_sum(left, mid, right)
 
        return max(left_max, right_max, cross_max)
 
    def max_crossing_sum(left: int, mid: int, right: int) -> int:
        left_sum = float("-inf")
        total = 0
        for i in range(mid, left - 1, -1):
            total += nums[i]
            left_sum = max(left_sum, total)
 
        right_sum = float("-inf")
        total = 0
        for i in range(mid + 1, right + 1):
            total += nums[i]
            right_sum = max(right_sum, total)
 
        return left_sum + right_sum
 
    return helper(0, len(nums) - 1)
 
print(max_sub_array_dc([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

When to Recognize Divide and Conquer

Signal	Example Problem
Sort/merge operations	Merge sort, count inversions
Binary search variant	Search in rotated array, find peak
Tree-like decomposition	Maximum subarray, closest pair of points
"Split and merge"	Count inversions, merge k sorted lists

7. Greedy Approach

When to use: Making the locally optimal choice at each step leads to the globally optimal solution.

How It Works

At every step, make the choice that looks best right now, without worrying about future consequences. This only works when the problem has the greedy choice property — local optimums lead to the global optimum.

Pattern 1: Maximum Subarray (Kadane's Algorithm)

TypeScript:

// Maximum subarray sum using Kadane's algorithm (greedy)
// Time: O(n), Space: O(1)
function maxSubArray(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = nums[0];
 
    for (let i = 1; i < nums.length; i++) {
        // Greedy choice: extend current subarray or start fresh
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
 
    return maxSum;
}
 
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 ([4,-1,2,1])
console.log(maxSubArray([1]));                                 // 1
console.log(maxSubArray([-1, -2, -3]));                       // -1

Python:

# Maximum subarray sum using Kadane's algorithm (greedy)
# Time: O(n), Space: O(1)
def max_sub_array(nums: list[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]
 
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
 
    return max_sum
 
print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
print(max_sub_array([1]))                                   # 1
print(max_sub_array([-1, -2, -3]))                         # -1

Greedy insight: At each position, we decide whether to extend the existing subarray or start a new one. If the current subarray sum is negative, starting fresh is always better.

Pattern 2: Activity Selection / Interval Scheduling

TypeScript:

// Maximum number of non-overlapping intervals
// Time: O(n log n), Space: O(1)
function maxNonOverlapping(intervals: [number, number][]): number {
    if (intervals.length === 0) return 0;
 
    // Greedy: sort by end time, always pick earliest ending
    intervals.sort((a, b) => a[1] - b[1]);
 
    let count = 1;
    let lastEnd = intervals[0][1];
 
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;
            lastEnd = intervals[i][1];
        }
    }
 
    return count;
}
 
console.log(maxNonOverlapping([[1, 3], [2, 4], [3, 5], [0, 6], [5, 7]])); // 3
// Selected: [1,3], [3,5], [5,7]

Python:

# Maximum number of non-overlapping intervals
# Time: O(n log n), Space: O(1)
def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:
    if not intervals:
        return 0
 
    intervals.sort(key=lambda x: x[1])
 
    count = 1
    last_end = intervals[0][1]
 
    for start, end in intervals[1:]:
        if start >= last_end:
            count += 1
            last_end = end
 
    return count
 
print(max_non_overlapping([(1, 3), (2, 4), (3, 5), (0, 6), (5, 7)]))  # 3

When to Recognize Greedy

Signal	Example Problem
"Maximum/minimum" with choices	Activity selection, coin change (certain denominations)
Intervals/scheduling	Meeting rooms, merge intervals
Locally optimal → globally optimal	Jump game, gas station
Sorting helps	Assign cookies, most profit assigning work

Warning: Greedy doesn't always work! For example, the coin change problem with arbitrary denominations requires dynamic programming. Always verify the greedy choice property.

8. Recursion and Backtracking

When to use: Exhaustively exploring all possibilities, constraint satisfaction, generating combinations/permutations.

How It Works

Recursion: Break a problem into smaller subproblems of the same type. Backtracking: Try a choice, explore it recursively, and "undo" (backtrack) if it doesn't lead to a solution.

Pattern 1: Generate All Subsets (Power Set)

TypeScript:

// Generate all subsets of an array
// Time: O(2^n), Space: O(n) for recursion depth
function subsets(nums: number[]): number[][] {
    const result: number[][] = [];
 
    function backtrack(start: number, current: number[]): void {
        result.push([...current]); // Add current subset (copy)
 
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);       // Choose
            backtrack(i + 1, current);   // Explore
            current.pop();               // Un-choose (backtrack)
        }
    }
 
    backtrack(0, []);
    return result;
}
 
console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Python:

# Generate all subsets of an array
# Time: O(2^n), Space: O(n) for recursion depth
def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
 
    def backtrack(start: int, current: list[int]) -> None:
        result.append(current[:])  # Add copy of current subset
 
        for i in range(start, len(nums)):
            current.append(nums[i])    # Choose
            backtrack(i + 1, current)  # Explore
            current.pop()              # Un-choose (backtrack)
 
    backtrack(0, [])
    return result
 
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Pattern 2: Generate Permutations

TypeScript:

// Generate all permutations of an array
// Time: O(n!), Space: O(n)
function permutations(nums: number[]): number[][] {
    const result: number[][] = [];
 
    function backtrack(current: number[], remaining: number[]): void {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }
 
        for (let i = 0; i < remaining.length; i++) {
            current.push(remaining[i]);
 
            // Create remaining without index i
            const nextRemaining = [
                ...remaining.slice(0, i),
                ...remaining.slice(i + 1),
            ];
 
            backtrack(current, nextRemaining);
            current.pop(); // Backtrack
        }
    }
 
    backtrack([], nums);
    return result;
}
 
console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Python:

# Generate all permutations of an array
# Time: O(n!), Space: O(n)
def permutations(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
 
    def backtrack(current: list[int], remaining: list[int]) -> None:
        if not remaining:
            result.append(current[:])
            return
 
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i + 1:])
            current.pop()
 
    backtrack([], nums)
    return result
 
print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Pattern 3: Valid Parentheses Generation

TypeScript:

// Generate all valid combinations of n pairs of parentheses
// Time: O(4^n / sqrt(n)), Space: O(n)
function generateParenthesis(n: number): string[] {
    const result: string[] = [];
 
    function backtrack(current: string, open: number, close: number): void {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
 
        // Can add open paren if we haven't used all
        if (open < n) {
            backtrack(current + "(", open + 1, close);
        }
 
        // Can add close paren if it won't be unmatched
        if (close < open) {
            backtrack(current + ")", open, close + 1);
        }
    }
 
    backtrack("", 0, 0);
    return result;
}
 
console.log(generateParenthesis(3));
// ["((()))", "(()())", "(())()", "()(())", "()()()"]

Python:

# Generate all valid combinations of n pairs of parentheses
# Time: O(4^n / sqrt(n)), Space: O(n)
def generate_parenthesis(n: int) -> list[str]:
    result: list[str] = []
 
    def backtrack(current: str, open_count: int, close_count: int) -> None:
        if len(current) == 2 * n:
            result.append(current)
            return
 
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
 
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)
 
    backtrack("", 0, 0)
    return result
 
print(generate_parenthesis(3))
# ["((()))", "(()())", "(())()", "()(())", "()()()"]

The Backtracking Template

Most backtracking problems follow this template:

function backtrack(state, choices):
    if state is a complete solution:
        record the solution
        return
 
    for each choice in choices:
        if choice is valid:
            make the choice        // Choose
            backtrack(new_state)   // Explore
            undo the choice        // Backtrack

When to Recognize Backtracking

Signal	Example Problem
"Generate all..."	All subsets, all permutations, all paths
"Find all valid..."	Valid parentheses, N-queens, Sudoku solver
Combinatorial search	Word search, combination sum
Constraint satisfaction	Sudoku, crossword puzzle

9. Pattern Recognition Cheat Sheet

Here's a quick reference for matching problems to patterns:

By Problem Type

Problem Type	Pattern	Time Complexity
Find pair in sorted array	Two Pointers	O(n)
Max/min subarray of size k	Sliding Window (fixed)	O(n)
Longest substring with condition	Sliding Window (variable)	O(n)
Find element / check existence	Hash Map	O(n)
Count occurrences	Hash Map (frequency)	O(n)
Range sum queries	Prefix Sum	O(n) preprocessing, O(1) query
Subarray with target sum	Prefix Sum + Hash Map	O(n)
Efficient sorting	Divide and Conquer	O(n log n)
Optimization with choices	Greedy	O(n) or O(n log n)
Generate all combinations	Backtracking	O(2ⁿ) or O(n!)

By Keywords in Problem Statement

Keyword	Think About
"Sorted array"	Two Pointers, Binary Search
"Contiguous subarray"	Sliding Window, Prefix Sum
"Substring"	Sliding Window, Hash Map
"Pair" or "two elements"	Two Pointers (sorted), Hash Map (unsorted)
"Unique" or "duplicate"	Hash Set
"Frequency" or "count"	Hash Map
"Range sum" or "cumulative"	Prefix Sum
"Maximum/minimum"	Greedy, Sliding Window, DP
"All combinations"	Backtracking
"Permutations"	Backtracking
"Optimal" substructure	Dynamic Programming (covered in DSA-12)

10. Practice Problems

Try these problems to reinforce each pattern. Start with the first one in each category.

Two Pointers

Container With Most Water — Find two lines that hold the most water
3Sum — Find all unique triplets summing to zero
Sort Colors — Dutch national flag problem (three-way partition)

Sliding Window

Maximum Average Subarray — Max average of k consecutive elements
Minimum Window Substring — Smallest window containing all target characters
Longest Repeating Character Replacement — Longest substring with at most k replacements

Hash Map

Contains Duplicate — Check if any value appears twice
First Unique Character — Find first non-repeating character
Intersection of Two Arrays — Find common elements

Prefix Sum

Running Sum of 1D Array — Compute running sum
Subarray Sum Equals K — Count subarrays with target sum
Product of Array Except Self — Product without division

Greedy

Best Time to Buy and Sell Stock — Maximum profit from one transaction
Jump Game — Can you reach the last index?
Merge Intervals — Merge overlapping intervals

Backtracking

Letter Combinations of Phone Number — Generate all letter combos
Combination Sum — Find combinations summing to target
Word Search — Find word in 2D grid

Summary and Key Takeaways

✅ Use the UMPIRE framework: Understand → Match → Plan → Implement → Review → Evaluate
✅ Two Pointers: Best for sorted arrays, pairs, and in-place modifications — O(n) time, O(1) space
✅ Sliding Window: Best for contiguous subarray/substring problems — O(n) time
✅ Hash Maps: Best for fast lookups, frequency counting, and grouping — O(n) time, O(n) space
✅ Prefix Sum: Best for range queries and subarray sum problems — O(1) per query after O(n) preprocessing
✅ Divide and Conquer: Best for problems that decompose into independent subproblems — O(n log n)
✅ Greedy: Best when local optimal choices lead to global optimum — verify the greedy property first
✅ Backtracking: Best for generating all valid combinations or exhaustive search — exponential time
✅ Pattern recognition is a skill: The more problems you solve, the faster you recognize patterns
✅ Start with brute force: Get a working solution, then optimize using the right pattern

Next Steps

Now that you know the essential problem-solving patterns, you're ready to apply them to specific data structures:

Continue the DSA series:

Arrays & Strings — The Foundation - Apply patterns to array and string problems
Linked Lists — Dynamic Sequential Data - Two pointers in linked lists

Back to roadmap:

Data Structures & Algorithms Roadmap - Complete learning path

Practice Resources:

LeetCode Patterns - Filter by topic and difficulty
NeetCode 150 - Curated problems organized by pattern
Grind 75 - Time-optimized study plan

Part of the Data Structures & Algorithms Roadmap series

Introduction

What You'll Learn

Prerequisites

1. The Problem-Solving Framework

The UMPIRE Method

Example: Applying the Framework

2. Two Pointers

How It Works

Pattern 1: Pair Sum in Sorted Array

Pattern 2: Remove Duplicates In-Place

Pattern 3: Palindrome Check

When to Recognize Two Pointers

3. Sliding Window

How It Works

Pattern 1: Maximum Sum of k Consecutive Elements (Fixed Window)

Pattern 2: Longest Substring Without Repeating Characters (Variable Window)

Pattern 3: Smallest Subarray with Sum ≥ Target (Variable Window)

When to Recognize Sliding Window

4. Hash Maps for Fast Lookups

How It Works

Pattern 1: Two Sum (Unsorted Array)

Pattern 2: Frequency Counting

Pattern 3: Group By Property

When to Recognize Hash Map

5. Prefix Sum

How It Works

Pattern 1: Range Sum Query

Pattern 2: Subarray Sum Equals K

When to Recognize Prefix Sum

6. Divide and Conquer

How It Works

Pattern 1: Merge Sort

Pattern 2: Maximum Subarray (Kadane's vs Divide and Conquer)

When to Recognize Divide and Conquer

7. Greedy Approach

How It Works

Pattern 1: Maximum Subarray (Kadane's Algorithm)

Pattern 2: Activity Selection / Interval Scheduling

When to Recognize Greedy

8. Recursion and Backtracking

How It Works

Pattern 1: Generate All Subsets (Power Set)

Pattern 2: Generate Permutations

Pattern 3: Valid Parentheses Generation

The Backtracking Template

When to Recognize Backtracking

9. Pattern Recognition Cheat Sheet

By Problem Type

By Keywords in Problem Statement

10. Practice Problems

Two Pointers

Sliding Window

Hash Map

Prefix Sum

Greedy

Backtracking

Summary and Key Takeaways

Next Steps

📬 Subscribe to Newsletter

💬 Comments