Introduction
This is a quick chapter. The idea behind divide and conquer is recursive – imagine we have some hammer that solves a problem T(n). Now, if we split our subproblems we can solve them using this same hammer, however we are just missing a 'join' step – how do we combine the results of T on our subproblems to result in T(n)?
We can reason about the time complexity of such recursive problems using Master Theorem or Akra Bazzi Theorem.
The key insight is that divide and conquer breaks a problem into smaller subproblems, solves them recursively, and then combines the results. The "join" step is often the creative part of the algorithm.
Merge Sort
This is a very commonly known sorting algorithm. The idea to sort an array, is to imagine we can sort an array A 'somehow'. If we split the array into a left and right half, let's sort these subarrays using this magical method. Now, what remains is – how can we combine/join two sorted subarrays into one sorted array?
Well that is simple, its a leetcode easy – merge 2 sorted arrays.
01Merge Sorted ArrayEasy
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i = m - 1
j = n - 1
while i >= 0 and j >= 0:
if nums1[i] >= nums2[j]:
nums1[i + j + 1] = nums1[i]
i -= 1
else:
nums1[i + j + 1] = nums2[j]
j -= 1
while j >= 0:
nums1[j] = nums2[j]
j -= 1O(m + n)O(1)Basically we start at either end of the 2 arrays. If i = 0, j = 0. If nums1[i] < nums2[j], we add nums1[i] as the global minimum of both arrays and increment i. Otherwise we add nums2[j] and increment j. Repeat. This code is a little different because we want to do it in place in nums1.
02Sort an ArrayMedium
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.
def sortArray(self, nums: List[int]) -> List[int]:
def merge(A, B):
i = j = 0
m, n = len(A), len(B)
res = []
while i < m and j < n:
if A[i] < B[j]:
res.append(A[i])
i += 1
else:
res.append(B[j])
j += 1
while i < m:
res.append(A[i])
i += 1
while j < n:
res.append(B[j])
j += 1
return res
def mergeSort(nums):
n = len(nums)
if n <= 1: return nums
left = mergeSort(nums[:n//2])
right = mergeSort(nums[n//2:])
return merge(left, right)
return mergeSort(nums)O(n log n)O(n)Using this merge(A,B) function, we can write the pseudocode for merge Sort. (don't forget for recursion the base case, if length 1 we are already sorted.)
Merge Sort Pseudocode:
mergeSort(A):
N = len(A)
If N == 1: return A
Left = mergeSort(A[:N//2])
Right = mergeSort(A[N//2:])
Return merge(Left, Right)We can model the time taken as: T(n) = 2*T(n//2) + O(n), which is T(n) = O(nlogn) using master theorem. This is because we split into 2 subproblems of n//2, and at each step we do O(n) work in the merge(A,B) function.
Count Inversions
This problem isn't on leetcode to my understanding, but it is important to know.
Inversions are defined as pairs of indices (i,j) where nums[i] > nums[j].
For example: [1,7,3,6]. (1,2), (1,3) are the two inversions.
A common problem is to count the number of inversions in an array. We can clearly brute force this in O(N^2) time.
We can use the merge sort divide and conquer idea to count the number of inversions in an array in O(nlogn) time.
The idea is, if we have a function f(A) that takes in an array and returns the number of inversions, and we split the array into two halves left and right:
The total number of inversions in A are the number of inversions in left (f(left)) plus the number of inversions in right (f(right)), plus the number of cross inversions between indices i in the left array and indices r in the right array.
So the question is the join function. And the trick is to also do the merge sort in the recursion. Given two sorted arrays, how can we count the number of inversions in the merge(A,B) function?
Example
For example:
[1,4,7], [3,8,10]
The cross inversions are (in terms of values not indices): (4,3), (7,3)
As we merge these, if nums1[i] > nums2[j], this is clearly an inversion, but not only that, nums1[i] also forms inversions with all indices k < j in nums2! So we can contribute j+1 inversions here.
Code
def sortArray(self, nums: List[int]) -> List[int]:
def merge(A, B):
i = j = 0
m, n = len(A), len(B)
res = []
count_inversions = 0
while i < m and j < n:
if A[i] < B[j]:
res.append(A[i])
i += 1
else:
res.append(B[j])
count_inversions += j + 1
j += 1
while i < m:
res.append(A[i])
i += 1
while j < n:
res.append(B[j])
j += 1
return res, count_inversions
def sort_and_countInversions(nums):
n = len(nums)
if n <= 1: return nums, 0
left, left_inversion_count = sort_and_countInversions(nums[:n//2])
right, right_inversion_count = sort_and_countInversions(nums[n//2:])
combined, cross_inversion_count = merge(left, right)
return combined, left_inversion_count + cross_inversion_count + right_inversion_count
return sort_and_countInversions(nums)[1]Quad Tree Problems
Other examples of divide and conquer: where you build a recursive solution, apply it on subproblems, and join the results of all subproblems together into the answer.
01Construct Quad TreeMedium
Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.
Return the root of the Quad-Tree representing grid.
"""
class Node:
def __init__(self, val, isLeaf, topLeft=None, topRight=None,
bottomLeft=None, bottomRight=None):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution:
def construct(self, grid):
return self.recurse(grid, 0, 0, len(grid))
def recurse(self, grid, i, j, length):
if length == 1:
return Node(grid[i][j], True)
half = length // 2
topLeft = self.recurse(grid, i, j, half)
topRight = self.recurse(grid, i, j + half, half)
bottomLeft = self.recurse(grid, i + half, j, half)
bottomRight = self.recurse(grid, i + half, j + half, half)
if (topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and
topLeft.val == topRight.val == bottomLeft.val == bottomRight.val):
return Node(topLeft.val, True)
else:
return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)O(n)O(n)This is a common problem in your first algorithms course. We construct a recursive build quad tree function with (i,j) coordinates of the top left corner of the square we are building the quad tree over, with (i+length, j+length) as the bottom right corner. The base case is when the square is size 1, this is a leaf node. Otherwise we recursively build the 4 sub quadrant squares.
Now, when is this current node a leaf? When all 4 sub quadrants are leaves, and they all have the same value! Otherwise, this node is an interior node with corresponding sub quad trees.
This is T(n) = 4*T(n/4) + O(1) time = O(n) time.
02Fill a Special GridMedium
You are given a non-negative integer n representing a 2^n x 2^n grid. You must fill the grid with integers from 0 to 2^(2n) - 1 to make it special. A grid is special if it satisfies all the following conditions:
- All numbers in the top-right quadrant are smaller than those in the bottom-right quadrant.
- All numbers in the bottom-right quadrant are smaller than those in the bottom-left quadrant.
- All numbers in the bottom-left quadrant are smaller than those in the top-left quadrant.
- Each of its quadrants is also a special grid.
Return the special 2^n x 2^n grid.
Note: Any 1x1 grid is special.
def specialGrid(self, N: int) -> List[List[int]]:
def dp(n, offset):
if n == 0:
return [[offset]]
sz = 2 ** (2*(n-1))
top_right = dp(n-1, 0)
bottom_right = dp(n-1, sz)
bottom_left = dp(n-1, 2 * sz)
top_left = dp(n-1, 3 * sz)
top = [a + b for a, b in zip(top_left, top_right)]
bottom = [a + b for a, b in zip(bottom_left, bottom_right)]
res = top + bottom
for i in range(len(res)):
for j in range(len(res[0])):
res[i][j] += offset
return res
return dp(N, 0)O(n log n)O(n)I think the best way to explain this is to look at the examples. It's clear that the top right will be 0, bottom right 1, and it will increment in a clockwise fashion. Think about how we build n=2 case from n=1 case. The top right quadrant for n=2 is just n=1. The bottom right is just n=1, but everything is incremented by 4, which is the number of elements in n=1. Similarly, for bottom_left and top_left. Now it's just a question of how do we merge these 4 quadrants into one? You can see we just construct top and bottom and concatenate them, and then finally increment all values in res by offset.
This is T(n) = 4 * T(n//4) + O(n) = O(nlogn) time.
Summary
Conclusion: Being able to think in this divide and conquer, recursive way will not only help you in your interviews, but also help you become a better software engineer.
Key Patterns:
1. Split: Divide the problem into smaller subproblems
2. Solve: Recursively solve the subproblems
3. Combine: Merge the results of subproblems to get the final answer
Time Complexity Analysis:
- Use Master Theorem: T(n) = aT(n/b) + f(n)
- Merge Sort: T(n) = 2T(n/2) + O(n) = O(n log n)
- Quad Tree: T(n) = 4T(n/4) + O(1) = O(n)
Common Applications:
- Sorting (Merge Sort, Quick Sort)
- Matrix multiplication (Strassen's algorithm)
- Tree construction (Quad Tree, Segment Tree)
- Counting inversions