Solve Any Divide & Conquer Problem With This Trick

And ace your next exam or interview

Photo by Anthony Intraversato on Unsplash

The Divide and Conquer software design paradigm is notorious for its strong problem solving abilities. By carefully breaking down problems into manageable subproblems, algorithms can efficiently and predictably find solutions.

However, designing a Divide and Conquer algorithm on the spot is nothing short of difficult. In my personal experience, I’ve been asked to accomplish this task on university exams as well as software engineering interviews. From my successes and failures comes one critical observation — almost every time, the answer is a slight variation of Binary Search or Merge Sort.

Now, For Some Review

Binary Search

Given a sorted array A and a target value t, locate the middle element, m. If m equals t, return the index of m. If m is greater than t, recurse on A’s right half subarray. Otherwise, recurse on A’s left half subarray.

The recurrence relation is expressed as T(n) = T(n/2) + O(1), allowing for a time complexity of O(log(n)).

This is significantly faster than searching an array with brute force (O(n)).

Merge Sort

Given an array A, split A in half into two subarrays, ALeft and ARight. Then recurse over these subarrays. Now, since we can assume they are sorted, iteratively merge ALeft and ARight into a single array, AFinal, by determining which subarray contains the next smallest element. In the end, return AFinal.

The recurrence relation is expressed as T(n) = 2T(n/2) + O(n), allowing for a time complexity of O(nlog(n)).

This is significantly faster than sorting an array with brute force (O(n²)).

Photo by Edu Grande on Unsplash

Determine Your Base Algorithm

First, decide which algorithm will lay most of the groundwork for your solution.

Generally, your solution will reduce a term n in the brute force time complexity to log(n). So, think about the problem’s naive solution. In other words, how can the problem be solved with brute force, and what is that algorithm’s time complexity? If the naive solution runs in O(n) time, choose Binary Search, and if O(n²), go with Merge Sort.

Using this trick, all that’s left is to alter these algorithms to fit your problem’s needs.

Augmenting Binary Search

1. If the array to be searched is of infinite length, start by finding a finite value larger than the target. Start i at 1, then advance to 2, 4, 8, 16, etc until Array[i] > target. This process requires O(log(n)) since indexes grow exponentially. Finally, perform Binary Search on Array[0..i].
2. Ensure that the target value exists in the recursed subarray. This is inherently true when an array is sorted to be strictly ascending or descending. More complex cases do appear, like when adjacent values in an unsorted array differ by at most 1. As long as the target value is between the array’s first and last elements, recursing on the left ensures that the target exists in the range [start, middle) because the subarray must contain every discrete element between the bounds. The same is true when recursing on the right.
3. Ensure that the target value or condition is consistent with the array’s order property. For instance, finding the index, i, of an element, e, whose value satisfies e = 10 * i is only possible when ordered elements are each separated by at least 10.

Augmenting Merge Sort

1. Observe from which subarray merged elements come from. One classic example of this is seen when determining the number of inversions in an array. If the next element to be merged exists in the left subarray, then an inversion pair is found (intended order is inverted). Handle this by incrementing an eventually-returned counter variable.
2. Observe when the subarray containing the next merged element switches (i.e. left-to-right or right-to-left). Like before, this also exposes the lack or order in the original array. Tracking this behavior can be a useful tool when solving your problem.

Final Thoughts

Divide and Conquer Algorithms have been perfected over the decades — If you’re tasked with building one from scratch, modeling your solution on a classic like Binary Search of Merge Sort is sure to put you on the right track.

Thanks for the read, and good luck dividing and conquering!