Divide and Conquer algorithm

/
fundamentals

This tutorial is a part of the Data Structures and Algorithms class:

A typical problem solved by Divide and Conquer algorithm

  • Divide (1)

    • Divide original problem into 2 (or more) easy to solve subproblems.

  • Conquer (solve (2) + combine (3))

    • Solve easy subproblems then combine subproblem solutions.

divide and conquer

Recursion implementation of sorting an array with Divide and Conquer

lecture-22/sort-array-recursion.js
// Sort array of numbers small -> big

// plug in your logic to these blocks to use divide and conquer
// Time: O(nlogn), Space: O(n)
const mergeSort = (arr) => {
  // exit condition (base case)
  if (arr.length === 1) return arr

  // divide:
  let leftArr = mergeSort(arr.slice(0, arr.length / 2)) // <- bottom up
  let rightArr = mergeSort(arr.slice(arr.length / 2)) // <- bottom up

  // solve: in this case, there's no solve step.
  // because single element array is already a sorted array.

  // combine:
  const mergedArr = combine(leftArr, rightArr) // <- bottom up

  console.log('leftArr:', leftArr)
  console.log('rightArr:', rightArr)
  console.log('mergedArr:', mergedArr)
  console.log('============================')

  return mergedArr
}

// Combine sorted left & right arrays
// Time: O(x + y), Space: O(x + y)
const combine = (leftArr, rightArr) => {
  const mergedArr = []

  // starting indexes
  let leftArrIdx = 0
  let rightArrIdx = 0

  // combine two array in asc order until one is empty
  while (leftArrIdx < leftArr.length && rightArrIdx < rightArr.length) {
    if (leftArr[leftArrIdx] <= rightArr[rightArrIdx]) {
      mergedArr.push(leftArr[leftArrIdx])
      leftArrIdx++
    } else {
      mergedArr.push(rightArr[rightArrIdx])
      rightArrIdx++
    }
  }

  // push all numbers left in leftArr to mergedArr
  while (leftArrIdx < leftArr.length) {
    mergedArr.push(leftArr[leftArrIdx])
    leftArrIdx++   
  }

  // push all numbers left in rightArr to mergedArr
  while (rightArrIdx < rightArr.length) {
    mergedArr.push(rightArr[rightArrIdx])
    rightArrIdx++  
  }

  return mergedArr    
}

const unsortedNumbers = [15, 26, 13, 7, 3, 5, 2, 22]
const sortedNumbersAscOrder = mergeSort(unsortedNumbers)

console.log(`Unsorted array: [${unsortedNumbers}]`)
console.log(`Sorted array: [${sortedNumbersAscOrder}]`)
$ node sort-array-recursion.js
leftArr: [ 15 ]
rightArr: [ 26 ]
mergedArr: [ 15, 26 ]
============================
leftArr: [ 13 ]
rightArr: [ 7 ]
mergedArr: [ 7, 13 ]
============================
leftArr: [ 15, 26 ]
rightArr: [ 7, 13 ]
mergedArr: [ 7, 13, 15, 26 ]
============================
leftArr: [ 3 ]
rightArr: [ 5 ]
mergedArr: [ 3, 5 ]
============================
leftArr: [ 2 ]
rightArr: [ 22 ]
mergedArr: [ 2, 22 ]
============================
leftArr: [ 3, 5 ]
rightArr: [ 2, 22 ]
mergedArr: [ 2, 3, 5, 22 ]
============================
leftArr: [ 7, 13, 15, 26 ]
rightArr: [ 2, 3, 5, 22 ]
mergedArr: [
   2,  3,  5,  7,
  13, 15, 22, 26
]
============================
Unsorted array: [15,26,13,7,3,5,2,22]
Sorted array: [2,3,5,7,13,15,22,26]

FOR Loop (iterative) implementation of sorting an array

sort array for loop

lecture-22/sort-array-for-loop.js
// Sort array of numbers small -> big

const sortArrayForLoop = (arr) => {
  // save final result to sortedArr
  const sortedArr = [arr[0]]

  console.log('sortedArr:', sortedArr)

  // FOR loop to go through all elements
  for(let i = 1; i < arr.length; i++) {
    console.log('arr[i]:', arr[i])
    
    let left = 0
    let right = sortedArr.length - 1
    let idxToInsert = null

    // Binary Search `sortedArr` to find the position to insert
    while(left <= right) {
      let mid = Math.ceil((left + right) / 2)

      console.log('left:', left, ', mid:', mid, ', right:', right)

      // when mid = left and mid = right, our new element position must be
      // either before or after mid. Compare elements to decide the idx #
      if (mid === left && mid === right) {
        if(arr[i] >= sortedArr[mid]) {
          idxToInsert = mid + 1
        } else {
          idxToInsert = mid
        }
        break
      }  else if(sortedArr[mid] < arr[i]) { // continue with data points on the right
        left = mid + 1
      } else if(sortedArr[mid] > arr[i]) { // continue with data points on the left
        right = mid - 1
      } else { // edge cases (1), left = 1, mid = 2, right = 3
        idxToInsert = mid + 1
        break
      }
    }

    // edge cases (2), left = 0, mid = 1, right = 1
    if (idxToInsert === null) {
      idxToInsert = right + 1
    }

    // insert element to sorted array
    sortedArr.splice(idxToInsert, 0, arr[i])

    console.log('idxToInsert:', idxToInsert)
    console.log('sortedArr after insert:', sortedArr)
    console.log('=====================')
  }

  return sortedArr
}
// Time: Binary Search nested in FOR Loop: O(nlogn), Space: O(n)

sortArrayForLoop([15, 26, 13, 7, 3, 5, 2, 22])
// sortArrayForLoop([-7,-5,-1,7,-4,-1,0,0,4,9]) // edge case (1), (2), loop runs forever
// sortArrayForLoop([-4,0,7,4,9,-5,-1,0,-7,-1]) // edge case (2), left, mid, right don't converge when (left = 0, mid = 1, right = 1)
$ node sort-array-for-loop.js
sortedArr: [ 15 ]
arr[i]: 26
left: 0 , mid: 0 , right: 0
idxToInsert: 1
sortedArr after insert: [ 15, 26 ]
=====================
arr[i]: 13
left: 0 , mid: 1 , right: 1
left: 0 , mid: 0 , right: 0
idxToInsert: 0
sortedArr after insert: [ 13, 15, 26 ]
=====================
arr[i]: 7
left: 0 , mid: 1 , right: 2
left: 0 , mid: 0 , right: 0
idxToInsert: 0
sortedArr after insert: [ 7, 13, 15, 26 ]
=====================
arr[i]: 3
left: 0 , mid: 2 , right: 3
left: 0 , mid: 1 , right: 1
left: 0 , mid: 0 , right: 0
idxToInsert: 0
sortedArr after insert: [ 3, 7, 13, 15, 26 ]
=====================
arr[i]: 5
left: 0 , mid: 2 , right: 4
left: 0 , mid: 1 , right: 1
left: 0 , mid: 0 , right: 0
idxToInsert: 1
sortedArr after insert: [ 3, 5, 7, 13, 15, 26 ]
=====================
arr[i]: 2
left: 0 , mid: 3 , right: 5
left: 0 , mid: 1 , right: 2
left: 0 , mid: 0 , right: 0
idxToInsert: 0
sortedArr after insert: [
   2,  3,  5, 7,
  13, 15, 26
]
=====================
arr[i]: 22
left: 0 , mid: 3 , right: 6
left: 4 , mid: 5 , right: 6
left: 6 , mid: 6 , right: 6
idxToInsert: 6
sortedArr after insert: [
   2,  3,  5,  7,
  13, 15, 22, 26
]

Characteristics of problems can be solved by Divide and Conquer

Problem Input characteristics Algorithm Time
Complexity
Can try with any problem type - pass split test: problem characteristics are the same after splitting input into halves
- usually array, string or graph		 Divide and Conquer O(nlogn)

divide and conquer

lecture-22/sort-array-recursion.js
// plug in your logic to these blocks to use divide and conquer
// Time: O(nlogn), Space: O(n)
const mergeSort = (arr) => {
  // exit condition (base case)
  // to control how small you want to divide
  if (arr.length === 1) return arr

  // divide:
  let leftArr = mergeSort(arr.slice(0, arr.length / 2)) // <- bottom up
  let rightArr = mergeSort(arr.slice(arr.length / 2)) // <- bottom up

  // solve: in this case, there's no solve step.
  // because single element array is already a sorted array.

  // combine:
  const mergedArr = combine(leftArr, rightArr) // <- bottom up

  return mergedArr
}

sort array for loop

lecture-22/sort-array-for-loop.js
// Time: O(nlogn)
// Binary Search inside FOR loop, or FOR loop inside Binary Search
const sortArrayForLoop = (arr) => {
  
  // FOR loop O(n)
  for(let i = 1; i < arr.length; i++) {

    // Binary Search O(logn) nested in FOR Loop
    while(left <= right) {
      
    }
  }
}

Summary

Prob. class P. sub-class Input characteristics Algorithm Time
Complexity
(almost) ANY problem class array, matrix, ... Brute Force O(n) & up
Can try with any problem type - pass split test
- array, string or graph, ...
- divide, solve, combine gives a possible solution		 Divide and Conquer O(nlogn)
1. Maximization
2. Minimization		 array, string or graph, ... Greedy choice,
no guarantee for most optimal solution		 varies
3. Find all options array, matrix, ... Brute Force O(n) & up
4. Find most optimal solution
5. Find a truth search for a number - sorted array
or balanced BST		 Binary Search O(logn)

Note: we're assuming array.splice is an efficient (O(1)), low level built function in both recursion and iterative implementation of Divide and Conquer algorithm above.

Real life interview questions

All problems below can be solved without the Divide and Conquer algorithm. You can solve them by logical thinking and are not forced to use Divide and Conquer. However, thinking about a Divide and Conquer approach (if possible) is encouraged afterward.

  1. How does Divide and Conquer solve problems?
  2. What kind of problems can typically be solved by Divide and Conquer?
  3. Draw the callstack and recursion tree of the sorting array problem and explain why the console logs out like below. Explain what it means by saying even with recursion, we're just looking at one data point at a time.
$ node sort-array-recursion.js
leftArr: [ 15 ]
rightArr: [ 26 ]
mergedArr: [ 15, 26 ]
============================
leftArr: [ 13 ]
rightArr: [ 7 ]
mergedArr: [ 7, 13 ]
============================
leftArr: [ 15, 26 ]
rightArr: [ 7, 13 ]
mergedArr: [ 7, 13, 15, 26 ]
  1. Not looking at the given code, sort the same array from big -> small from scratch by yourself with both Recursion and FOR Loop. You should be able to quickly explain how the algorithm works and implement it within 15 mins.
  2. (Easy) Leetcode #169: Majority Element
  3. (Easy) Leetcode #191: Number of 1 Bits
  4. (Easy) Leetcode #190: Reverse Bits
  5. (Medium) Leetcode #912: Sort an Array
  6. (Medium) Leetcode #53: Maximum Subarray
  7. (Medium) Leetcode #654: Maximum Binary Tree
  8. (Medium) Leetcode #148: Sort List
  9. (Medium) Leetcode #775: Global and Local Inversions
  10. More on Leetcode #divide-and-conquer.