Algorithmic challenges are a staple of modern tech interviews, and not just at FAANG companies. A deep understanding of common problem-solving patterns is a crucial advantage for any developer. This guide breaks down 15 essential patterns that will sharpen your skills and help you tackle unfamiliar problems with confidence.

After solving over 1,500 LeetCode problems, the author of the original guide learned a crucial lesson:

Success on LeetCode isn't about the number of problems you solve, but the number of patterns you recognize.

Recognizing these patterns allows you to solve more problems in less time and quickly identify the right approach for unfamiliar challenges. We'll explore each pattern with clear explanations, use cases, and links to practice problems on LeetCode to solidify your understanding.

1. Prefix Sum

Pattern 1: Prefix Sum

The Prefix Sum pattern involves pre-processing an array to create a new one where each element at index `i` is the sum of all elements from the start up to `i`. This allows for highly efficient querying of subarray sums.

When to use: Ideal for problems requiring multiple sum queries on a subarray or the calculation of cumulative totals.

Example Problem

Given an array nums, calculate the sum of elements between indices `i` and `j`.

Input: nums = [1, 2, 3, 4, 5, 6], i = 1, j = 3
Output: 9

Explanation: First, create a prefix sum array: P = [1, 3, 6, 10, 15, 21]. The sum for the range [i, j] is then calculated as P[j] - P[i-1] (for i > 0).

Recommended Problems:

Java Solution Example: Link

2. Two Pointers

Pattern 2: Two Pointers

The Two Pointers pattern uses two pointers to iterate through an array or list. They can move towards each other, away from each other, or in the same direction at different speeds. It's often used to find pairs of elements that satisfy a specific condition.

When to use: Perfect for sorted arrays or lists where you need to find pairs that meet a condition, such as summing to a target value.

Example Problem

Find two numbers in a sorted array whose sum equals a given target value.

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

Explanation: Initialize pointers: left = 0, right = nums.length – 1.
If the sum is less than the target, move left to the right to increase the sum.
If the sum is greater than the target, move right to the left to decrease the sum.
Repeat until the pair is found or the pointers cross.

Recommended Problems:

Two Sum II - Input Array is Sorted (LeetCode #167)
3Sum (LeetCode #15)
Container With Most Water (LeetCode #11)

Java Solution Example: Link

3. Sliding Window

Pattern 3: Sliding Window

The Sliding Window pattern is used to find a subarray or substring that satisfies a certain condition. It optimizes time complexity by maintaining a 'window' of a fixed or variable size that slides over the data.

When to use: When dealing with problems involving continuous subarrays or substrings, like finding the maximum sum or longest substring.

Example Problem

Find the maximum sum of any contiguous subarray of size `k`.

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9 (from subarray [5, 1, 3])

Explanation: Calculate the sum of the first `k` elements. Then, 'slide' the window by subtracting the element leaving the window and adding the new element entering it, tracking the maximum sum found.

Recommended Problems:

Java Solution Example: Link

4. Fast & Slow Pointers

Pattern 4: Fast & Slow Pointers

This pattern, also known as the 'tortoise and hare' algorithm, uses two pointers that move through a sequence at different speeds. It is commonly used to detect cycles in linked lists and other data structures.

When to use: For detecting cycles, finding the middle of a linked list, or solving other problems involving cyclic structures.

Example Problem

Determine if a linked list contains a cycle.

Explanation: Initialize a slow pointer (moves one step at a time) and a fast pointer (moves two steps). If the pointers ever meet, a cycle exists. If the fast pointer reaches the end of the list, there is no cycle.

Recommended Problems:

Java Solution Example: Link

5. In-place Reversal of a Linked List

Pattern 5: In-place Reversal of a Linked List

Pattern 5: In-place Reversal of a Linked List

This pattern allows you to reverse a portion of a linked list without using any additional memory space.

When to use: When you need to reverse a sublist or an entire list 'in-place'.

Example Problem

Reverse a sublist from position `m` to `n`.

Input: head = [1, 2, 3, 4, 5], m = 2, n = 4
Output: [1, 4, 3, 2, 5]

Explanation: Identify the nodes before `m` and after `n`. Then, reverse the pointers of the nodes between them, carefully re-linking the reversed portion to the rest of the list.

Recommended Problems:

Java Solution Example: Link

6. Monotonic Stack

Pattern 6: Monotonic Stack

A monotonic stack maintains its elements in a strictly increasing or decreasing order. It's often used to find the next greater/smaller element for each item in an array.

When to use: When you need to find the nearest greater/smaller element to the left or right of each element in an array.

Example Problem

For each element in an array, find the next greater element. If none exists, use -1.

Input: nums = [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]

Explanation: Use a stack to keep track of elements for which we haven't found a next greater element. Iterate through the array. For each element, pop from the stack until you find an element that is greater, establishing the result for the popped items.

Recommended Problems:

Java Solution Example: Link

7. Top 'K' Elements

Pattern 7: Top 'K' Elements

This pattern involves finding the K largest or smallest elements in a collection, typically using a min-heap or max-heap.

When to use: For finding the median, top K frequent elements, or Kth largest/smallest item in a stream of data.

Example Problem

Find the Kth largest element in an unsorted array.

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Explanation: Use a min-heap of size `k`. Iterate through the array, adding elements to the heap. If the heap's size exceeds `k`, remove the smallest element. The root of the heap will be the Kth largest element.

Recommended Problems:

Java Solution Example: Link

8. Overlapping Intervals

Pattern 8: Overlapping Intervals

This pattern is used for merging or processing intervals that intersect with one another.

When to use: When working with schedules, time ranges, or merging overlapping data ranges.

Example Problem

Merge all overlapping intervals in a collection.

Input: [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]

Explanation: Sort the intervals by their start time. Iterate through the sorted intervals, merging the current interval with the previous one if they overlap. If they don't overlap, add the current interval as a new one to the result list.

Recommended Problems:

Java Solution Example: Link

9. Modified Binary Search

Pattern 9: Modified Binary Search

This is an adaptation of the classic binary search algorithm for scenarios like rotated sorted arrays or finding the boundaries of elements.

When to use: For searching in sorted or rotated arrays where a standard binary search won't work directly.

Example Problem

Find a target element in a rotated sorted array.

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4 (index)

Explanation: Perform a binary search, but with an additional check to determine which half of the current search space is sorted. Then, check if the target lies within the sorted half to decide where to continue the search.

Recommended Problems:

Java Solution Example: Link

10. Binary Tree Traversal

Pattern 10: Binary Tree Traversal

This pattern involves visiting all nodes in a tree in a specific order. The three primary methods are:

Pre-order: Root → Left → Right
In-order: Left → Root → Right
Post-order: Left → Right → Root

When to use: Fundamental to almost all tree-based problems.

Example Problem

Perform an in-order traversal of a binary tree.

Input: root = [1, null, 2, 3]
Output: [1, 3, 2]

Explanation: For an in-order traversal, nodes are visited in Left, Root, Right order. This can be implemented using recursion or a stack.

Recommended Problems:

Pre-order → Binary Tree Paths (LeetCode #257)
In-order → Kth Smallest Element in a BST (LeetCode #230)
Post-order → Binary Tree Maximum Path Sum (LeetCode #124)

Java Solution Example: Link

11. Depth-First Search (DFS)

Pattern 11: Depth-First Search

Depth-First Search (DFS) explores as far as possible along each branch before backtracking. It's often implemented recursively or with a stack.

When to use: For traversing all paths, generating combinations, and solving recursive problems on trees or graphs.

Example Problem

Find all root-to-leaf paths in a binary tree.

Input: root = [1,2,3,null,5]
Output: [1->2->5, 1->3]

Explanation: Use recursion or a stack to traverse each path from the root to a leaf node, recording each path along the way.

Recommended Problems:

Java Solution Example: Link

12. Breadth-First Search (BFS)

Pattern 12: Breadth-First Search

Breadth-First Search (BFS) explores nodes level by level in a tree or graph. It is typically implemented with a queue.

When to use: For finding the shortest path in an unweighted graph or for level-order traversal of a tree.

Example Problem

Perform a level-order traversal of a binary tree.

Input: root = [3,9,20,null,null,15,7]
Output: [[3], [9,20], [15,7]]

Explanation: Use a queue to keep track of nodes at each level. Traverse each level and add the children of the current nodes to the queue for the next level.

Recommended Problems:

Java Solution Example: Link

13. Matrix Traversal

Pattern 13: Matrix Traversal

This involves traversing elements in a 2D matrix using techniques like DFS, BFS, or spiral traversal.

When to use: For problems involving a grid or matrix, such as finding islands, flood fill operations, or searching.

Example Problem

Perform a 'flood fill' operation: change the color of all connected cells of the same color, starting from a given cell.

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Explanation: Use DFS or BFS to navigate the matrix starting from the given cell, changing the color of all connected cells with the same initial color.

Recommended Problems:

Java Solution Example: Link

14. Backtracking

Pattern 14: Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point in time (i.e., 'backtracking').

When to use: For problems involving permutations, combinations, subsets, or solving puzzles like Sudoku and N-Queens.

Example Problem

Generate all possible permutations of a list.

Input: nums = [1,2,3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Explanation: Use recursion to build permutations. For each element, include it in the current permutation and recursively generate the remaining permutations. Backtrack once all permutations for a given path are generated.

Recommended Problems:

Java Solution Example: Link

15. Dynamic Programming

Pattern 15: Dynamic Programming

Dynamic Programming (DP) breaks down a complex problem into simpler subproblems, solving each subproblem just once and storing their solutions to avoid redundant computations.

When to use: When a problem has overlapping subproblems and an optimal substructure.

Common DP Subtypes

Fibonacci-style problems
0/1 Knapsack
Longest Common Subsequence (LCS)
Longest Increasing Subsequence (LIS)

Example Problem

Find the nth Fibonacci number.

Input: n = 5
Output: 5 (The sequence is 0, 1, 1, 2, 3, 5)

Explanation: Use a bottom-up approach (tabulation) to calculate the nth Fibonacci number. Start with the first two numbers (0 and 1) and iterate to compute subsequent numbers using the formula dp[i] = dp[i - 1] + dp[i - 2].

Recommended Problems:

#leetcode #interview