Saikat Kumar Dey

Mastering Common Patterns to Solve Leetcode Problems

December 1, 2022

In this post, I will introduce you to 14 important patterns that can help you solve most of the problems on Leetcode. I will provide a template for each pattern to help you quickly apply it to a problem, as well as a list of important problems to practice with. By the end of this post, you will have a powerful set of tools to enhance your problem-solving skills on Leetcode and beyond. Let’s get started!

1. Sliding Window

The sliding window pattern is a common technique used to solve problems involving arrays or strings. It involves using a fixed-size “window” that slides through the array or string, and performs some operation on each sub-array or sub-string that it covers. This allows you to perform the operation on each possible sub-array or sub-string without having to create a new array or string for each one.

Here is a simple template in Python that you can use to solve any problem that uses the sliding window pattern:

Template

# initialize the window
window_start = 0
window_end = 0

# initialize any other variables you need
result = 0

# loop until the window_end reaches the end of the array/string
while window_end < len(arr):
  # perform the operation on the current sub-array/sub-string
  result = update_result(arr[window_start:window_end+1], result)

  # move the window to the right
  window_start += 1
  window_end += 1

# return the final result
return result

To use this template, you just need to define the update_result() function, which should take in the current sub-array/sub-string and the current result, and return an updated result.

Practise

Here are some important problems on leetcode that can be solved using the sliding window pattern:

  • Longest Substring Without Repeating Characters: This problem involves finding the longest substring in a string that does not contain any repeating characters. The sliding window pattern can be used to efficiently search for this substring.
  • Minimum Size Subarray Sum: This problem involves finding the smallest subarray in an array that has a given sum. The sliding window pattern can be used to efficiently search for this subarray.
  • Permutation in String: This problem involves checking whether one string is a permutation of another string. The sliding window pattern can be used to efficiently compare the two strings and check for a permutation.
  • Longest Substring with At Most Two Distinct Characters 💰: This problem involves finding the longest substring in a string that contains at most two distinct characters. The sliding window pattern can be used to efficiently search for this substring.
  • Minimum Window Substring: This problem involves finding the smallest substring in a string that contains all of the characters in another string. The sliding window pattern can be used to efficiently search for this substring.

2. Two pointers

The two pointers pattern is a common technique used to solve problems involving arrays or strings. It involves using two “pointers” that point to different elements in the array or string, and moving them in a specific way to perform some operation on the sub-array or sub-string they cover. This allows you to perform the operation on each possible sub-array or sub-string without having to create a new array or string for each one.

Here is a simple template in Python that you can use to solve any problem that uses the two pointers pattern:

Template

# initialize the pointers
pointer1 = 0
pointer2 = 0

# initialize any other variables you need
result = 0

# loop until the pointers reach the end of the array/string
while pointer1 < len(arr) and pointer2 < len(arr):
  # perform the operation on the current sub-array/sub-string
  result = update_result(arr[pointer1:pointer2+1], result)

  # move the pointers according to the specific rules of the pattern
  pointer1, pointer2 = move_pointers(pointer1, pointer2)

# return the final result
return result

To use this template, you just need to define the move_pointers() and update_result() functions. The move_pointers() function should take in the current values of the pointers, and return updated values for the pointers according to the specific rules of the pattern. The update_result() function should take in the current sub-array/sub-string and the current result, and return an updated result.

Practise

Here are some important problems on leetcode that can be solved using the two pointers pattern:

  • Two Sum: This problem involves finding two numbers in an array that add up to a given target number. The two pointers pattern can be used to efficiently search for these numbers by moving the pointers in opposite directions.
  • Remove Duplicates from Sorted Array: This problem involves removing duplicate elements from a sorted array. The two pointers pattern can be used to efficiently remove the duplicates by comparing the elements at each pointer and moving them as necessary.
  • Container With Most Water: This problem involves finding the maximum area of a container formed by two lines on a graph. The two pointers pattern can be used to efficiently search for the maximum area by moving the pointers in opposite directions.
  • Trapping Rain Water: This problem involves finding the amount of rainwater that can be trapped between bars on a histogram. The two pointers pattern can be used to efficiently calculate the trapped water by moving the pointers inwards from the ends of the array.

3. Fast and slow pointers

The fast and slow pointers pattern is a common technique used to solve problems involving linked lists. It involves using two pointers that traverse the linked list at different speeds. The “slow” pointer moves one step at a time, while the “fast” pointer moves two steps at a time. This allows the fast pointer to “lap” the slow pointer, and makes it possible to detect when the two pointers are pointing to the same node (i.e., they have “collided”).

Template

# initialize the pointers
slow_pointer = linked_list.head
fast_pointer = linked_list.head

# initialize any other variables you need
result = 0

# loop until the pointers reach the end of the linked list
while fast_pointer is not None and fast_pointer.next is not None:
  # perform the operation on the current nodes
  result = update_result(slow_pointer, fast_pointer, result)

  # move the pointers according to the specific rules of the pattern
  slow_pointer = slow_pointer.next
  fast_pointer = fast_pointer.next.next

  # check if the pointers have collided
  if slow_pointer == fast_pointer:
    break

# return the final result
return result

To use this template, you just need to define the update_result() function, which should take in the current values of the slow and fast pointers, and the current result, and return an updated result.

Practise

Here are some important problems on leetcode that can be solved using the fast and slow pointers pattern:

  • Linked List Cycle: This problem involves detecting whether a linked list contains a cycle. The fast and slow pointers pattern can be used to efficiently detect the cycle by moving the pointers at different speeds and checking for overlap.
  • Middle of the Linked List: This problem involves finding the middle element of a linked list. The fast and slow pointers pattern can be used to efficiently find the middle element by moving the pointers at different speeds and stopping when the fast pointer reaches the end of the list.
  • Happy Number: This problem involves determining whether a number is a happy number. The fast and slow pointers pattern can be used to efficiently check for happiness by moving the pointers at different speeds and checking for a cycle. Reorder List: This problem involves reordering the elements of a linked list in a specific way. The fast and slow pointers pattern can be used to efficiently reorder the elements by moving the pointers at different speeds and rearranging the elements as necessary.
  • Palindrome Linked List: This problem involves checking whether a linked list is a palindrome. The fast and slow pointers pattern can be used to efficiently check for palindromicity by moving the pointers at different speeds and comparing the elements at each pointer.

4. Merge Intervals

The merge intervals pattern is a common technique used to solve problems involving sets of intervals. It involves sorting the intervals by their start time, and then merging any intervals that overlap. This allows you to take a set of potentially overlapping intervals and convert it into a set of non-overlapping intervals.

Here is a simple template in Python that you can use to solve any problem that uses the merge intervals pattern:

Template


# sort the intervals by their start time
intervals = sorted(intervals, key=lambda x: x[0])

# initialize the result list with the first interval
result = [intervals[0]]

# loop through the remaining intervals
for i in range(1, len(intervals)):
  # get the last interval in the result list
  last_interval = result[-1]

  # check if the current interval overlaps with the last interval
  if intervals[i][0] <= last_interval[1]:
    # if it does, merge the current interval with the last interval
    result[-1] = (last_interval[0], max(last_interval[1], intervals[i][1]))
  else:
    # if it doesn't, add the current interval to the result list
    result.append(intervals[i])

# return the final result
return result

To use this template, you just need to provide a list of intervals (in the form of tuples of start and end times), and the template will return a list of non-overlapping intervals.

Practise

Here are some important problems on leetcode that can be solved using the merge intervals pattern:

-Merge Intervals: This problem involves merging a list of intervals that may overlap.

  • Insert Interval: This problem involves inserting a new interval into a list of intervals that may overlap.
  • Meeting Rooms: This problem involves checking whether it is possible to attend all of the meetings in a list of intervals.
  • Meeting Rooms II: This problem involves finding the minimum number of rooms needed to hold all of the meetings in a list of intervals.
  • Minimum Number of Arrows to Burst Balloons: This problem involves finding the minimum number of arrows needed to burst a given set of balloons.

5. Cyclic sort

Cyclic sort is a technique used to sort a list of numbers that are in a certain range, but not necessarily in the correct order. It involves looping through the list and “cycling” the numbers into the correct positions. For example, if the list is [3, 1, 5, 4, 2] and the range is 1 to 5, the first step would be to put the 1 in its correct position at index 0, the second step would be to put the 2 in its correct position at index 1, and so on.

Template

# initialize the current index and the number of items to sort
current_index = 0
num_to_sort = len(arr)

# loop until all items have been sorted
while num_to_sort > 0:
  # get the correct value for the current index
  correct_value = current_index + 1

  # check if the current value is already correct
  if arr[current_index] == correct_value:
    # if it is, move on to the next index
    current_index += 1
    num_to_sort -= 1
  else:
    # if it isn't, swap the current value with the correct value
    arr[current_index], arr[arr[current_index] - 1] = arr[arr[current_index] - 1], arr[current_index]

# return the sorted array
return arr

To use this template, you just need to provide a list of numbers that are in a certain range, and the template will return the sorted list.

Practise

Here are some important problems on leetcode that can be solved using the cyclic sort pattern:

6. In-place reversal of linked-list

“In-place reversal of a linked list” refers to a technique for reversing the order of the nodes in a linked list without using any additional data structures. This is done by changing the links between the nodes in the linked list so that the nodes are connected in the opposite order.

Template

# initialize the previous, current, and next nodes
prev_node = None
curr_node = linked_list.head
next_node = None

# loop until the current node is None
while curr_node is not None:
  # store the next node
  next_node = curr_node.next

  # reverse the link between the current and previous nodes
  curr_node.next = prev_node

  # move the previous and current nodes forward
  prev_node = curr_node
  curr_node = next_node

# set the head of the linked list to the new start node
linked_list.head = prev_node

To use this template, you just need to provide a linked list object and the template will reverse the order of the nodes in the linked list.

Practise

Here are some important problems on leetcode that can be solved using the in-place reversal of linked list pattern:

7. Tree BFS

The tree BFS (Breadth-First Search) pattern is a technique used to traverse the nodes of a tree in a level-by-level order. In the case of a binary tree (i.e., a tree in which each node has at most two children), the tree BFS algorithm can be implemented as follows:

Template

# initialize the queue with the root node
queue = [root]

# initialize any other variables you need
result = []

# loop until the queue is empty
while len(queue) > 0:
  # get the next node from the queue
  current_node = queue.pop(0)

  # perform the operation on the current node
  result = update_result(current_node, result)

  # add the left and right child nodes of the current node to the queue
  if current_node.left is not None:
    queue.append(current_node.left)
  if current_node.right is not None:
    queue.append(current_node.right)

# return the final result
return result

To use this template, you just need to provide the root node of the binary tree and define the update_result() function, which should take in the current node and the current result, and return an updated result.

Practise

Here are some important problems on leetcode that can be solved using the tree BFS pattern:

8. Tree DFS

The tree DFS (Depth-First Search) pattern is a technique used to traverse the nodes of a tree in a depth-first manner. In the case of a binary tree (i.e., a tree in which each node has at most two children), the tree DFS algorithm can be implemented as follows:

Template

# initialize any other variables you need
result = []

# perform the DFS traversal on the root node
traverse(root, result)

# return the final result
return result

def traverse(node, result):
  # perform the operation on the current node
  result = update_result(node, result)

  # recursively traverse the left and right child nodes of the current node
  if node.left is not None:
    traverse(node.left, result)
  if node.right is not None:
    traverse(node.right, result)

To use this template, you just need to provide the root node of the binary tree and define the update_result() function, which should take in the current node and the current result, and return an updated result.

Practise

Here are some important problems on leetcode that can be solved using the tree DFS pattern:

9. Two heaps

The “two heaps” pattern is a common technique used to solve problems involving sets of numbers. It involves using two heaps (i.e., data structures that provide efficient ways to insert and remove items, and to find the minimum or maximum item) to store the numbers in the set. This allows you to efficiently maintain certain properties of the numbers in the set, and to quickly perform operations on the numbers when needed.

Template

import heapq

# initialize the two heaps
heap1 = []
heap2 = []

# initialize any other variables you need

# loop through the numbers in the set
for num in nums:
  # insert the number into the appropriate heap
  if condition1:
    heapq.heappush(heap1, num)
  else:
    heapq.heappush(heap2, num)

  # balance the heaps if necessary
  if condition2:
    heapq.heappush(heap2, heapq.heappop(heap1))
  elif condition3:
    heapq.heappush(heap1, heapq.heappop(heap2))

  # update any other variables you need
  update_variables(num)

# return the final result
return result

To use this template, you just need to provide a list of numbers and define the condition1, condition2, condition3, and update_variables() functions. These functions should determine which heap to insert the current number into, whether the heaps need to be balanced, and how to update any other variables you need.

For example, if you want to use the two heaps pattern to find the median of a set of numbers, you could define the following functions:

# insert the number into the smaller_half heap if it is smaller than the current median,
# or into the larger_half heap if it is larger or equal to the current median
def condition1(num, median):
  return num < median

# balance the heaps if the size difference between them is greater than 1
def condition2(smaller_half, larger_half):
  return len(smaller_half) > len(larger_half) + 1

# balance the heaps if the size difference between them is greater than 1
def condition3(smaller_half, larger_half):
  return len(larger_half) > len(smaller_half) + 1

# update the median if the size of the two heaps is equal, or if one heap is larger than the other
def update_variables(num, median, smaller_half, larger_half):
  if len(smaller_half) == len(larger_half):
    median = (-smaller_half[0] + larger_half[0]) / 2
  elif len(smaller_half) > len(larger_half):
    median = -smaller_half[0]
  else:
    median = larger_half[0]

Practise

Here are some important problems on leetcode that can be solved using the two heaps pattern:

10. Subsets

The “subsets” pattern is a common technique used to solve problems involving sets of numbers. It involves generating all possible subsets of the set and then performing some operation on each subset to find the desired result. This allows you to consider all possible combinations of numbers in the set and to efficiently compute the result for each combination.

Template 1

# initialize the result
result = []

# generate all possible subsets of the set
for subset in itertools.combinations(nums, r) for r in range(len(nums)+1):
  # perform the operation on the current subset
  result = update_result(subset, result)

# return the final result
return result

Template 2

# initialize the result
result = []

# generate all possible subsets of the set
for i in range(1, 2**len(nums)):
  # convert the binary representation of i to a list of indices
  indices = [j for j in range(len(nums)) if i & (1 << j)]

  # generate the current subset
  subset = [nums[j] for j in indices]

  # perform the operation on the current subset
  result = update_result(subset, result)

# return the final result
return result

It uses a single loop and binary operations to generate the subsets. It converts the binary representation of each number in the range 1..2^len(nums) to a list of indices, and then uses those indices to select the elements of the set that are included in the current subset.

Practise

Here are some important problems on leetcode that can be solved using the subsets pattern:

  • Subsets: This problem involves generating all of the subsets of a given set of elements.
  • Subsets II: This problem involves generating all of the subsets of a given set of elements, allowing for duplicates.
  • Permutations: This problem involves generating all of the permutations of a given set of elements.
  • Permutations II: This problem involves generating all of the permutations of a given set of elements, allowing for duplicates.
  • Combination Sum: This problem involves finding all of the combinations of a given set of elements that add up to a specific target sum.

The “modified binary search” pattern is a common technique used to solve problems involving a sorted array of numbers. It is similar to regular binary search, but it allows you to modify the condition used to determine whether to search the left or right half of the array. This can be useful if the problem you’re trying to solve involves finding the position of an element in the array that satisfies a certain condition, or if the array has duplicate elements and you need to find the first or last occurrence of a given element.

Template

# initialize the left and right pointers
left = 0
right = len(nums) - 1

# search the array until the left and right pointers meet
while left < right:
  # calculate the middle index
  mid = left + (right - left) // 2

  # modify the condition used to determine which half of the array to search
  if condition(nums[mid]):
    right = mid
  else:
    left = mid + 1

# return the final result
return left

If you want to use the modified binary search pattern to find the first occurrence of a given element in an array, you could define the following condition() function:

def condition(num):
  return num == target and (mid == 0 or nums[mid-1] != target)

This function checks whether the current element is equal to the target element and whether it is the first occurrence of that element in the array (i.e., whether the element before it is not equal to the target). If both of these conditions are satisfied, then the function returns True, indicating that the left pointer should be updated to the current index. Otherwise, it returns False, indicating that the right pointer should be updated to the current index.

Practise

Here are some important problems on leetcode that can be solved using the modified binary search pattern:

12. Top K elements

The “top k elements” pattern is a common technique used to solve problems involving a large set of numbers. It involves finding the largest or smallest k elements in the set and then performing some operation on those elements to find the desired result. This allows you to efficiently select the most important elements from the set and to compute the result using only those elements.

Template

# initialize the heap with the first k elements of the set
heap = nums[:k]

# heapify the heap
heapq.heapify(heap)

# loop through the remaining elements of the set
for num in nums[k:]:
  # insert the current element into the heap if it is larger than the smallest element in the heap
  if num > heap[0]:
    heapq.heappushpop(heap, num)

# return the final result
return operation(heap)

For example, if you want to use the top k elements pattern to find the sum of the largest k elements in a set, you could define the following operation() function:

def operation(heap):
  return sum(heap)

This function simply returns the sum of all the elements in the heap, which are the largest k elements in the set

Practise

Here are some important problems on leetcode that can be solved using the top k elements pattern:

13. K-way Merge (using heap)

The k-way merge pattern using a heap is a common technique used to merge k sorted arrays into a single sorted array. It involves using a heap data structure to efficiently select the smallest element from the k arrays and to add it to the result. This allows you to efficiently combine the k arrays into a single sorted array and to perform further operations on that array.

Template

# initialize the result and the heap with the first elements of the k arrays
result = []
heap = [(arrays[i][0], i) for i in range(k)]

# heapify the heap
heapq.heapify(heap)

# loop until all the arrays have been merged
while heap:
  # get the smallest element from the heap
  min_element, min_index = heapq.heappop(heap)

  # add the smallest element to the result
  result.append(min_element)

  # insert the next element from the array where the smallest element was found into the heap
  if min_index < len(arrays[min_index]) - 1:
    heapq.heappush(heap, (arrays[min_index][min_index+1], min_index))

# return the final result
return result

Practise

Here are some important problems on leetcode that can be solved using the k-way merge (using heap) pattern:

14. Topological Sort

Topological sort is an algorithm that is used to arrange the vertices of a directed acyclic graph (DAG) in a linear order such that, for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. This is useful for problems where a certain set of dependencies must be satisfied, such as scheduling tasks or determining the order in which to assemble a product.

To perform a topological sort, we first identify all of the vertices with no incoming edges (i.e., no dependencies) and put them in a queue. We then remove these vertices from the graph and repeat the process until the queue is empty. At each step, we add the vertices we remove to a list, which will eventually give us the topological ordering of the vertices.

Topological sort is commonly used to solve problems on LeetCode, such as “Course Schedule” and “Alien Dictionary”. It can also be useful for solving other problems that involve dependencies between objects or tasks.

Template

from collections import deque

def topological_sort(vertices, edges):
    # Create a list to store the topological ordering of the vertices
    top_order = []

    # Create a queue to keep track of the vertices with no incoming edges
    queue = deque()

    # Create a dictionary to store the indegrees of each vertex
    indegrees = {vertex: 0 for vertex in vertices}

    # Create a dictionary to store the adjacency list for each vertex
    adj_list = {vertex: [] for vertex in vertices}

    # Populate the indegrees dictionary and adjacency list
    for edge in edges:
        u, v = edge
        indegrees[v] += 1
        adj_list[u].append(v)

    # Add all vertices with no incoming edges to the queue
    for vertex, indegree in indegrees.items():
        if indegree == 0:
            queue.append(vertex)

    # Perform the topological sort
    while queue:
        # Remove a vertex from the queue
        vertex = queue.popleft()

        # Add the vertex to the topological ordering
        top_order.append(vertex)

        # Decrement the indegree of each of its neighbors
        for neighbor in adj_list[vertex]:
            indegrees[neighbor] -= 1

            # If the indegree of a neighbor becomes 0, add it to the queue
            if indegrees[neighbor] == 0:
                queue.append(neighbor)

    # If there are any vertices left in the graph, then the original graph was not a DAG
    if len(top_order) != len(vertices):
        return []

    return top_order

Practise

Here are some important problems on leetcode that can be solved using the topological sort pattern:

  • Course Schedule: This problem involves checking whether a given set of courses can be completed, given the dependencies between the courses.
  • Course Schedule II: This problem involves finding the order in which the courses should be taken in order to complete them all.
  • Alien Dictionary: This problem involves reconstructing the order of the letters in an alien language, given a list of words.
  • Sequence Reconstruction: This problem involves checking whether a given sequence can be reconstructed from a given set of subsequences.
  • Minimum Height Trees: This problem involves finding the root(s) of a tree with minimum height.

References