2. Divide & Conquer - swchen1234/Algorithm GitHub Wiki

A typical Divide and Conquer algorithm solves a problem using following three steps.

  1. Divide: Break the given problem into subproblems of same type.
  2. Conquer: Recursively solve these subproblems
  3. Combine: Appropriately combine the answers (This is usually the most challenging part.)

DC 的应用：

  • Merge Sort / Quick Sort
  • 90% 用D&C？

Time & Space Complexity

Although the divide & conquer does not explicitly allocate any additional memory, it uses a non-constant amount of additional memory in stack frames due to recursion. Because the algorithm "cuts" the array in half at each level of recursion, it follows that there can only be O(lgn) "cuts" before the base case of 1 is reached

Traverse vs DC

Traverse Devide & Conquer
Recursion Recursion
Result in parameter Result in return value
Top Down Bottom Up

模版

Traverse 遍历

def traverse(node, result): // （1）定义
    if(not root):  // (2）出口
        return
    result.append(node.val) // （3）拆解
    traverse(node.left)
    traverse(node.right)
    
def traversePreOrder(root):
   result = []
   traverse(root, result)
   return result

Devide & Conquer 遍历

def traversePreOrder(root): // （1）定义
    result = []
    if(not root):  // (2）出口
        return result
    left = traversePreOrder(root.left)
    right = traversePreOrder(root.right) // （3）拆解
    result.append(node.val)
    result.extend(left)
    result.extend(right)
    return result

Problems

1. On 1D Array

variants of merge sort, where the combination go through the all elements through two pointers in both halfs and return a sorted array. For Merge Sort, the worst time is 6n(log2_n + 1).?

[Count of inversion in an array](coursera assignment)
148. Sort List
23. Merge k Sorted Lists 4. Median of Two Sorted Arrays

it is extrememly painful to get this question right, with so many corner cases. There is also a faster binary search version. Suggest to do it again, again....Honestly, I am even not sure if it is an DC solution.

932. Beautiful Array

This hard for me. The key point is to realize if all left part are odd beautiful-array, and all right part is even beautiful array, it remains to be beautiful after concatenation. To construct the left/right part, we need to shrink down the range N to N/2, utilizing the fact that if A is beautiful then A*2 is still beautiful. The code can be solved elegantly from a bottom up approach. This is discussion is helpful.https://leetcode.com/problems/beautiful-array/discuss/186679/C%2B%2BJavaPython-Odd-%2B-Even-Pattern-O(N).

53. Maximum SubarraymaxArray(i, j) = max(maxArray(i, mid-1), maxArray(mid+1, j), maxLeft+nums[mid]+maxRight)， O(nlgn)\

2. On 2D Array

240. Search a 2D Matrix II 找到row r, st. mat[r-1][mid] < target < mat[r][mid], 排除左上&右下，继续在左下&右上寻找，o(nlgn), space O(lgn)

1274. Number of Ships in a Rectangle

3. On Linked List

148. Sort List
Merge k sorted list

4. DC on Tree

108. Convert Sorted Array to Binary Search Tree 427. Construct Quad Tree细分后判断四个sub-grid的值是否一样&都为叶节点，再决定是否合并为一个叶节点，O(nlgn)
105. Construct Binary Tree from Preorder and Inorder Traversal由preorder第一个元素为root， idx = inorder.index(root), 将inorder 分为左右两部分
106. Construct Binary Tree from Inorder and Postorder Traversal同上\

5. Solved by Merge Sort Approach

315. Count of Smaller Numbers After Self

This question can be solved through constructing a binary search, when visiting each node reversely. We add a count of left subtree size in the tree node. When inserting element backward, the number of smaller number after itself = size of left size subtree + size of root(1 if element is not duplicate) + count value of recursively visit the right sub tree. It can also be solved through merge-sort style divide and conquer. The reason starting reversely is that, if constructing tree from left to right, then each time there is small element comes in, the worst case is to update all the previous nodes, O(n^2).

This is solved elegantly by Divide-Conquer, which can also be solved through BST. In DC approach, we take a similar merge sort style algo, sort both the left and right part in increasing order, and merge the two. During the merge, if all elements in left is smaller than right, than means no smaller number after itself. However, when we add an element x in left, some elements in right part has already been added, then means all these added elements are bigger than x, and we increase the count of the x by the number of elements in the right part that already been added.

327. Count of Range Sum

get presum, divide into two half, for each presum on the left, find the starting(>=lower) i and ending(>upper) j point of presum on the right, cnt += j - i, sort the presum.

493. Reverse Pairs同样方法，对于左边每个数，找到右边第一个符合条件的数，逆序排列