Mastering Python

20 Essential DSA Patterns in Python for Interviews

Table of Contents
1. Sliding Window Pattern
2. Two Pointer Pattern
3. Fast & Slow Pointers Pattern
4. Merge Intervals Pattern
5. Cyclic Sort Pattern
6. In-place Reversal of a Linked List
7. Breadth-First Search (BFS)
8. Depth-First Search (DFS)
9. Two Heaps Pattern
10. Subsets Pattern
11. Modified Binary Search
12. Topological Sort
13. Bitwise XOR Pattern
14. Fast Exponentiation
15. Greedy Pattern
16. Dynamic Programming
17. Matrix Traversal
18. Backtracking
19. Divide & Conquer
20. Graph Traversal

Part 1: Sliding Window Pattern

Pattern Overview
The Sliding Window Pattern is a powerful technique for solving problems involving arrays or strings
where you need to examine contiguous sequences of elements. Instead of using nested loops (O(n²)), this
pattern maintains a "window" that slides through the data, achieving O(n) time complexity.

When to Use:
Finding longest/shortest substring with specific properties
Finding maximum/minimum sum of subarray of size k
String permutation problems
 Any problem dealing with contiguous elements

How it Works:
Array: [1, 3, 2, 6, -1, 4, 1, 8, 2]

Window size: 3

Step 1: [1, 3, 2] 6, -1, 4, 1, 8, 2 (sum = 6)

Step 2: 1, [3, 2, 6] -1, 4, 1, 8, 2 (sum = 11)

Step 3: 1, 3, [2, 6, -1] 4, 1, 8, 2 (sum = 7)

... and so on

Problems: Sliding Window Pattern

Problem 1: Maximum Sum Subarray of Size K

Find the maximum sum of any contiguous subarray of size k.

def maxSumSubarray(arr, k):

max_sum = window_sum = sum(arr[:k])

for i in range(k, len(arr)):

window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)

return max_sum

Problem 2: Smallest Subarray with a Given Sum

Find the length of the smallest contiguous subarray whose sum is greater than or equal to a given value.

def smallestSubarrayWithSum(arr, target):

window_sum = 0
min_length = float('inf')
start = 0

for end in range(len(arr)):

window_sum += arr[end]

while window_sum >= target:

min_length = min(min_length, end - start + 1)
window_sum -= arr[start]
start += 1

return 0 if min_length == float('inf') else min_length

Problem 3: Longest Substring with K Distinct Characters

Find the length of the longest substring with at most k distinct characters.

def longestSubstringKDistinct(s, k):

from collections import defaultdict

freq_map = defaultdict(int)
max_length = 0
start = 0

for end in range(len(s)):

freq_map[s[end]] += 1

while len(freq_map) > k:

start_char = s[start]
freq_map[start_char] -= 1
if freq_map[start_char] == 0:
del freq_map[start_char]
start += 1

max_length = max(max_length, end - start + 1)

return max_length

Problem 4: Fruits Into Baskets

You have two baskets, and each basket can carry any quantity of one type of fruit. Find the maximum
number of fruits you can collect.

def fruitsIntoBaskets(fruits):
from collections import defaultdict

basket = defaultdict(int)
max_fruits = 0
start = 0

for end in range(len(fruits)):

basket[fruits[end]] += 1

while len(basket) > 2:

start_fruit = fruits[start]
basket[start_fruit] -= 1
if basket[start_fruit] == 0:
del basket[start_fruit]
start += 1

max_fruits = max(max_fruits, end - start + 1)

 return max_fruits

Problem 5: No-repeat Substring

Find the length of the longest substring without repeating characters

def noRepeatSubstring(s):
char_index = {}
max_length = 0
start = 0

for end in range(len(s)):

right_char = s[end]

if right_char in char_index and char_index[right_char] >= start:

start = char_index[right_char] + 1

char_index[right_char] = end
max_length = max(max_length, end - start + 1)

return max_length

Part 2: Two Pointer Pattern

Pattern Overview
The Two Pointer Pattern uses two pointers to traverse data structures, typically arrays or linked lists. These
pointers can move towards each other (from opposite ends) or in the same direction at different speeds.
This pattern is excellent for reducing time complexity from O(n²) to O(n).

When to Use:
Sorted arrays or linked lists
Finding pairs with specific sum
Comparing elements from both ends
Removing duplicates in-place
Palindrome problems

How it Works:
Sorted Array: [1, 2, 3, 4, 6, 8, 9]

Target Sum: 10

left right

↓ ↓
[1, 2, 3, 4, 6, 8, 9]

Sum = 1 + 9 = 10 ✓ Found!

Problems:

Problem 1: Pair with Target Sum

Find a pair of numbers in a sorted array that sum up to a target value.

def pairWithTargetSum(arr, target):

left, right = 0, len(arr) - 1

while left < right:

current_sum = arr[left] + arr[right]

if current_sum == target:
return [left, right]

if current_sum < target:

left += 1
else:
right -= 1

return [-1, -1]

Problem 2: Remove Duplicates from a Sorted Array

Remove duplicates in-place and return the new length.

def removeDuplicates(nums):
if not nums:
return 0

next_non_duplicate = 1

for i in range(1, len(nums)):

if nums[next_non_duplicate - 1] != nums[i]:
nums[next_non_duplicate] = nums[i]
next_non_duplicate += 1

return next_non_duplicate

Problem 3: Squaring a Sorted Array

Given a sorted array, create a new array containing squares of all numbers sorted in ascending order.
 def makeSquares(arr):
n = len(arr)
squares = [0] * n
left, right = 0, n - 1
highest_square_idx = n - 1

while left <= right:

left_square = arr[left] ** 2
right_square = arr[right] ** 2

if left_square > right_square:

squares[highest_square_idx] = left_square
left += 1
else:
squares[highest_square_idx] = right_square
right -= 1

highest_square_idx -= 1

return squares

Problem 4: Triplet Sum to Zero

Find all unique triplets in the array that sum up to zero.

def searchTriplets(arr):
arr.sort()
triplets = []

for i in range(len(arr) - 2):

if i > 0 and arr[i] == arr[i - 1]:
continue

left, right = i + 1, len(arr) - 1

while left < right:

current_sum = arr[i] + arr[left] + arr[right]

if current_sum == 0:
triplets.append([arr[i], arr[left], arr[right]])
left += 1
right -= 1

while left < right and arr[left] == arr[left - 1]:

left += 1
while left < right and arr[right] == arr[right + 1]:
right -= 1

elif current_sum < 0:

 left += 1
else:
right -= 1

return triplets

Problem 5: Dutch National Flag Problem

Sort an array containing only 0s, 1s, and 2s in-place.

def swap(arr, i, j):

arr[i], arr[j] = arr[j], arr[i]

def dutchFlagSort(arr):
low, high = 0, len(arr) - 1
i = 0

while i <= high:

if arr[i] == 0:
swap(arr, i, low)
low += 1
i += 1
elif arr[i] == 1:
i += 1
else:
swap(arr, i, high)
high -= 1

Part 3: Fast & Slow Pointers Pattern

Pattern Overview
The Fast & Slow Pointers pattern (also known as Floyd's Tortoise and Hare algorithm) uses two pointers
that move at different speeds through a data structure. This pattern is particularly useful for detecting
cycles and finding middle elements in linked lists.

When to Use:
Detecting cycles in linked lists
Finding the middle of a linked list
Determining if a number is happy
Finding the start of a cycle
Palindrome linked list problems

How it Works:
Linked List with Cycle:

1→2→3→4

↑ ↓

7←6←5

Slow pointer moves 1 step

Fast pointer moves 2 steps

They will meet if there's a cycle!

Problems:

Problem 1: Linked List Cycle

Detect if a linked list has a cycle.

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def hasCycle(head):
slow = head
fast = head

while fast and fast.next:

slow = slow.next
fast = fast.next.next

if slow == fast:
return True

return False

Problem 2: Start of Linked List Cycle

Find the node where the cycle begins.

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def detectCycle(head):
slow = head
fast = head
 # First phase: detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next

if slow == fast:
# Second phase: find entry point
ptr1 = head
while ptr1 != slow:
ptr1 = ptr1.next
slow = slow.next
return ptr1

return None

Problem 3: Happy Number

A happy number is defined by the following process: replace the number by the sum of the squares of its
digits, repeat until it equals 1 or loops endlessly.

class HappyNumber:
def findSquareSum(self, num):
total = 0
while num > 0:
digit = num % 10
total += digit * digit
num //= 10
return total

def isHappy(self, num):

slow = num
fast = num

while True:
slow = self.findSquareSum(slow)
fast = self.findSquareSum(self.findSquareSum(fast))
if slow == fast:
break

return slow == 1

Problem 4: Middle of the Linked List

Find the middle node of a linked list.

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
 self.next = next

def middleNode(head):
slow = head
fast = head

while fast and fast.next:

slow = slow.next
fast = fast.next.next

return slow

Problem 5: Palindrome Linked List

Check if a linked list is a palindrome.

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def isPalindrome(head):
if not head or not head.next:
return True

# Step 1: Find the middle

slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next

# Step 2: Reverse the second half

second_half = reverse(slow)
first_half = head

# Step 3: Compare both halves

while second_half:
if first_half.val != second_half.val:
return False
first_half = first_half.next
second_half = second_half.next

return True

def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
 prev = head
head = nxt
return prev

Part 4: Merge Intervals Pattern

Pattern Overview
The Merge Intervals pattern deals with overlapping intervals. It's commonly used in problems involving
time intervals, meeting rooms, or any scenario where you need to merge or manipulate overlapping
ranges.

When to Use:
Calendar scheduling problems
Meeting room allocation
Merging overlapping ranges
Finding gaps in intervals
Interval intersection problems

How it Works:
Input intervals: [[1,3], [2,6], [8,10], [15,18]]

After sorting: [[1,3], [2,6], [8,10], [15,18]]

Step 1: [1,3] and [2,6] overlap → merge to [1,6]

Step 2: [1,6] and [8,10] don't overlap → keep separate

Step 3: [8,10] and [15,18] don't overlap → keep separate

Result: [[1,6], [8,10], [15,18]]

Problems:

Problem 1: Merge Intervals

Merge all overlapping intervals.

def merge(intervals):
if not intervals:
return []

intervals.sort(key=lambda x: x[0])
merged = []
current = intervals[0]

for interval in intervals:

 if current[1] >= interval[0]:
current[1] = max(current[1], interval[1])
else:
merged.append(current)
current = interval

merged.append(current)
return merged

Problem 2: Insert Interval

Insert a new interval into a list of non-overlapping intervals

def insert(intervals, newInterval):

result = []
i = 0
n = len(intervals)

while i < n and intervals[i][1] < newInterval[0]:

result.append(intervals[i])
i += 1

while i < n and intervals[i][0] <= newInterval[1]:

newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1

result.append(newInterval)

while i < n:
result.append(intervals[i])
i += 1

return result

Problem 3: Intervals Intersection

Find the intersection of two lists of intervals.

def intervalIntersection(A, B):

result = []
i = j = 0

while i < len(A) and j < len(B):

if A[i][1] >= B[j][0] and B[j][1] >= A[i][0]:
result.append([
max(A[i][0], B[j][0]),
min(A[i][1], B[j][1])
 ])

if A[i][1] < B[j][1]:

i += 1
else:
j += 1

return result

Problem 4: Conflicting Appointments

Determine if a person can attend all appointments.

def canAttendMeetings(intervals):
intervals.sort(key=lambda x: x[0])

for i in range(1, len(intervals)):

if intervals[i][0] < intervals[i - 1][1]:
return False

return True

Problem 5: Minimum Meeting Rooms

Find the minimum number of meeting rooms required.

def minMeetingRooms(intervals):
if not intervals:
return 0

start_times = sorted([i[0] for i in intervals])

end_times = sorted([i[1] for i in intervals])

rooms = 0
end_ptr = 0

for i in range(len(intervals)):
if start_times[i] < end_times[end_ptr]:
rooms += 1
else:
end_ptr += 1

return rooms

Part 5: Cyclic Sort Pattern

Pattern Overview
The Cyclic Sort pattern is used when dealing with arrays containing numbers in a given range. It places
each number at its correct index, making it efficient for finding missing or duplicate numbers.

When to Use:
Array contains numbers from 0 to n or 1 to n
Finding missing numbers
Finding duplicate numbers
Finding the smallest missing positive number
Problems involving array indices

How it Works:
Array: [3, 1, 5, 4, 2]

Goal: Place each number at index (number - 1)

Step 1: 3 should be at index 2

Swap with element at index 2

[5, 1, 3, 4, 2]

Step 2: 5 should be at index 4

Swap with element at index 4

[2, 1, 3, 4, 5]

Continue until sorted...

Final: [1, 2, 3, 4, 5]

Problems:

Problem 1: Cyclic Sort

Sort an array containing numbers from 1 to n.

def cyclicSort(nums):
i = 0
while i < len(nums):
correct_index = nums[i] - 1
if nums[i] != nums[correct_index]:
nums[i], nums[correct_index] = nums[correct_index], nums[i]
else:
i += 1

Problem 2: Find the Missing Number

Find the missing number in an array containing n distinct numbers from 0 to n.

def findMissingNumber(nums):
i = 0
while i < len(nums):
if nums[i] < len(nums) and nums[i] != nums[nums[i]]:
nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
else:
i += 1

for i in range(len(nums)):
if nums[i] != i:
return i

return len(nums)

Problem 3: Find All Missing Numbers

Find all missing numbers in an array containing numbers from 1 to n.

def findMissingNumbers(nums):
i = 0
while i < len(nums):
correctIndex = nums[i] - 1
if nums[i] != nums[correctIndex]:
nums[i], nums[correctIndex] = nums[correctIndex], nums[i]
else:
i += 1

missingNumbers = []
for i in range(len(nums)):
if nums[i] != i + 1:
missingNumbers.append(i + 1)

return missingNumbers

Problem 4: Find the Duplicate Number

Find the duplicate number in an array containing n+1 numbers from 1 to n.

def findDuplicateNumber(nums):
i = 0
while i < len(nums):
if nums[i] != i + 1:
if nums[i] == nums[nums[i] - 1]:
return nums[i]
 nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
else:
i += 1
return -1

Problem 5: Find All Duplicates in an Array

Find all duplicates in an array containing numbers from 1 to n.

def findAllDuplicates(nums):
i = 0
while i < len(nums):
correctIndex = nums[i] - 1
if nums[i] != nums[correctIndex]:
nums[i], nums[correctIndex] = nums[correctIndex], nums[i]
else:
i += 1

duplicates = []
for i in range(len(nums)):
if nums[i] != i + 1:
duplicates.append(nums[i])

return duplicates

Part 6: In-place Reversal of a Linked List

Pattern Overview
This pattern reverses linked lists or portions of linked lists in-place without using extra memory. It's
fundamental for many linked list problems and often combined with other patterns.

When to Use:
Reversing entire linked lists
Reversing sub-lists
Reversing every k nodes
Rotating linked lists
Problems requiring link manipulation

How it Works:
Original: 1 → 2 → 3 → 4 → 5 → null

Step 1: null ← 1 2 → 3 → 4 → 5
Step 2: null ← 1 ← 2 3 → 4 → 5

Step 3: null ← 1 ← 2 ← 3 4 → 5

...

Final: null ← 1 ← 2 ← 3 ← 4 ← 5

Problems:

Problem 1: Reverse a Linked List

Reverse an entire linked list.

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def reverseList(head):
prev = None
curr = head

while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp

return prev

Problem 2: Reverse a Sub-list

Reverse nodes from position m to n.

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def reverseBetween(head, m, n):

if not head:
return None

dummy = ListNode(0)
dummy.next = head
prev = dummy

# Step 1: Move `prev` to node before reversal starts

for _ in range(m - 1):
 prev = prev.next

start = prev.next
then = start.next

# Step 2: Reverse nodes between m and n

for _ in range(n - m):
start.next = then.next
then.next = prev.next
prev.next = then
then = start.next

return dummy.next

Problem 3: Reverse Every K-element Sub-list

Reverse every k nodes in the linked list.

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def reverseKGroup(head, k):

curr = head
count = 0

# Step 1: Check if there are at least k nodes to reverse

while curr and count != k:
curr = curr.next
count += 1

if count == k:
# Step 2: Recursively process the remaining list
curr = reverseKGroup(curr, k)

# Step 3: Reverse the current group of k nodes

while count > 0:
temp = head.next
head.next = curr
curr = head
head = temp
count -= 1

head = curr # New head of this reversed group

return head
Problem 4: Rotate a Linked List

Rotate the list to the right by k places.

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def rotateRight(head, k):

if not head:
return head

# Step 1: Find the length and tail

oldTail = head
length = 1
while oldTail.next:
oldTail = oldTail.next
length += 1

# Step 2: Make the list circular

oldTail.next = head

# Step 3: Find new tail at (length - k % length - 1)

k = k % length
newTail = head
for _ in range(length - k - 1):
newTail = newTail.next

# Step 4: Break the circle and set new head

newHead = newTail.next
newTail.next = None

return newHead

Problem 5: Reverse Nodes in K-Group

Reverse the nodes of a linked list k at a time. Nodes that do not form a complete k-group should remain
as they are

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def reverseKGroup(head, k):

curr = head
count = 0
 # Check if there are at least k nodes to reverse
while curr and count != k:
curr = curr.next
count += 1

if count == k:
# Recursively reverse the remaining list
curr = reverseKGroup(curr, k)

# Reverse the current k-group

while count > 0:
temp = head.next
head.next = curr
curr = head
head = temp
count -= 1

head = curr # New head after reversal

return head

Part 7: Breadth-First Search (BFS)

Pattern Overview:
Breadth-First Search is an algorithm for traversing or searching tree and graph data structures level-by-
level, visiting all nodes at the current depth before moving to nodes at the next depth level. BFS is
typically implemented using a queue.

When to Use:
Shortest path or minimum steps problems.
Level-order traversals (trees, graphs).
Finding nodes at a certain distance.

How it Works (Example):

Given Binary Tree:

/ \

2 3

/\ /\

4 56 7
BFS Traversal: 1 → 2 → 3 → 4 → 5 → 6 → 7

Problems:

Problem 1: Binary Tree Level Order Traversal

from collections import deque

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def levelOrder(root):
result = []
if not root:
return result

queue = deque([root])

while queue:
level_size = len(queue)
level = []

for _ in range(level_size):
current = queue.popleft()
level.append(current.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)

result.append(level)

return result

Problem 2: Minimum Depth of Binary Tree.

from collections import deque

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def minDepth(root):
 if not root:
return 0

queue = deque([root])
depth = 1

while queue:
size = len(queue)
for _ in range(size):
node = queue.popleft()
if not node.left and not node.right:
return depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1

return depth

Problem 3: Binary Tree Right Side View.

from collections import deque

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def rightSideView(root):
result = []
if not root:
return result

queue = deque([root])

while queue:
size = len(queue)
for i in range(size):
node = queue.popleft()
if i == size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return result
Problem 4: Rotten Oranges (LeetCode 994)

from collections import deque

def orangesRotting(grid):
if not grid:
return 0

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

queue = deque()
fresh = 0
minutes = 0

for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1

if fresh == 0:
return 0

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while queue:
size = len(queue)
rotted = False

for _ in range(size):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
grid[nx][ny] = 2
queue.append((nx, ny))
fresh -= 1
rotted = True

if rotted:
minutes += 1

return minutes if fresh == 0 else -1

Problem 5: Course Schedule (LeetCode 207)

 from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):

indegree = [0] * numCourses
adj = defaultdict(list)

for a, b in prerequisites:
adj[b].append(a)
indegree[a] += 1

queue = deque(i for i in range(numCourses) if indegree[i] == 0)

count = 0

while queue:
course = queue.popleft()
count += 1
for neighbor in adj[course]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)

return count == numCourses

Part 8: Depth-First Search (DFS)

Pattern Overview:
Depth-First Search (DFS) is an algorithm that explores nodes in depth-wise order, going as deep as
possible before backtracking. It is implemented using recursion or stacks.

When to Use:
Finding paths, connectivity, or cycles in graphs and trees.
Searching deeper before breadth (opposite of BFS).
Top-down problems where decisions affect subsequent paths (backtracking).

How it Works (Example):

Given Binary Tree:

/\

2 3

/\ \

4 5 6
DFS Traversal: 1 → 2 → 4 → 5 → 3 → 6

Problems:

Problem 1: Maximum Depth of Binary Tree (LeetCode 104)

def maxDepth(root):
if root is None:
return 0
left = maxDepth(root.left)
right = maxDepth(root.right)
return max(left, right) + 1

Problem 2: Path Sum (LeetCode 112)

Check if a path with a given sum exists.

def hasPathSum(root, target_sum):

if not root:
return False
if not root.left and not root.right:
return root.val == target_sum
return (hasPathSum(root.left, target_sum - root.val) or
hasPathSum(root.right, target_sum - root.val))

Problem 3: All Root-to-Leaf Paths (LeetCode 257)

Find all paths from root to leaves.

def dfsPaths(node, path, paths):

if not node:
return
path += str(node.val)
if not node.left and not node.right:
paths.append(path)
else:
dfsPaths(node.left, path + "->", paths)
dfsPaths(node.right, path + "->", paths)

def binaryTreePaths(root):
paths = []
dfsPaths(root, "", paths)
return paths

Problem 4: Number of Islands (LeetCode 200)

Find number of islands in a grid.

def dfs(grid, i, j):

if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
dfs(grid, i + 1, j)
dfs(grid, i - 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j - 1)

def numIslands(grid):
if not grid:
return 0
islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid, i, j)
islands += 1
return islands

Problem 5: Flood Fill (LeetCode 733)

Perform flood fill on a 2D array.

def fill(image, i, j, old_color, new_color):

if i < 0 or i >= len(image) or j < 0 or j >= len(image[0]) or image[i][j] != old_co
return
image[i][j] = new_color
fill(image, i + 1, j, old_color, new_color)
fill(image, i - 1, j, old_color, new_color)
fill(image, i, j + 1, old_color, new_color)
fill(image, i, j - 1, old_color, new_color)

def floodFill(image, sr, sc, new_color):

old_color = image[sr][sc]
if old_color != new_color:
fill(image, sr, sc, old_color, new_color)
return image

Part 9: Two Heaps Pattern

Pattern Overview:
The Two Heaps pattern leverages two heap data structures (a min-heap and a max-heap) simultaneously,
allowing efficient retrieval of both minimum and maximum values or median calculations. This technique
is extremely efficient for streaming data problems or scenarios involving frequent min/max queries.

When to Use:
Problems involving real-time or streaming data.
Finding median from a continuous stream.
Efficient retrieval of the largest/smallest elements frequently.
Balancing two opposite extremes.

How it Works (Example):

Max Heap stores the smaller half of numbers.
Min Heap stores the larger half of numbers.
This way, the median can be quickly calculated:
If heaps have equal size, median = (maxHeap.peek() + minHeap.peek()) / 2
If heaps differ in size, median is at top of larger heap.
Example Stream: [3, 1, 5, 4]

Max Heap Min Heap Median

[3] [] 3

[1] [3] 2

[1,3] [5] 3

[1,3] [4,5] 3.5

Problems:

Problem 1: Find Median from Data Stream (LeetCode 295)

import heapq

class MedianFinder:
def __init__(self):
self.maxHeap = [] # max heap (as negative values)
self.minHeap = [] # min heap

def addNum(self, num: int) -> None:

heapq.heappush(self.maxHeap, -num)
heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))

if len(self.maxHeap) < len(self.minHeap):

heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))

def findMedian(self) -> float:

if len(self.maxHeap) == len(self.minHeap):
 return (-self.maxHeap[0] + self.minHeap[0]) / 2.0
return -self.maxHeap[0]

Problem 2: Sliding Window Median (LeetCode 480)

import heapq
from collections import defaultdict

class MedianSlidingWindow:
def medianSlidingWindow(self, nums, k):
result = []
minHeap = [] # min heap for the larger half
maxHeap = [] # max heap for the smaller half (inverted)
delayed = defaultdict(int)

def prune(heap):
while heap and delayed[heap[0][1]] > 0:
delayed[heap[0][1]] -= 1
heapq.heappop(heap)

def balance():
if len(maxHeap) > len(minHeap) + 1:
val = heapq.heappop(maxHeap)[1]
heapq.heappush(minHeap, (val, val))
elif len(maxHeap) < len(minHeap):
val = heapq.heappop(minHeap)[1]
heapq.heappush(maxHeap, (-val, val))

for i, num in enumerate(nums):

if not maxHeap or num <= maxHeap[0][1]:
heapq.heappush(maxHeap, (-num, num))
else:
heapq.heappush(minHeap, (num, num))

if i >= k:
to_remove = nums[i - k]
delayed[to_remove] += 1
if to_remove <= maxHeap[0][1]:
prune(maxHeap)
else:
prune(minHeap)

balance()

if i >= k - 1:
if k % 2 == 1:
result.append(float(maxHeap[0][1]))
else:
result.append((maxHeap[0][1] + minHeap[0][1]) / 2.0)
 return result

Problem 3: IPO (Maximize Capital) (LeetCode 502)

import heapq

def findMaximizedCapital(k, w, profits, capital):

minCapital = list(zip(capital, profits))
heapq.heapify(minCapital) # Min-heap based on capital
maxProfit = []

for _ in range(k):
while minCapital and minCapital[0][0] <= w:
_, profit = heapq.heappop(minCapital)
heapq.heappush(maxProfit, -profit) # Max-heap using negative profits
if not maxProfit:
break
w += -heapq.heappop(maxProfit)

return w

Problem 4: K Closest Points to Origin (LeetCode 973)

import heapq

def kClosest(points, K):

maxHeap = []

for p in points:
dist = -(p[0]**2 + p[1]**2)
heapq.heappush(maxHeap, (dist, p))
if len(maxHeap) > K:
heapq.heappop(maxHeap)

return [point for _, point in maxHeap]

Problem 5: Next Interval (LeetCode 436)

import heapq

def findRightInterval(intervals):
n = len(intervals)
maxStartHeap = [(-intervals[i][0], i) for i in range(n)]
maxEndHeap = [(-intervals[i][1], i) for i in range(n)]
 heapq.heapify(maxStartHeap)
heapq.heapify(maxEndHeap)
result = [-1] * n

while maxEndHeap:
end, endIdx = heapq.heappop(maxEndHeap)
end = -end

if maxStartHeap and -maxStartHeap[0][0] >= end:

start = None
while maxStartHeap and -maxStartHeap[0][0] >= end:
start = heapq.heappop(maxStartHeap)
result[endIdx] = start[1]
heapq.heappush(maxStartHeap, start)

return result

Part 10: Subsets Pattern

Pattern Overview:
The Subsets Pattern deals with generating all possible subsets (or combinations, permutations) from a
given set of elements. It's heavily based on recursion and backtracking, where the algorithm explores all
possibilities step by step, then backtracks to explore alternatives.

When to Use:
Problems requiring generation of combinations or permutations.
Finding subsets satisfying certain conditions.
Backtracking scenarios with exhaustive exploration.

How it Works (Example):

Set: [1, 3, 5]

Subsets generated:

[]

[1]

[3]

[5]

[1,3]

[1,5]

[3,5]

[1,3,5]
Problems:

Problem 1: Subsets (LeetCode 78)

def subsets(nums):
result = []
subset = []

def backtrack(start):
result.append(list(subset))
for i in range(start, len(nums)):
subset.append(nums[i])
backtrack(i + 1)
subset.pop()

backtrack(0)
return result

Problem 2: Subsets with Duplicates (LeetCode 90)

def subsetsWithDup(nums):
nums.sort()
res = []
temp = []

def backtrack(start):
res.append(list(temp))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
temp.append(nums[i])
backtrack(i + 1)
temp.pop()

backtrack(0)
return res

Problem 3: Permutations (LeetCode 46)

def permute(nums):
res = []
temp = []
used = [False] * len(nums)

def backtrack():
if len(temp) == len(nums):
 res.append(temp[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
temp.append(nums[i])
backtrack()
temp.pop()
used[i] = False

backtrack()
return res

Problem 4: Letter Case Permutation (LeetCode 784)

def letterCasePermutation(s):
res = []
s = list(s)

def backtrack(idx):
if idx == len(s):
res.append(''.join(s))
return
if s[idx].isalpha():
s[idx] = s[idx].lower()
backtrack(idx + 1)
s[idx] = s[idx].upper()
backtrack(idx + 1)
else:
backtrack(idx + 1)

backtrack(0)
return res

Problem 5: Combination Sum (LeetCode 39)

def combinationSum(candidates, target):

res = []
candidates.sort()

def backtrack(remain, start, temp):

if remain < 0:
return
elif remain == 0:
res.append(list(temp))
else:
 for i in range(start, len(candidates)):
temp.append(candidates[i])
backtrack(remain - candidates[i], i, temp)
temp.pop()

backtrack(target, 0, [])
return res

Part 11: Modified Binary Search

Pattern Overview:
The Modified Binary Search pattern extends traditional binary search to solve problems where a direct
sorted search isn't enough. It’s commonly used for sorted arrays that are rotated, infinite arrays, or arrays
with duplicates.

When to Use:
Sorted arrays with special conditions (rotated, infinite size, unknown boundaries).
Searching for an element with conditions beyond simple equality.
Problems requiring efficient logarithmic search with complex conditions.

How it Works (Example):

Example: Find an element in a rotated sorted array.

Array: [4,5,6,7,0,1,2], target = 0

Standard binary search fails directly, but by modifying conditions,

we can efficiently search in O(log n).

Problems:

Problem 1: Search in Rotated Sorted Array (LeetCode 33)

def search(nums, target):

left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 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

Problem 2: Find Minimum in Rotated Sorted Array (LeetCode 153)

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

Problem 3: Search in a Sorted Array of Unknown Size (Infinite Array)

class ArrayReader:
def get(self, index: int) -> int:
# This should be implemented externally
pass

def search(reader: ArrayReader, target: int) -> int:

start, end = 0, 1
while reader.get(end) < target:
start = end
end <<= 1 # equivalent to end *= 2

while start <= end:

mid = start + (end - start) // 2
mid_val = reader.get(mid)
if mid_val == target:
return mid
elif mid_val < target:
start = mid + 1
else:
end = mid - 1

return -1
Problem 4: Peak Index in a Mountain Array (LeetCode 852)

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

Problem 5: Search for a Range (Find First and Last Position - LeetCode 34)

def searchRange(nums, target):

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

start = findBound(nums, target, True)

end = findBound(nums, target, False) if start != -1 else -1
return [start, end]

Part 12: Topological Sort

Pattern Overview:
The Topological Sort pattern is used to find a linear ordering of vertices in a Directed Acyclic Graph
(DAG) such that for every directed edge u → v, vertex u comes before v in the ordering.

This is widely used in scheduling, build systems, task ordering, and dependency resolution.
When to Use:
Scheduling tasks with dependencies.
Course scheduling problems.
Build order problems.
Cycle detection in directed graphs.

How it Works (Example):

Given a graph:

1→2→3

↓ ↑

4→5→6

Valid Topological Orders:

One possible order: 1, 4, 5, 6, 2, 3

Core Idea:

Use

BFS

with in-degree counts (Kahn’s Algorithm) or

DFS

with stack to maintain order.

Problems:

Problem 1: Topological Sort of a Graph (Kahn’s Algorithm)

from collections import deque, defaultdict

def topologicalSort(vertices, edges):

sortedOrder = []
graph = defaultdict(list)
inDegree = {i: 0 for i in range(vertices)}

for u, v in edges:
graph[u].append(v)
inDegree[v] += 1

sources = deque([v for v in inDegree if inDegree[v] == 0])

while sources:
vertex = sources.popleft()
sortedOrder.append(vertex)
for child in graph[vertex]:
 inDegree[child] -= 1
if inDegree[child] == 0:
sources.append(child)

return sortedOrder if len(sortedOrder) == vertices else []

Problem 2: Course Schedule (LeetCode 207)

from collections import defaultdict, deque

def canFinish(numCourses, prerequisites):

graph = defaultdict(list)
inDegree = [0] * numCourses

for dest, src in prerequisites:

graph[src].append(dest)
inDegree[dest] += 1

queue = deque([i for i in range(numCourses) if inDegree[i] == 0])

completed = 0
while queue:
course = queue.popleft()
completed += 1
for next_course in graph[course]:
inDegree[next_course] -= 1
if inDegree[next_course] == 0:
queue.append(next_course)

return completed == numCourses

Problem 3: Course Schedule II (LeetCode 210)

from collections import defaultdict, deque

def findOrder(numCourses, prerequisites):

graph = defaultdict(list)
inDegree = [0] * numCourses

for dest, src in prerequisites:

graph[src].append(dest)
inDegree[dest] += 1

queue = deque([i for i in range(numCourses) if inDegree[i] == 0])

order = []

while queue:
 course = queue.popleft()
order.append(course)

for next_course in graph[course]:

inDegree[next_course] -= 1
if inDegree[next_course] == 0:
queue.append(next_course)

return order if len(order) == numCourses else []

Problem 4: Alien Dictionary (LeetCode 269)

from collections import defaultdict, deque

def alienOrder(words):
graph = defaultdict(set)
inDegree = {}

# Initialize inDegree for all unique characters

for word in words:
for c in word:
inDegree[c] = 0

# Build the graph and update inDegree

for i in range(len(words) - 1):
first, second = words[i], words[i + 1]
minLen = min(len(first), len(second))
found = False
for j in range(minLen):
a, b = first[j], second[j]
if a != b:
if b not in graph[a]:
graph[a].add(b)
inDegree[b] += 1
found = True
break
if not found and len(first) > len(second):
return ""

# Queue for characters with zero inDegree

q = deque([c for c in inDegree if inDegree[c] == 0])
result = []

while q:
c = q.popleft()
result.append(c)
for nei in graph[c]:
inDegree[nei] -= 1
if inDegree[nei] == 0:
 q.append(nei)

return "".join(result) if len(result) == len(inDegree) else ""

Problem 5: Sequence Reconstruction (LeetCode 444)

from collections import defaultdict, deque

def sequenceReconstruction(org, seqs):

graph = defaultdict(set)
inDegree = {}

# Initialize inDegree for all numbers in seqs

for seq in seqs:
for num in seq:
if num not in inDegree:
inDegree[num] = 0

# Build graph and compute inDegree

for seq in seqs:
for i in range(1, len(seq)):
u, v = seq[i - 1], seq[i]
if v not in graph[u]:
graph[u].add(v)
inDegree[v] += 1

# If number of unique nodes doesn't match org size, return False

if len(inDegree) != len(org):
return False

q = deque([node for node in inDegree if inDegree[node] == 0])

idx = 0

while q:
if len(q) > 1:
return False # Multiple choices, no unique sequence
node = q.popleft()
if idx >= len(org) or org[idx] != node:
return False
idx += 1
for nei in graph[node]:
inDegree[nei] -= 1
if inDegree[nei] == 0:
q.append(nei)

return idx == len(org)

Part 13: Bitwise XOR Pattern

Pattern Overview:
The Bitwise XOR Pattern is based on the fundamental properties of the XOR (^) operation:
a ^ a = 0 (a number XORed with itself cancels out)
a ^ 0 = a (a number XORed with zero remains unchanged)
XOR is commutative and associative
This pattern is very efficient for finding unique elements and solving low-level binary problems in O(n)
time and O(1) space.

When to Use:
Finding the single number in arrays where all other numbers occur in pairs.
Finding two unique numbers in arrays.
Swapping variables without using extra space.
Detecting missing or duplicate numbers using XOR.
Parity check or bitwise tricks.

How it Works (Example):

Find the unique number in an array:

Array: [1, 2, 3, 2, 1]

Process: 1 ^ 2 ^ 3 ^ 2 ^ 1 = (1 ^ 1) ^ (2 ^ 2) ^ 3 = 0 ^ 0 ^ 3 = 3

Problems:

Problem 1: Single Number (LeetCode 136)

def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result

Key Concept:

When all numbers appear twice except one, XOR all elements → duplicates cancel out.

Problem 2: Single Number III (LeetCode 260)

Find the two numbers that appear only once when all others appear twice.

from typing import List

def singleNumber(nums: List[int]) -> List[int]:

xorVal = 0
 for num in nums:
xorVal ^= num

diffBit = xorVal & (-xorVal)

result = [0, 0]

for num in nums:

if (num & diffBit) == 0:
result[0] ^= num
else:
result[1] ^= num

return result

Key Concept:

Use the rightmost set bit to partition numbers into two groups

Problem 3: Find Missing Number (LeetCode 268)

from typing import List

def missingNumber(nums: List[int]) -> int:

n = len(nums)
xorVal = 0
for i in range(n):
xorVal ^= i ^ nums[i]
return xorVal ^ n

Key Concept:

XOR from 0 to n and XOR all array elements. The missing number remains.

Problem 4: Counting Bits (LeetCode 338)

from typing import List

def countBits(n: int) -> List[int]:

dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp

Key Concept:

Using right shift and bitwise AND to count number of 1’s efficiently

Problem 5: Sum of Two Integers (LeetCode 371)

Add two numbers without using + or -.

def getSum(a: int, b: int) -> int:

while b != 0:
carry = (a & b) << 1
a = a ^ b
b = carry
return a

Key Concept:

Simulate binary addition using XOR for sum and AND for carry.

Part 14: Fast Exponentiation (Binary Exponentiation)

Pattern Overview:
The Fast Exponentiation (or Binary Exponentiation) pattern is an efficient method to compute large
exponents in O(log n) time using the divide and conquer principle.

Instead of multiplying the base n times, it squares the base and divides the exponent by 2 at each step.

When to Use:
Calculating large power values modulo some number.
Modular inverse calculations.
Efficient power calculations for cryptography.
Solving exponential growth problems.

How it Works (Example):

To compute:

3^13 = 3^(1101)₂

Breakdown:

3^13 = 3^8 * 3^4 * 3^1

(square and multiply method)

Steps:
Start with result = 1
If exponent is odd → multiply result by base
Square base each time
Divide exponent by 2
Problems:

Problem 1: Power Function (LeetCode 50)

def myPow(x: float, n: int) -> float:

if n == 0:
return 1

N = n
if N < 0:
x = 1 / x
N = -N

result = 1
while N > 0:
if N % 2 == 1:
result *= x
x *= x
N //= 2

return result

Key Concept:

Divide the exponent by 2 each time and square the base.

Problem 2: Modular Exponentiation

def modPow(x: int, n: int, mod: int) -> int:

result = 1
base = x % mod

while n > 0:
if n & 1:
result = (result * base) % mod
base = (base * base) % mod
n >>= 1

return result

Key Concept:

Always take modulo to prevent integer overflow.

Problem 3: Super Pow (LeetCode 372)

def modPow(x: int, n: int, mod: int) -> int:

result = 1
 x %= mod

while n > 0:
if n % 2 == 1:
result = (result * x) % mod
x = (x * x) % mod
n //= 2
return result

def superPow(a: int, b: list[int]) -> int:

mod = 1337
result = 1

for digit in b:
result = (modPow(result, 10, mod) * modPow(a, digit, mod)) % mod

return result

Key Concept:

Handles very large exponents using fast modular exponentiation

Problem 4: Check if Power of Two (LeetCode 231)

def isPowerOfTwo(n: int) -> bool:

return n > 0 and (n & (n - 1)) == 0

Key Concept:

Power of two has only one bit set in binary form

Problem 5: Implement pow(x, n) with Recursion

def fastPower(x: float, n: int) -> float:

if n == 0:
return 1

half = fastPower(x, n // 2)

if n % 2 == 0:
return half * half
else:
return half * half * x if n > 0 else half * half / x

Key Concept:

Divide and conquer recursive approach.

Part 15: Greedy Pattern

Pattern Overview:
The Greedy Pattern solves optimization problems by making locally optimal choices at each step with
the hope of finding a global optimum.

Greedy algorithms work when the problem has the greedy-choice property and optimal substructure —
meaning a locally optimal solution leads to a globally optimal one.

When to Use:
Interval scheduling problems.
Activity selection problems.
Finding minimum coins or jumps.
Optimization where you can make a greedy decision without revisiting.
Problems requiring minimal/maximal total cost, length, or time.

How it Works (Example):

Example: Select the maximum number of non-overlapping meetings.
Sort by end times.
Always pick the meeting that ends earliest.
Skip overlapping meetings.
This greedy approach works because selecting the earliest end time leaves room for the maximum
number of remaining meetings.

Problems:

Problem 1: Jump Game II (Minimum Jumps - LeetCode 45)

def jump(nums: list[int]) -> int:

jumps = 0
farthest = 0
currentEnd = 0

for i in range(len(nums) - 1):

farthest = max(farthest, i + nums[i])
if i == currentEnd:
jumps += 1
currentEnd = farthest

return jumps

Key Concept:

Always jump to the farthest reachable point.

Problem 2: Partition Labels (LeetCode 763)

def partitionLabels(s: str) -> list[int]:

lastIndex = [0] * 26
for i, ch in enumerate(s):
lastIndex[ord(ch) - ord('a')] = i

result = []
start, end = 0, 0

for i, ch in enumerate(s):
end = max(end, lastIndex[ord(ch) - ord('a')])
if i == end:
result.append(end - start + 1)
start = i + 1

return result

Key Concept:
Greedily choose the largest partition without overlapping characters.

Problem 3: Non-overlapping Intervals (LeetCode 435)

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:

intervals.sort(key=lambda x: x[1])

end = intervals[0][1]
count = 1
for i in range(1, len(intervals)):
if intervals[i][0] >= end:
count += 1
end = intervals[i][1]
return len(intervals) - count

Key Concept:
Greedily keep intervals with the earliest end times to maximize non-overlapping intervals.

Problem 4: Minimum Number of Arrows to Burst Balloons (LeetCode 452)

def findMinArrowShots(points):
if not points:
return 0
 points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]

for i in range(1, len(points)):

if points[i][0] > end:
arrows += 1
end = points[i][1]

return arrows

Key Concept:

Greedily shoot the arrow at the end of the current balloon's range.

Problem 5: Assign Cookies (LeetCode 455)

def findContentChildren(g, s):

g.sort()
s.sort()

child = cookie = 0
while child < len(g) and cookie < len(s):
if s[cookie] >= g[child]:
child += 1
cookie += 1
return child

Key Concept:

Always assign the smallest available cookie that satisfies the current child.

Part 16: Dynamic Programming

Pattern Overview:
The Dynamic Programming Pattern solves complex problems by breaking them down into overlapping
subproblems and solving each subproblem only once, storing its result.

It is typically used when:

The problem has optimal substructure (the solution to the problem depends on solutions to smaller
subproblems).
The problem has overlapping subproblems.

When to Use:
Problems that can be divided into smaller, similar subproblems.
 Optimization problems (minimum, maximum, longest, shortest).
When recursive brute-force solutions cause repeated calculations.
When memoization or bottom-up tabulation is possible.

How it Works (Example):

Fibonacci Sequence:

Fib(0) = 0, Fib(1) = 1

Fib(n) = Fib(n-1) + Fib(n-2)

Without DP → O(2^n) time

With DP → O(n) time

Store previously calculated values to avoid recomputation.

Problems:

Problem 1: Climbing Stairs (LeetCode 70)

def climbStairs(n):
if n <= 2:
return n

first, second = 1, 2
for _ in range(3, n + 1):
ways = first + second
first = second
second = ways

return second

Key Concept:

Number of ways to reach step n is the sum of ways to reach n-1 and n-2.

Problem 2: House Robber (LeetCode 198)

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], nums[i] + dp[i - 2])

return dp[-1]

Key Concept:

At each house, rob it or skip it, whichever yields the maximum profit.

Problem 3: Longest Palindromic Subsequence (LeetCode 516)

def longestPalindromeSubseq(s: str) -> int:

n = len(s)
dp = [[0] * n for _ in range(n)]

for i in range(n - 1, -1, -1):

dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = 2 + dp[i + 1][j - 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

return dp[0][n - 1]

Key Concept:

Build solutions for small substrings and expand them.

Problem 4: Coin Change (LeetCode 322)

def coinChange(coins: List[int], amount: int) -> int:

dp = [amount + 1] * (amount + 1)
dp[0] = 0

for i in range(1, amount + 1):

for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)

return -1 if dp[amount] > amount else dp[amount]

Key Concept:

Bottom-up calculation to find the minimum number of coins for each amount.

Problem 5: Edit Distance (LeetCode 72)

 def minDistance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(m + 1):

dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j

for i in range(1, m + 1):

for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # replace
dp[i][j - 1], # insert
dp[i - 1][j] # delete
)

return dp[m][n]

Key Concept:

Classic DP for string transformation problems using insertion, deletion, and substitution.

Part 17: Matrix Traversal

Pattern Overview:
The Matrix Traversal Pattern is commonly used to solve problems involving 2D grids or matrices. It often
requires exploring cells in a particular direction (up, down, left, right, or diagonally) and may involve
backtracking, BFS, DFS, or simple iteration.

When to Use:
Pathfinding in a matrix.
Counting islands or connected components.
Searching for patterns in grids.
Flood-fill algorithms.
Simulating spread (e.g. infection, fire).

How it Works (Example):

Example: Traversing a matrix to count connected islands

Grid:
11000

01001

10011

00000

10101

Traverse in all 4 directions from each "1" that is not visited.

Mark cells as visited during traversal.

Use DFS or BFS to explore connected regions.

Common movement directions:

int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};

Problems:

Problem 1: Number of Islands (LeetCode 200)

def numIslands(grid: List[List[str]]) -> int:

if not grid:
return 0

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

def dfs(i, j):

if i < 0 or j < 0 or i >= rows or j >= cols or grid[i][j] == '0':
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)
count += 1
return count

Key Concept:

Use DFS to explore and mark the entire island.

Problem 2: Word Search (LeetCode 79)

 def exist(board: List[List[str]], word: str) -> bool:
def dfs(i, j, index):
if index == len(word):
return True
if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] != wo
return False

temp = board[i][j]
board[i][j] = '#' # Mark as visited

found = (dfs(i - 1, j, index + 1) or

dfs(i + 1, j, index + 1) or
dfs(i, j - 1, index + 1) or
dfs(i, j + 1, index + 1)

board[i][j] = temp # Restore original value

return found

for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0):
return True
return False

Key Concept:

Use backtracking to search for the word in all directions.

Problem 3: Rotting Oranges (LeetCode 994)

from collections import deque

def orangesRotting(grid: List[List[int]]) -> int:

rows, cols = len(grid), len(grid[0])
q = deque()
fresh = 0
minutes = 0

# Initialize queue with rotten oranges and count fresh oranges

for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
fresh += 1

# Directions for adjacent cells (up, down, left, right)

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 while q and fresh > 0:
# Process all current rotten oranges in this minute
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in dirs:
x, y = r + dr, c + dc
if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 1:
grid[x][y] = 2
q.append((x, y))
fresh -= 1
minutes += 1

return minutes if fresh == 0 else -1

Key Concept:

Use multi-source BFS to simulate spreading (level by level).

Problem 4: Flood Fill (LeetCode 733)

def floodFill(image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int
oldColor = image[sr][sc]
if oldColor == newColor:
return image

rows, cols = len(image), len(image[0])

def dfs(i, j):

if i < 0 or j < 0 or i >= rows or j >= cols or image[i][j] != oldColor:
return
image[i][j] = newColor
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)

dfs(sr, sc)
return image

Key Concept:

Classic DFS-based flood-fill like a paint tool.

Problem 5: Shortest Path in Binary Matrix (LeetCode 1091)

from collections import deque

def shortestPathBinaryMatrix(grid: List[List[int]]) -> int:

n = len(grid)
 if grid[0][0] != 0 or grid[n-1][n-1] != 0:
return -1

q = deque()
q.append((0, 0))
grid[0][0] = 1 # Mark as visited

# 8 possible directions
dirs = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]

path_length = 1

while q:
size = len(q)
for _ in range(size):
x, y = q.popleft()

if x == n-1 and y == n-1:

return path_length

for dx, dy in dirs:

new_x, new_y = x + dx, y + dy
if 0 <= new_x < n and 0 <= new_y < n and grid[new_x][new_y] == 0:
q.append((new_x, new_y))
grid[new_x][new_y] = 1 # Mark as visited
path_length += 1

return -1

Key Concept:

Use BFS to find the shortest path in a grid, visiting all eight directions.

Part 18: Backtracking Pattern

Pattern Overview:
The Backtracking Pattern is a systematic way of trying out all possible configurations to solve a problem.

It incrementally builds candidates for the solution and abandons a candidate (“backtracks”) as soon as it
determines that the candidate cannot lead to a valid solution.

It is commonly used in combinatorial problems where you need to:

Explore all possibilities.
Find all valid combinations or permutations.
Solve constraint satisfaction problems.
When to Use:
Problems asking for all subsets, permutations, or combinations.
Problems that require exploring all decision trees.
Problems with constraints (sudoku, n-queens).
Recursive problems that can prune invalid paths early.

How it Works (Example):

Example: Generate all subsets of a set {1, 2, 3}

Start with empty set → try adding each number → recursively explore → backtrack

Tree structure:

[]

/ | \

1 2 3

/ \ / \ /\

2 33 - -

At each node:
Include the current element.
Exclude the current element.
Backtrack to previous state.

Problems:

Problem 1: Subsets (LeetCode 78)

def subsets(nums: List[int]) -> List[List[int]]:

result = []

def backtrack(start, current):

result.append(current.copy())
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()

backtrack(0, [])
return result

Key Concept:

Recursive tree to explore all subsets by adding/removing elements.

Problem 2: Permutations (LeetCode 46)

def permute(nums: List[int]) -> List[List[int]]:

result = []

def backtrack(current):
if len(current) == len(nums):
result.append(current.copy())
return
for num in nums:
if num in current:
continue
current.append(num)
backtrack(current)
current.pop()

backtrack([])
return result

Key Concept:

Try each unused number in the current position.

Problem 3: Combination Sum (LeetCode 39)

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:

result = []

def backtrack(start, remain, current):

if remain == 0:
result.append(current.copy())
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
continue
current.append(candidates[i])
backtrack(i, remain - candidates[i], current)
current.pop()

backtrack(0, target, [])

return result

Key Concept:

At each step, decide whether to include a candidate (repeats allowed).

Problem 4: N-Queens Problem (LeetCode 51)

 def solveNQueens(n: int) -> List[List[str]]:
result = []
positions = [0] * n # Track queen positions for each row

def backtrack(row):
if row == n:
# Generate the board configuration
board = []
for i in range(n):
row_str = ['.'] * n
row_str[positions[i]] = 'Q'
board.append(''.join(row_str))
result.append(board)
return

for col in range(n):

valid = True
# Check if current column is valid
for i in range(row):
# Same column or diagonal conflict
if positions[i] == col or abs(positions[i] - col) == row - i:
valid = False
break
if valid:
positions[row] = col
backtrack(row + 1)

backtrack(0)
return result

Key Concept:

Recursive placement with validity checks to prune paths.

Problem 5: Sudoku Solver (LeetCode 37)

def solveSudoku(board: List[List[str]]) -> None:

backtrack(board)

def backtrack(board: List[List[str]]) -> bool:

for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if isValid(board, i, j, num):
board[i][j] = num
if backtrack(board):
return True
board[i][j] = '.' # backtrack
 return False
return True

def isValid(board: List[List[str]], row: int, col: int, num: str) -> bool:
# Check row and column
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False

# Check 3x3 sub-box

box_row = (row // 3) * 3
box_col = (col // 3) * 3
for i in range(3):
for j in range(3):
if board[box_row + i][box_col + j] == num:
return False

return True

Key Concept:

Recursively fill empty cells while checking Sudoku constraints.

Part 19: Divide & Conquer Pattern

Pattern Overview:
The Divide & Conquer Pattern breaks a large problem into smaller subproblems of the same type, solves
them recursively, and combines their solutions to solve the original problem.

It’s a powerful technique used in many efficient algorithms, including:

Merge Sort
Quick Sort
Binary Search
Matrix Multiplication
Closest Pair of Points

When to Use:
Problems that can be split into independent subproblems.
Sorting and searching problems.
Tree problems (naturally divide into subtrees).
Problems where you can break input into smaller chunks.

How it Works (Example):

Example: Merge Sort
Array: [6, 3, 8, 5, 2]

1. Divide → split array into halves

2. Conquer → recursively sort each half

3. Combine → merge two sorted halves

Divide until size = 1 → Combine back

Time Complexity: O(n log n)

Problems:

Problem 1: Merge Sort Implementation

def quick_sort(nums: List[int], low: int = 0, high: int = None) -> None:
if high is None:
high = len(nums) - 1
if low < high:
pivot_index = partition(nums, low, high)
quick_sort(nums, low, pivot_index - 1)
quick_sort(nums, pivot_index + 1, high)

def partition(nums: List[int], low: int, high: int) -> int:

pivot = nums[high]
i = low - 1

for j in range(low, high):

if nums[j] < pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]

nums[i + 1], nums[high] = nums[high], nums[i + 1]

return i + 1

Key Concept:

Divide into halves → recursively sort → merge.

Problem 2: Quick Sort Implementation

def quick_sort(nums: list, low: int = 0, high: int = None) -> None:
"""Sorts the list in-place using quicksort algorithm"""
if high is None:
high = len(nums) - 1
if low < high:
pivot_index = partition(nums, low, high)
quick_sort(nums, low, pivot_index - 1)
quick_sort(nums, pivot_index + 1, high)
 def partition(nums: list, low: int, high: int) -> int:
"""Lomuto partition scheme"""
pivot = nums[high] # Choose last element as pivot
i = low - 1 # Index for smaller elements

for j in range(low, high):

if nums[j] < pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i] # Swap

nums[i + 1], nums[high] = nums[high], nums[i + 1] # Move pivot to correct positio

return i + 1 # Return pivot index

# Example usage
if __name__ == "__main__":
data = [10, 7, 8, 9, 1, 5]
print("Original array:", data)
quick_sort(data)
print("Sorted array:", data)

Key Concept:

Partition the array and recursively sort partitions.

Problem 3: Binary Search (LeetCode 704)

def binary_search(nums: list, target: int) -> int:

left, right = 0, len(nums) - 1

while left <= right:

mid = left + (right - left) // 2 # Prevents integer overflow (though not neede

if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1

Key Concept:

Divide search space in half each time → O(log n) time.

Problem 4: Search in Rotated Sorted Array (LeetCode 33)

def search(nums: List[int], target: int) -> int:

left, right = 0, len(nums) - 1
 while left <= right:
mid = left + (right - left) // 2

if nums[mid] == target:
return mid

# Left half is sorted

if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1

return -1

Key Concept:

Adapt binary search to work with rotation.

Problem 5: Kth Largest Element in an Array (LeetCode 215)

import random

def partition(nums: List[int], left: int, right: int) -> int:

"""Lomuto partition scheme with random pivot selection"""
pivot_idx = random.randint(left, right) # Random pivot for better average performa
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] # Move pivot to end
pivot = nums[right]
i = left

for j in range(left, right):

if nums[j] <= pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1

nums[i], nums[right] = nums[right], nums[i] # Move pivot to final position

return i

def quick_select(nums: List[int], left: int, right: int, k_smallest: int) -> int:
"""Recursive quickselect implementation"""
if left == right:
return nums[left]
 pivot_index = partition(nums, left, right)

if pivot_index == k_smallest:
return nums[pivot_index]
elif pivot_index < k_smallest:
return quick_select(nums, pivot_index + 1, right, k_smallest)
else:
return quick_select(nums, left, pivot_index - 1, k_smallest)

def findKthLargest(nums: List[int], k: int) -> int:

"""Returns the k-th largest element in the array"""
return quick_select(nums, 0, len(nums) - 1, len(nums) - k)

Key Concept:

Quickselect efficiently finds the kth largest without fully sorting.

Part 20: Graph Traversal Pattern

Pattern Overview:
The Graph Traversal Pattern is used to explore nodes and edges in a graph using systematic methods
like Breadth-First Search (BFS) and Depth-First Search (DFS).

This pattern is essential when working with:

Connected components
Pathfinding
Cycle detection
Graph-based simulations
Graph traversal helps to visit each node in a structured order to solve problems like shortest path, island
counting, and network spread.

When to Use:
Problems involving graphs, grids, or networks.
When you need to visit all nodes, find paths, detect cycles, or explore components.
Problems that can be represented as adjacency lists or matrices.

How it Works (Example):

Example: BFS Traversal of Graph

Graph:

A-B-C

| |
D-E

Start BFS from node A:

Queue: [A]

Visit: A → B → D → C → E

BFS:
Explore level by level.
Uses a queue.

DFS:
Explore as deep as possible.
Uses

recursion or stack.

Problems:

Problem 1: Clone Graph (LeetCode 133).

from collections import deque

class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: 'Node') -> 'Node':

if not node:
return None

# Dictionary to map original nodes to their clones

node_map = {}
queue = deque([node])
node_map[node] = Node(node.val)

while queue:
current = queue.popleft()
for neighbor in current.neighbors:
if neighbor not in node_map:
# Clone the neighbor if not already cloned
node_map[neighbor] = Node(neighbor.val)
queue.append(neighbor)
# Connect the cloned node to its cloned neighbors
node_map[current].neighbors.append(node_map[neighbor])

return node_map[node]
Key Concept:

Use BFS to clone graph nodes and their connections

Problem 2: Course Schedule (LeetCode 207 - Topological Sort / Cycle Detection).

from collections import deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:

# Initialize graph and in-degree count
graph = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses

# Build the graph and in-degree count

for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1

# Initialize queue with courses having no prerequisites

queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
completed = 0

# Process the queue

while queue:
course = queue.popleft()
completed += 1

# Reduce in-degree for neighbors and add to queue if in-degree becomes 0

for neighbor in graph[course]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)

return completed == numCourses

Key Concept:

BFS for topological sorting to detect cycles.

Problem 3: Number of Connected Components (LeetCode 323)

def countComponents(n: int, edges: List[List[int]]) -> int:

# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # Undirected graph
 visited = [False] * n
count = 0

def dfs(node):
if visited[node]:
return
visited[node] = True
for neighbor in graph[node]:
dfs(neighbor)

# Count connected components

for i in range(n):
if not visited[i]:
dfs(i)
count += 1

return count

Key Concept:

Use DFS to explore each connected component.

Problem 4: Graph Valid Tree (LeetCode 261)

from collections import deque

def validTree(n: int, edges: List[List[int]]) -> bool:

# A tree must have exactly n-1 edges
if len(edges) != n - 1:
return False

# Build adjacency list

graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)

# Check for cycles and connectivity using BFS

visited = [False] * n
parent = [-1] * n
queue = deque([0])
visited[0] = True

while queue:
node = queue.popleft()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
parent[neighbor] = node
queue.append(neighbor)
 elif neighbor != parent[node]:
# Found a cycle
return False

# Check if all nodes are connected

return all(visited)

Key Concept:

A valid tree has no cycles and all nodes are connected.

Problem 5: Word Ladder (LeetCode 127 - Shortest Path in Graph)

from collections import deque

def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:

word_set = set(wordList)
if endWord not in word_set:
return 0

queue = deque([beginWord])
level = 1

while queue:
level_size = len(queue)
for _ in range(level_size):
current_word = queue.popleft()

for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = current_word[:i] + c + current_word[i+1:]

if next_word == endWord:
return level + 1

if next_word in word_set:
queue.append(next_word)
word_set.remove(next_word)
level += 1

return 0

Key Concept:

Use BFS to find the shortest transformation sequence.