1,909 reads

10 LeetCode Patterns to Solve 1000 LeetCode Problems

by Thomas CherickalJuly 25th, 2024

Too Long; Didn't Read

10 LeetCode Patterns that solve 1000 LeetCode Problems. Too optimistic? Not at all. These 10 patterns will get you well on your way to LeetCode mastery. They cover foundational areas in competitive programming.

featured image - 10 LeetCode Patterns to Solve 1000 LeetCode Problems

‘Coding Problems and Solutions\’ Image created by HackerNoon AI Image Generator

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