ADVANCE WARNING - Don’t confuse LeetCode Patterns with Design Patterns.
They are two completely different concepts.
These patterns are not design patterns, but LeetCode patterns that recur in LeetCode problems again and again.
The Credit for the LeetCode Patterns Idea
As far as I can research into the past, these patterns have been listed before, at the following links.
-
"Patterns for Coding Questions" by Educative.io (2020)
This course covers various patterns for solving coding problems, including LeetCode problems.
-
"10 Common LeetCode Questions You Should Know By Heart" by Byte by Byte (2019)
This article discusses 10 common LeetCode patterns, including Two Pointers, Sliding Window, Binary Search, and more.
-
"LeetCode Patterns" by Neetcode (2021)
Neetcode's website and YouTube channel provide detailed explanations of different patterns for solving LeetCode problems.
-
"Patterns for Solving LeetCode Problems" by Clement Mihailescu (2021)
In this video, Clement Mihailescu discusses common patterns and strategies for solving LeetCode problems.
-
"LeetCode Patterns: A Comprehensive Guide" by Geeks for Geeks (2022)
This article on Geeks for Geeks covers various patterns for solving LeetCode problems, including examples and explanations.
But they have all neglected one thing.
In order to make their articles short, they have not included complete detailed source code solutions and explanations for all ten patterns.
Well - that’s what this article does.
We list:
-
The Pattern
-
A Sample Question that Utilizes the Pattern
-
The Source Code Solution in Python
-
An Explanation of the Source Code For Beginners with Analysis
-
Ten Other LeetCode Questions that the Pattern Applies To
As you can clearly see, if you are a beginner, and you want to ace LeetCode as efficiently as possible, you have struck solid gold in this article!
Let’s get started.
Ten LeetCode Patterns that Solve over 1000 LeetCode Problems
1. Two Pointers
Pattern Outline
The two-pointer technique involves using two indices (or pointers) to traverse an array or list.
This approach is often used to solve problems involving pairs, subarrays, or certain conditions that require comparison between two elements.
Sample LeetCode Problem
Problem:
15. 3Sum Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Solution
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # Skip duplicates
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # Skip duplicates
while left < right and nums[right] == nums[right - 1]:
right -= 1 # Skip duplicates
left += 1
right -= 1
return result
Explanation
In this solution, we first sort the input list to make it easier to avoid duplicates and to apply the two-pointer technique effectively.
We iterate through the sorted list with one pointer (i) and use two additional pointers (left and right) to find pairs that sum to zero with the current number.
If the sum is less than zero, we move the left pointer to the right to increase the sum.
If the sum is greater than zero, we move the right pointer to the left to decrease the sum.
When we find a valid triplet, we store it in the result list and skip over duplicate values to ensure unique triplets.
Time Complexity
• O(n^2): The outer loop runs in O(n) and the inner while loop also runs in O(n) in the worst case.
Space Complexity
• O(1):
We are using a constant amount of space for pointers and results, not counting the output list.
Ten Similar LeetCode Problems
- Trapping Rain Water - 42
- Remove Duplicates from Sorted Array - 26
- Remove Element - 27
- Reverse String - 344
- Container With Most Water - 11
- Remove Nth Node From End of List - 19
- Minimum Window Substring - 76
- Two Sum II - Input Array Is Sorted - 167
- 3Sum - 15
- 4Sum - 18
2. Sliding Window
Pattern Outline
The sliding window technique is used to maintain a subset of elements within a larger dataset, allowing for dynamic adjustments to the size of the window.
This is particularly useful for problems involving contiguous subarrays or substrings.
Sample LeetCode Problem
Problem: 3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Solution
def lengthOfLongestSubstring(s: str) -> int:
char_map = {}
left = 0
max_length = 0
for right in range(len(s)):
if s[right] in char_map:
left = max(left, char_map[s[right]] + 1) # Move left pointer
char_map[s[right]] = right # Update the last seen index
max_length = max(max_length, right - left + 1) # Update max length
return max_length
Explanation
This solution uses a sliding window to track the longest substring without repeating characters.
We maintain a dictionary (char_map) to store the last seen index of each character.
As we iterate through the string with the right pointer, we check if the current character has been seen before.
If it has, we move the left pointer to the right of the last occurrence of that character to ensure all characters in the current window are unique.
We continuously update the maximum length of the substring found.
Time Complexity
• O(n): Each character is processed at most twice (once by the right pointer and once by the left pointer).
Space Complexity
• O(min(n, m)): Where n is the size of the input string and m is the size of the character set (e.g., 26 for lowercase English letters).
Ten Similar LeetCode Problems
- Minimum Window Substring - 76
- Minimum Size Subarray Sum - 209
- Find All Anagrams in a String - 438
- Permutation in String - 567
- Max Consecutive Ones III - 1004
- Longest Repeating Character Replacement - 424
- Substring with Concatenation of All Words - 30
- Longest Substring with At Most Two Distinct Characters - 159
- Longest Substring with At Most K Distinct Characters - 340
- Longest Substring Without Repeating Characters - 3
3. Binary Search
Pattern Outline
Binary search is an efficient algorithm for finding a target value within a sorted array.
By repeatedly dividing the search interval in half, it reduces the time complexity significantly compared to linear search.
Sample LeetCode Problem
Problem: 33. Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums, nums, ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Solution
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
if nums[left] <= nums[mid] or target > nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if nums[mid] > nums[right] or target < nums[left]:
right = mid - 1
else:
left = mid + 1
return -1
Explanation
In this binary search solution, we start with two pointers, left and right, that define the current search interval.
We calculate the middle index (mid) and compare the middle element with the target.
If the middle element is equal to the target, we return the index.
If the middle element is less than the target, we determine which half of the rotated sorted array the target could be in based on the middle
element and the left pointer.
If the target could be in the right half, we search the right half by moving the left pointer.
If it's in the left half, we search the left half by moving the right pointer.
If the middle element is greater than the target, we determine which half the target could be in based on the middle element and the right pointer and adjust the pointers accordingly.
This process continues until we find the target or exhaust the search space.
Time Complexity
• O(log n): The search space is halved with each iteration.
Space Complexity
• O(1): We are using a constant amount of space for pointers.
Ten Similar LeetCode Problems
- Search Insert Position - 35
- Find Peak Element - 162
- First Bad Version - 278
- Arranging Coins - 441
- Find Minimum in Rotated Sorted Array - 153
- Sqrt(x) - 69
- Split Array Largest Sum - 410
- Koko Eating Bananas - 875
- Find First and Last Position of Element in Sorted Array - 34
- Find Smallest Letter Greater Than Target - 744
4. Depth-First Search (DFS)
Pattern Outline
Depth-First Search (DFS) is a traversal method used for exploring trees and graphs.
It explores as far down a branch as possible before backtracking, making it useful for problems that require exploring all possible paths.
Sample LeetCode Problem
Problem: 200. Number of Islands
Given an m x n 2D binary grid grid where 0 represents water and 1 represents land, return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Solution
def numIslands(grid):
if not grid:
return 0
def dfs(i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
return
grid[i][j] = '0' # Mark as visited
dfs(i + 1, j) # Down
dfs(i - 1, j) # Up
dfs(i, j + 1) # Right
dfs(i, j - 1) # Left
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1 # Increment count for each island found
return count
Explanation
This DFS solution counts the number of islands in a 2D grid where '1' represents land and '0' represents water.
We iterate through each cell in the grid, and when we find a '1', we initiate a DFS to mark all connected land cells as visited by changing them to '0'.
Each time we start a DFS, we increment our island count.
The DFS explores all four directions (up, down, left, right) from the current cell.
Time Complexity
• O(m * n): Where m is the number of rows and n is the number of columns in the grid. Each cell is visited once.
Space Complexity
• O(m * n): In the worst case, the recursion stack could go as deep as the number of cells in the grid.
Ten Similar LeetCode Problems
- Maximum Depth of Binary Tree - 104
- Same Tree - 100
- Symmetric Tree - 101
- Invert Binary Tree - 226
- Binary Tree Paths - 257
- Binary Tree Postorder Traversal - 145
- Binary Tree Inorder Traversal - 94
- Binary Tree Level Order Traversal - 102
- Path Sum - 112
- Path Sum II - 113
5. Breadth-First Search (BFS)
Pattern Outline
Breadth-First Search (BFS) is a traversal method that explores all neighbors at the present depth before moving on to nodes at the next depth level.
This is particularly effective for finding the shortest path in unweighted graphs.
Sample LeetCode Problem
Problem: 542. 0-1 Matrix
Given an m x n binary matrix mat where each 0 marks the sea and each 1 marks the land. If a cell is surrounded by land, it is called a normal cell.
If a cell is on the border of the grid or surrounded by the sea, it is called a special cell.
Return an m x n matrix representing the distance of each cell from the nearest special cell.
If a normal cell is unreachable from any special cell, it is assigned with -1.
Solution
from collections import deque
def updateMatrix(mat):
if not mat:
return []
rows, cols = len(mat), len(mat[0])
queue = deque()
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# Initialize the queue with all '0' positions
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
queue.append((r, c))
else:
mat[r][c] = float('inf') # Set distance to infinity for '1's
# BFS to update distances
while queue:
r, c = queue.popleft()
for dr, dc in directions:
new_r, new_c = r + dr, c + dc
if 0 <= new_r < rows and 0 <= new_c < cols:
if mat[new_r][new_c] > mat[r][c] + 1:
mat[new_r][new_c] = mat[r][c] + 1
queue.append((new_r, new_c))
return mat
Explanation
In this BFS solution, we aim to update each cell in a binary matrix to reflect the distance to the nearest '0'.
We initialize a queue with all the positions of '0's and set all '1's to infinity, representing an unvisited state.
We then perform BFS by dequeuing a position, checking its neighbors, and updating their distances if a shorter path is found.
The process continues until all reachable cells are updated with the correct distances.
Time Complexity
• O(m * n): Each cell is processed once.
Space Complexity
• O(m * n): The queue can store up to all cells in the worst case.
Ten Similar LeetCode Problems
- Number of Islands - 200
- Rotting Oranges - 994
- Word Ladder - 127
- Find Largest Value in Each Tree Row - 515
- Populating Next Right Pointers in Each Node - 116
- Binary Tree Right Side View - 199
- Minimum Height Trees - 310
- All Nodes Distance K in Binary Tree - 863
- 01 Matrix - 542
- Rotting Oranges - 994
6. Backtracking
Pattern Outline
Backtracking is a problem-solving technique that involves building a solution incrementally and abandoning paths that fail to satisfy the constraints of the problem.
It is often used for generating combinations, permutations, or solving constraint satisfaction problems.
Sample LeetCode Problem
Problem: 46. Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Solution
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path)
return
for i in range(len(remaining)):
backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
backtrack([], nums)
return result
Explanation
This backtracking solution generates all possible permutations of a list of numbers.
The backtrack function takes two parameters: the current path (the current permutation being built) and the remaining numbers that can still be added.
If there are no remaining numbers, we add the current path to the results.
For each number in the remaining list, we recursively call backtrack, adding that number to the path and removing it from the remaining list.
This process continues until all permutations are found.
Time Complexity
• O(n!): The number of permutations of n elements is n!.
Space Complexity
• O(n): The space used for the recursion stack and the result list.
Ten Similar LeetCode Problems
- Combination Sum - 39
- Combination Sum II - 40
- N-Queens - 51
- N-Queens II - 52
- Combinations - 77
- Combination Sum III - 216
- Subsets - 78
- Permutations II - 47
- Palindrome Partitioning - 131
- Subsets II - 90
7. Dynamic Programming
Pattern Outline
Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations.
It is particularly useful for optimization problems.
Sample LeetCode Problem
Problem: 198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Solution
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
Explanation
In this dynamic programming solution, we determine the maximum amount of money that can be robbed without alerting the police (i.e., not robbing two adjacent houses).
We maintain a list dp where dp[i] represents the maximum amount that can be robbed from the first i houses.
The recurrence relation is that for each house, we can either skip it (take the maximum from the previous house) or rob it (add its value to the maximum from two houses before).
The final answer is found in dp[-1], which represents the maximum amount that can be robbed from all houses.
Time Complexity
• O(n): We iterate through the list of houses once.
Space Complexity
• O(n): We use an array to store the maximum amounts for each house.
Ten Similar LeetCode Problems
- Longest Increasing Subsequence - 300
- Unique Paths - 62
- Unique Paths II - 63
- Climbing Stairs - 70
- Fibonacci Number - 509
- Coin Change - 322
- Partition Equal Subset Sum - 416
- Word Break - 139 • Paint House - 256
- House Robber II - 213
8. Greedy Algorithms
Pattern Outline
Greedy algorithms make the locally optimal choice at each step with the hope of finding a global optimum.
They are often used in optimization problems where a local optimum leads to a global optimum.
Sample LeetCode Problem
Problem: 55. Jump Game You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, and false otherwise.
Solution
def canJump(nums):
max_reachable = 0
for i in range(len(nums)):
if i > max_reachable:
return False # Can't reach this index
max_reachable = max(max_reachable, i + nums[i])
if max_reachable >= len(nums) - 1:
return True # Can reach the last index
return False
Explanation
In this greedy solution, we determine whether we can reach the last index of the array from the first index.
We maintain a variable max_reachable that tracks the farthest index we can reach at any point.
As we iterate through the array, if we encounter an index that is beyond max_reachable, we return False, indicating that we cannot reach that index.
If at any point max_reachable meets or exceeds the last index, we return True, indicating that reaching the end is possible.
Time Complexity
• O(n): We iterate through the list once.
Space Complexity
• O(1): We use a constant amount of space for variables.
Ten Similar LeetCode Problems
-
Jump Game II - 45
-
Task Scheduler - 621
-
Is Subsequence - 392
-
Candy - 135
-
Queue Reconstruction by Height - 406
-
Partition Labels - 763
-
Two City Scheduling - 1029
-
Non-overlapping Intervals - 435
-
Minimum Number of Arrows to Burst Balloons - 452
-
Jump Game - 55
9. Hashing
Pattern Outline
Hashing involves using hash tables to store and quickly retrieve data.
This technique is particularly useful for problems that require finding duplicates, counting occurrences, or checking for membership.
Sample LeetCode Problem
Problem: 1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Solution
def twoSum(nums, target):
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return []
Explanation
This solution uses a hash map to store the indices of the numbers as they are iterated.
For each number, it checks if the complement (the number needed to reach the target) exists in the map.
If it does, it returns the indices of the complement and the current number.
If the complement is not found, it adds the current number and its index to the map.
If no pair is found that sums to the target, an empty list is returned.
Time Complexity
• O(n): We iterate through the list once, and each lookup in the hash map takes constant time on average.
Space Complexity
• O(n): We use a hash map to store at most all the elements in the worst case.
Ten Similar LeetCode Problems
- Group Anagrams - 49
- Happy Number - 202
- First Unique Character in a String - 387
- Valid Anagram - 242
- Bulls and Cows - 299
- 4Sum II - 454
- Subarray Sum Equals K - 560
- Two Sum - 1
- Top K Frequent Elements - 347
- Longest Consecutive Sequence - 128
10. Sorting
Pattern Outline
Sorting is a fundamental operation that arranges elements in a specific order (ascending or descending).
It is often used as a preprocessing step to simplify problem-solving or to prepare data for further processing.
Sample LeetCode Problem
Problem: 912. Sort an Array Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in your programming language's standard library that are capable of sorting the entire array inline (such as qsort in C).
Solution
def sortArray(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left_half = nums[:mid]
right_half = nums[mid:]
sortArray(left_half)
sortArray(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
nums[k] = left_half[i]
i += 1
else:
nums[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
nums[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
nums[k] = right_half[j]
j += 1
k += 1
return nums
Explanation
This solution uses the merge sort algorithm to sort the array.
It recursively divides the array into two halves until each subarray contains only one element.
Then, it merges the subarrays back together, comparing the elements and placing them in the correct order.
The base case is when the array has zero or one elements, in which case it is already sorted.
Time Complexity
• O(n log n): The time complexity of merge sort is O(n log n) in the average and worst cases.
Space Complexity
• O(n): The space complexity of merge sort is O(n) due to the creation of temporary arrays during the merge process.
Ten Similar LeetCode Problems
- Merge Intervals - 56
- Sort Colors - 75
- Top K Frequent Elements - 347
- Kth Largest Element in an Array - 215
- Merge Sorted Array - 88
- Queue Reconstruction by Height - 406
- Sort List - 148
- Maximum Gap - 164
- Wiggle Sort II - 324
- Reverse Pairs - 493
Summary
These patterns provide a structured approach to solving various LeetCode problems.
By recognizing and applying these patterns, you can enhance your problem-solving skills.
You can also improve your efficiency in coding interviews and competitive programming.
These patterns are shortcuts.
You can either wrestle with the LeetCode problem for hours -
Or identify the pattern and solve it in minutes.
However, be warned.
This list of patterns is not complete.
There are 10 more patterns but they are advanced and not necessary for everyone.
With the ten patterns above, you will be able to solve the majority of the questions on LeetCode.
All the best.
The job market is at its worst in years, highly competitive -
But with these patterns, your path is now much easier.
Again, all the best!
