Master LeetCode: 15 Essential Patterns Explained in Under 10 Minutes

Having solved over 1500 LeetCode problems, if there is one thing I have learned, it is this: LeetCode is less about the number of problems you have solved and more about how many patterns you know. Learning patterns allows you to solve a wide variety of problems in less time and helps you quickly identify the right approach to a problem you have never seen before. In this article, I will walk you through 15 of the most important patterns I learned that made my LeetCode journey a lot less painful. The best part is these patterns frequently appear in technical interviews.

For each pattern, I will explain when to use it, walk through an example, and list code problems you can practice to learn them better.

1. Prefix Sum

This pattern is commonly used for problems where you need to query the sum of elements in a subarray. Imagine you are given an array and you need to find the sum of all elements between indices i and j. If you have just one query, you can simply loop through the array in linear time. However, with multiple queries, this can take up to O(n * m) time, where m is the number of queries and n is the length of the array.

To make such queries faster, you can create a prefix sum array, where the value at index i is the sum of all elements from the start up to index i. Now, you can answer range sum queries in O(1) time using the formula:

sum(i, j) = prefix_sum[j] - prefix_sum[i-1]

Note: You don't always need a new array for prefix sums; sometimes you can use the input array itself to avoid using extra space. You can practice this pattern by solving various problems available on platforms like LeetCode.

2. Two Pointers

In the two-pointer approach, we initialize two variables and move them toward or away from each other based on the problem's requirements. For example, let's say you are given a string and need to check whether it's a palindrome.

To solve this, use one pointer at the beginning and the other at the end. At each step, compare the characters at both pointers. If they don't match, the string is not a palindrome. If they do match, move the pointers closer until they meet. The two-pointers pattern can reduce the time complexity for many problems from O(n²) to O(n). You can find several problems on LeetCode to get better at this pattern.

3. Sliding Window

This pattern helps us find subarrays or substrings that meet a specific criterion. Suppose you're given an array and need to find a subarray of size k with the maximum sum. A brute-force approach would consider all subarrays of size k, leading to a time complexity of O(n * k).

We can optimize this using the sliding window approach. We start by initializing a window containing the sum of the first k elements. As we iterate through the array, we slide the window by subtracting the leftmost item and adding the new item's value, updating the result along the way. This reduces the time complexity to O(n). There are many LeetCode problems to practice this approach.

4. Fast and Slow Pointers

This pattern, a variant of two pointers, helps solve problems involving linked lists and arrays, particularly for finding cycles. It works by moving two pointers at different speeds. Imagine a circular track with two runners; if one runs faster, they will eventually lap the slower one.

Using this approach, you can check if a linked list contains a cycle. 1. Place both slow and fast pointers at the head. 2. Move the slow pointer one node at a time and the fast pointer two nodes at a time. 3. If there is a cycle, they will eventually meet.

This pattern can also find the middle node of a linked list in a single pass. When the fast pointer reaches the end, the slow pointer will be at the middle. To get better at this pattern, you can practice various linked list problems online.

5. Linked List In-place Reversal

Many linked list problems ask you to change nodes and pointers without using extra space. Let's look at an example where you need to reverse a linked list. A simple approach is to copy the values into an array and then update the list, but this requires extra space.

We can do it in one pass without extra space using three pointers: previous, current, and next. 1. Set previous to null and current to the head. 2. Loop until current is null. 3. In each loop, set next to current.next. 4. Reverse the current node's pointer to point to previous. 5. Move previous to current and current to next.

At the end, previous will point to the new head. You can find multiple problems on LeetCode to practice this pattern.

6. Monotonic Stack

This pattern uses a stack to find the next greater or smaller element in an array. For instance, given an array, find the next greater element for each item. A brute-force approach takes O(n²) time. We can solve it in O(n) time using a stack.

The algorithm looks like this: 1. Use a stack to track indices of elements for which we haven't found the next greater element. 2. Initialize the result array with -1s. 3. For each element, check if it's greater than the element at the top of the stack. If it is, pop from the stack and set the result for that index to the current element. 4. Push the current element's index onto the stack.

This process keeps the stack elements in decreasing order. For finding the next smaller element, keep them in increasing order. You can practice this pattern on LeetCode.

7. Top K Elements

This pattern helps you find the k largest, smallest, or most frequent elements. Imagine you need to find the three largest elements in an array. Sorting takes O(n log n) time. We can do better using a min-heap.

By using a min-heap, we can keep track of the three largest elements as we loop through the array. 1. Put the first k elements into a min-heap. 2. For every subsequent element, compare it with the top heap element. 3. If the current element is greater, pop the top element and push the new one.

This reduces the time complexity to O(n log k). For finding the k largest elements, use a min-heap; for k smallest, use a max-heap. You can find numerous problems to practice this pattern.

8. Overlapping Intervals

This pattern is useful for problems involving intervals or ranges that may overlap. Common problem types include: * Merging Intervals: Given a collection of intervals, merge all overlapping ones. * Interval Intersection: Find the intersection between two sets of intervals. * Insert Interval: Add a new interval to a list of non-overlapping intervals.

To merge overlapping intervals: 1. Start by sorting the intervals by their start time. 2. Create an empty list to store the merged intervals. 3. Iterate through the intervals. If an interval overlaps with the last one in the merged list, update the end time. Otherwise, add it as a new interval.

To get better at this pattern, try solving related problems on LeetCode.

9. Modified Binary Search

This is a variant of the standard binary search algorithm used when an array isn't perfectly sorted. It's useful for: * Searching in a nearly sorted or rotated sorted array. * Searching in a list with an unknown length. * Finding the first or last occurrence of an element.

For example, in a rotated sorted array, you can perform a binary search with an additional check to determine which half of the array is sorted, then search within that half. You can practice this approach with various search-related problems.

10. Binary Tree Traversal

Binary trees are all about traversing them in a specific order. The four popular ways are: * Pre-order, In-order, Post-order: These are easily implemented with recursion, while the iterative versions require a stack. * Level-order: This explores nodes level by level and is implemented with a queue.

When to use each: * In-order: To retrieve values from a BST in sorted order. * Pre-order: To copy a tree or for serialization. * Post-order: To process child nodes before the parent (e.g., deleting a tree). * Level-order: To explore all nodes at the current level before moving to the next.

You can solve many tree problems on LeetCode to master these traversals.

11. Depth First Search (DFS)

DFS is used to explore all paths or branches in graphs or trees. It's ideal for problems like: * Finding a path between two nodes. * Checking for cycles in a graph. * Finding the topological order in a directed acyclic graph. * Counting connected components.

DFS can be implemented recursively or iteratively using a stack. The generic approach involves choosing a starting point, keeping track of visited nodes to avoid cycles, and exploring unvisited neighbors. There are many LeetCode problems to practice this pattern.

12. Breadth First Search (BFS)

BFS is a traversal technique that explores nodes level by level. It is very useful for: * Finding the shortest path between two nodes in an unweighted graph. * Printing all nodes of a tree level by level. * Finding all connected components in a graph.

To implement BFS, we use a queue. The generic approach involves adding a starting node to the queue, tracking visited nodes, and processing nodes level by level until the queue is empty. You can practice using this approach on LeetCode.

13. Matrix Traversal

Most matrix traversal problems can be seen as graph problems. In a matrix (a 2D array), the cells are nodes, and you can move to adjacent cells (horizontally, vertically, or diagonally). You can use graph algorithms like DFS and BFS to solve matrix problems.

Consider the "island count" problem, where you count groups of connected '1's in a grid. 1. Iterate through each cell. 2. If you find a land cell ('1'), you've found a new island. 3. Explore this island using DFS or BFS, marking all connected land cells as visited. 4. Increment your island count and continue.

You can practice this approach with various grid and matrix problems.

14. Backtracking

Backtracking is a powerful technique for solving problems that involve exploring all potential solution paths and reversing course when a path doesn't lead to a valid solution. It's used to: * Generate all possible permutations or combinations. * Solve puzzles like Sudoku or the N-Queens problem. * Find all possible paths in a graph or maze.

For example, to generate all subsets of an array, you can use backtracking. Start with an empty subset. For each element, you have two choices: include it or not. After making a choice, recurse to the next element and backtrack to explore other possibilities. You can practice these problems online.

15. Dynamic Programming (DP)

DP is a technique for solving optimization problems by breaking them down into smaller subproblems and storing their solutions to avoid re-computation. It is useful for problems with overlapping subproblems and optimal substructure properties.

Common DP patterns include: * Fibonacci Numbers * 0/1 Knapsack * Longest Common Subsequence * Longest Increasing Subsequence * Subset Sum * Matrix Chain Multiplication

Dynamic programming is a challenging topic, but learning these common patterns can make it much more approachable. You can find numerous problems on LeetCode to learn these patterns.