Intro to Divide and Conquer Algorithms

Divide and conquer is an excellent technique for optimizing algorithms, whether you are trying to ace technical interviews or write efficient software. It is widely used in many algorithms including Binary Search, Merge Sort and Fast Fourier Transform.

Divide and conquer means that when you are faced with a large problem, you recursively divide it into smaller versions of the same problem. When you break up a problem in this way, the complexity often decreases exponentially, leading to O(n log n) instead of O(n) time complexity.

One simple example of divide and conquer would be finding the one unique value in a group of duplicates. Imagine we have 9 balls. 8 of them have equal weight, and one is slightly heavier.

balls = [1,1,1,2,1,1,1,1,1]

We could find the location of the heavier element by brute force by iterating through the entire array:

for (var i = 0; i < balls.length - 1; i++) {
    if (balls[i + 1] > balls[i]) {
        return i + 1
    } 
} return 0 

Though this would work, in the worst case scenario, the brute force method would take O(n) calculations. We can optimize this problem with divide and conquer.

First, we will divide the list into equal parts. In this case, we will divide the array into 3 arrays with length 3. Though divide and conquer will work for an array of any length.

balls1 = [1,1,1]
balls2 =[2,1,1]
balls3 = [1,1,1]

Now we will compare the divided arrays to find which one is heavier (in pseudo code):

function findHeaviest(arr) {
   var balls1, balls2, balls3 = dividearr(arr)
// breakpoint
    if (arr.length <= 3) {
        for (var i = 0; i < arr.length - 1; i++) {
            if (arr[i + 1] > arr[i]) {
               return arr[i + 1]
            } 
            
        }
    return arr[0] }
    else if (balls1 === balls2) {
       return findHeaviest(balls3) }
    else if (balls1 === balls3) {
       return findHeaviest(balls2) }
    else {
       return findHeaviest(balls1) }
}

1. Divide the array into three equal parts.
2. Check the equality of the arrays to find the heavier one.
3. Recursively call the function on the heavier array until you have an input array with length 3 or less.
4. At the breakpoint, check the equality of the elements in the final array to find the heavy element.
5. You can either return the element itself or refactor the function to return the index of the element in the array.
6. For arrays that don’t have a length multiple of 9, you need to refactor the function a little, but the same methodology applies.

The worst case scenario for the divide and conquer algorithm is 4 calculations for an array of length 9. The brute force algorithm has a worst case of 8 calculations. As the length of the input array increases, the difference between the two methods widens. The brute force version will always require O(N -1) while the divide and conquer will be O(n Log n), where p is the number of subproblems to solve. For example, if the input array is length 18, the divide and conquer algorithm only requires 5 calculations maximum while the brute force requires 17. For an input array with length 162, the divide and conquer requires 9 calculations, while the brute force requires 161.

DIVIDE AND CONQUER 
Length | # of Calculations
9        4
18       5
162      9

BRUTE FORCE 
Length | # of Calculations
9        8
18       17
162      161

As you can see, the number of calculations required in the divide and conquer increases with size much slower than the brute force algorithm.

Challenge: write a version of this divide and conquer algorithm that will work for arrays of any length.

Enjoy!