Mastering 15 Common Patterns in LeetCode Problems

LeetCode problems often follow certain patterns that can be key to solving a wide variety of coding challenges. Understanding and recognizing these patterns will enable you to approach problems more systematically and efficiently. This post provides a concise introduction to 15 common patterns, along with links to in-depth explanations and examples for each. Whether you're a beginner or looking to solidify your problem-solving skills, these patterns will be a crucial part of your LeetCode toolkit.

1. Sliding Window

The sliding window technique is essential for solving problems involving contiguous subarrays or substrings. It is often used to find the maximum sum of a subarray of fixed length, or the longest substring without repeating characters.

Common Use Cases: Maximum subarray problems, substring problems, dynamic-sized window problems.

2. Two Pointers

The two pointers pattern simplifies array problems where two indices are required to move towards a target, such as finding pairs in a sorted array that sum to a specific value or merging sorted arrays.

Common Use Cases: Sorted arrays, pair problems, or problems requiring partitioning.

3. Fast and Slow Pointers

This pattern is most often used in linked list problems. A slow pointer moves one step at a time, while a fast pointer moves two steps, making it perfect for cycle detection or finding the middle node of a list.

Common Use Cases: Detecting cycles, middle of a linked list, palindrome linked lists.

4. Depth-First Search (DFS)

DFS is a recursive algorithm used to explore all possible paths in tree or graph traversal problems. It digs deep into a branch before backtracking, making it ideal for problems where exploring all solutions is necessary, like generating all combinations.

Common Use Cases: Graph/tree traversal, connected components, backtracking problems.

5. Breadth-First Search (BFS)

BFS explores all nodes at the present depth before moving on to the nodes at the next depth level. It is perfect for shortest path problems in unweighted graphs or level-order traversal in trees.

Common Use Cases: Shortest path in unweighted graphs, level-order traversal in trees.

6. Binary Search

Binary Search is the go-to algorithm for efficient searching in sorted arrays. It divides the search space in half at each step, making it highly efficient for solving problems with logarithmic time complexity.

Common Use Cases: Searching in sorted arrays, optimization problems, square root computation.

7. Backtracking

Backtracking explores all possibilities by making a choice, exploring it fully, and then unmaking it to try another path. It is widely used in permutation, combination, and subset problems like the N-Queens problem or Sudoku.

Common Use Cases: N-Queens, Sudoku, permutation, and combination generation.

8. Dynamic Programming (DP)

Dynamic Programming breaks a problem into overlapping subproblems, solving each subproblem just once and storing the results. It's crucial in optimization problems such as the Knapsack problem or calculating the longest increasing subsequence.

Common Use Cases: Knapsack, longest common subsequence, Fibonacci sequence, coin change.

9. Greedy Algorithm

A Greedy Algorithm makes the optimal choice at each step to ensure a locally optimal solution, hoping that it leads to a globally optimal solution. It's commonly used in problems like interval scheduling or finding the minimum number of platforms for train arrivals.

Common Use Cases: Scheduling problems, interval problems, coin change (minimizing coins).

10. Topological Sort

Topological Sort is a sorting technique for directed acyclic graphs (DAGs), often used in dependency resolution problems. It is particularly useful in course scheduling or task scheduling problems where certain tasks depend on others.

Common Use Cases: Course scheduling, task scheduling, dependency resolution.

11. In-Place Reversal of a Linked List

This technique is used to reverse linked lists without using extra space. It often appears in problems like reversing a sublist of a linked list or rotating parts of a list in place.

Common Use Cases: Reversing a linked list, reversing a sublist, palindrome check for linked lists.

12. Monotonic Stack

A Monotonic Stack is used to maintain elements in a sorted order while processing an array. It is highly effective in problems involving ranges, such as finding the next greater element or solving the daily temperatures problem.

Common Use Cases: Next greater element, stock span problem, daily temperatures.

13. Trie

A Trie is a tree-like data structure used for storing strings efficiently. It supports fast prefix queries, making it useful in applications like autocomplete or solving word search problems.

Common Use Cases: Autocomplete, prefix matching, word search.

14. Union-Find

The Union-Find algorithm, also known as Disjoint Set Union (DSU), is used to solve connectivity problems. It is effective in determining whether elements are in the same set, often used in problems like finding the number of connected components in a grid.

Common Use Cases: Connected components, cycle detection in graphs, number of islands.

15. Divide and Conquer

Divide and Conquer is a powerful algorithmic technique that recursively breaks a problem into subproblems, solves each, and then combines them. It is frequently used in sorting algorithms like merge sort and solving the maximum subarray sum problem.

Common Use Cases: Merge sort, quick sort, maximum subarray problem.