Divide and Conquer – What is it and How to use it

What is it

Divide and Conquer is an algorithm design paradigm. It works by breaking the original problem into similar subproblems recursively. The solutions to subproblems are then combined to give the solution to the original problem. (Wikipedia)

Following that intuition, there are three steps in each recursion calls:

1. Divide: Divide the problem into subproblems.
2. Conquer: If the sizes of subproblems are small enough, solve them directly; or, solve them recursively.
3. Combine: Combine solutions from subproblems for the original problem.

How to use it

That’s it! Simple, right? Let’s walk through it in details with an example – Mergesort.

Remember that there are three steps in divide and conquer, what shall we do specifically here? Given the input arr=[5,3,1,9,8,7,6,2]:

1. Divide: Divide the original array into subarrays.
2. Conquer: If there is only one item left, return it directly as it’s already been sorted; else, recursively divide the subarray into sub-subarrays.
3. Combine: Combine two sorted subarrays into a sorted array.

Practices

• 148. Sort List
• 23. Merge k Sorted Lists
• 215. Kth Largest Element in an Array