Data Structure and Algorithm 7 | Divide and Conquer

1. Divide-and-Conquer Algorithm

(1) Definition

The divide-and-conquer algorithm recursively breaks down a problem two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

(2) Pseudocode

1
def divide_and_conquer(case):
2
    subcases = divide(case)
3
    results = [conquer(subcase) for subcase in subcases]
4
    return combine(results)

(3) Review: Merge Sort

Time complexity $O(n\log n)$.

Leetcode 912.

xxxxxxxxxx
43
1
def mergesort(data):
2
  
3
    if len(data)==0:
4
        return []
5
      
6
    elif len(data)==1:
7
        return [data[0]]
8
      
9
    elif len(data)==2:
10
        if data[0]<data[1]:
11
            return data
12
        return [data[1], data[0]]
13
      
14
    else:
15
        m = len(data) // 2
16
        left = mergesort(data[0:m])
17
        right = mergesort(data[m:])
18
        return mergeTwoSortedArray(left, right)
19
        
20
def mergeTwoSortedArray(list1, list2):
21
    result = []
22
        
23
    p1 = 0
24
    p2 = 0
25
        
26
    while True:
27
        if p1 == len(list1) and p2 == len(list2):
28
            return result
29
        elif p1 == len(list1):
30
            result.append(list2[p2])
31
            p2 += 1
32
        elif p2 == len(list2):
33
            result.append(list1[p1])
34
            p1 += 1
35
        else:
36
            if list1[p1] > list2[p2]:
37
                result.append(list2[p2])
38
                p2 += 1
39
            else:
40
                result.append(list1[p1])
41
                p1 += 1
42
                
43
   return result

(4) Review: Quick Sort

Time complexity $O(n\log n)$.

Leetcode 912.

​x
1
def partition(a, lo, hi):
2
    pivot = a[hi]
3
    left  = [a[i] for i in range(lo,hi) if a[i]<pivot]
4
    right = [a[i] for i in range(lo,hi) if a[i]>=pivot]
5
    a[lo:hi+1] = left + [pivot] + right
6
    return lo + len(left)
7
​
8
def quickSort(a, low, high):
9
    if low < high:
10
        pi = partition(a, low, high)
11
        quickSort(a, low, pi - 1)
12
        quickSort(a, pi + 1, high)
13
        
14
quickSort(a, 0, len(a)-1)

(5) Valid BST

Given the root of a tree, return if it is a BST.

Leetcode 98.

xxxxxxxxxx
13
1
class Solution:
2
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3
        return self.validate(root)
4
    
5
    def validate(self, node, low=-math.inf, high=math.inf):
6
        
7
        if not node:
8
            return True
9
        
10
        if node.val <= low or node.val >= high:
11
            return False
12
        
13
        return self.validate(node.right, node.val, high) and self.validate(node.left, low, node.val)

(6) Search Matrix I

Search a target element in a sorted matrix. This is a binary search problem.

Leetcode 240.

xxxxxxxxxx
20
1
class Solution:
2
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3
        mat_flat = []
4
        for row in matrix:
5
            mat_flat += row
6
            
7
        left = 0
8
        right = len(mat_flat) - 1
9
        
10
        pivot = right // 2
11
        
12
        while left <= right:
13
            if mat_flat[pivot] > target:
14
                right = pivot - 1
15
                pivot = (left + right) // 2
16
            elif mat_flat[pivot] < target:
17
                left = pivot + 1
18
                pivot = (left + right) // 2
19
            else:
20
                return True

(7) Search Matrix II

Search a target element in a matrix with both sorted columns and sorted rows. The idea is to device the matrix into smaller ones

Leetcode 240.

xxxxxxxxxx
25
1
class Solution:
2
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3
        
4
        if not matrix:
5
            return False
6
        
7
        def search_rec(left, up, right, down):
8
            
9
            if left > right or up > down:
10
                return False
11
            
12
            elif target < matrix[up][left] or target > matrix[down][right]:
13
                return False
14
            
15
            mid = left + (right - left) // 2
16
            row = up
17
            
18
            while row <= down and matrix[row][mid] <= target:
19
                if matrix[row][mid] == target:
20
                    return True
21
                row += 1
22
                
23
            return search_rec(left, row, mid - 1, down) or search_rec(mid+1, up, right, row - 1)
24
        
25
        return search_rec(0, 0, len(matrix[0]) - 1, len(matrix) - 1)