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.
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.
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.
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.
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
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.
• O(n^2): The outer loop runs in O(n) and the inner while loop also runs in O(n) in the worst case.
• O(1):
We are using a constant amount of space for pointers and results, not counting the output list.
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.
Problem: 3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
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
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.
• O(n): Each character is processed at most twice (once by the right pointer and once by the left pointer).
• 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).
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.
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.
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
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.
• O(log n): The search space is halved with each iteration.
• O(1): We are using a constant amount of space for pointers.
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.
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.
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
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.
• 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.
• O(m * n): In the worst case, the recursion stack could go as deep as the number of cells in the grid.
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.
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.
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
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.
• O(m * n): Each cell is processed once.
• O(m * n): The queue can store up to all cells in the worst case.
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.
Problem: 46. Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
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
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.
• O(n!): The number of permutations of n elements is n!.
• O(n): The space used for the recursion stack and the result list.
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.
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.
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]
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.
• O(n): We iterate through the list of houses once.
• O(n): We use an array to store the maximum amounts for each house.
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.
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.
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
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.
• O(n): We iterate through the list once.
• O(1): We use a constant amount of space for variables.
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
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.
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.
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 []
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.
• O(n): We iterate through the list once, and each lookup in the hash map takes constant time on average.
• O(n): We use a hash map to store at most all the elements in the worst case.
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.
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).
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
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.
• O(n log n): The time complexity of merge sort is O(n log n) in the average and worst cases.
• O(n): The space complexity of merge sort is O(n) due to the creation of temporary arrays during the merge process.
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!