Patterns

Prefix Sum

Useful for finding the sum of elements in a subarray. In this pattern, you would store the sum of the elements up the that point in an array.

array = [1,2,3,4,5,6,7]
prefix_sum = [1,3,6,10,15,21,28]

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

Two Pointers

Can be helpful in array problems where you iterate from the beginning and end of the array, moving the pointers towards each other until they meet. You can also start from the middle and work outwards.

Sliding Window

Helpful for finding subarrays that meet a criteria. You can check sums of subarrays by creating a window of length k, check the currently selected elements, and then when moving the window subtract the left-most element and add the new right-most element.

def max_subarray(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    max_start_index = 0
    for i in range(n-k):
        window_sum = window_sum - arr[i] + arr[i+k]
        if window_sum > max_sum:
            max_sum = window_sum
            max_start_index = i + 1

    return arr[max_start_index:max_start_index + k], max_sum

Fast and Slow Pointers

Useful for working with arrays and linked lists. Slow pointer moves 1 node per loop, and the faster moves 2 nodes per loop. This can be used when trying to find a cycle in a linked list, or if trying to find the middle of a linked-list, since when the fast pointer is at the end, the slow pointer is in the middle.

Linked List In-Place Reversal

You can do this by creating 3 pointers: prev, curr, and next.

def reverse_linked_list(head):
    prev = None
    curr = head
    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    return prev

Monotonic Stack

Useful for finding the next greatest or next smaller element in an array.

# Find the next greater element for each item in the array
def next_greater_element(arr):
    n = len(arr)
    stack = []
    result = [-1] * n

    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            result[stack.pop()] = arr[i]

        stack.append(i)

    return result

arr = [1,4,6,3,2,7]
result = next_greater_element(arr) # [4,6,7,7,7,-1]

Top K Elements

This pattern helps find the top K elements in a dataset that satisfy a criteria (greatest, least, etc). This can be done by using a min/max-heap, which only has K slots, where the top element is the next one to check against. Since popping and inserting in a heap is O(logn), then the time complexity of this is O(n*logk)

Overlapping Intervals

This pattern can be used when solving problems involving integers or ranges where they may overlap and finding intersections. This is done by sorting all intervals by the start, and then checking if the interval overlaps with the previous interval (start of next element is greater than end of previous element).

# Merging Intervals
[[1,3], [2,6], [8,10], [15,18]]
[[1,6], [8,10], [15,28]]

# Interval intersection
[[0,2], [5,10], [13,23], [24,25]], [[1,5], [8,12], [15,24], [25,26]]
[[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]]

# Insert interval
[[1,2], [3,5], [6,7], [8,10], [12,16]], [4,8]
[[1,2], [3,10], [12,16]]

Modified Binary Search

This pattern is helpful when solving problems where you need to find elements in an imperfectly sorted array (nearly sorted, rotated sorted, unknown length, containing duplicates). It can also be helpful finding the first or last occurance of an element, finding the square root of a number, and finding a peak element.

def search_rotated_array(nums, target):
    left, right = 0, len(nums)-1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

print(search_rotated_array([4,5,6,7,0,1,2]))

Binary Tree Traversal

Traversing a tree can use either BFS or DFS, but which one you use can depend on what the use case is.

• To retrieve values, use DFS inorder traversal.
• To create a copy of a tree, use DFS preorder traversal.
• To process child nots before the parent (like deleting a tree), use DFS postorder traversal.
• If you need to explore all nodes at current level before moving on, use BFS.

Matrix Traversal

Matrix traversal can be seen as graph problems, so you can use DFS or BFS to solve a lot of these problems.

# Number of Islands problem
def count_islands(grid):
    if not grid or not grid[0]: return 0

    rows, cols = len(grid), len(grid[0])
    islands = 0

    def dfs(i,j):
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':
            return

        grid[i][j] = '0'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == "1":
                dfs(i,j)
                islands += 1
    return islands

Backtracking

This can be used to find all potential solution paths and backtracking the paths that do not lead to a solution. This can be helpful for finding permutations, combinations, and all possible paths from start to end points.