Divide and Conquer — Concept, Code, and Practice Problems

This blog introduces the reader to the Divide and Conquer strategy and discusses a versatile 3 step method that can be adapted to solve almost all the problems that fall under the category of Divide and Conquer. To explain the concept in detail, the blog will use — Merge Sort — an algorithm that every Computer Science student should understand well. The blog also explains how to code Merge Sort and covers the practical aspect by providing the reader with a well-commented Python code. In the end, it also provides a few practice questions with links to the solutions.

I hope that the blog proves to be helpful.

With no more delay, let us begin!! 😃

Why the name: ‘Divide and Conquer’?

We will try to understand this using a hypothetical example.

Let us assume that we have a deck of cards (52 cards in total), and we want to separate all the Spades from the rest of the deck. We can achieve this in many ways; however, we are super smart 😎 😆, as we all know. We divide the deck into 2 halves, each having 26 cards, and ask two of our good friends for help. We give one half to the first friend and the other half to the second friend and ask them to hand over all the Spades to us. In other words, we ask them to conquer each half by collecting all spades from the halves delegated to them.

To reiterate, we divided the deck into 2 halves and asked the friends to conquer each half for us. Well, as it might already be relevant, this approach is known as the Divide and Conquer approach.

To put it more formally, in the Divide and Conquer approach, we divide the given problem into subproblems and try to solve/conquer the subproblems. Once the subproblems have been conquered, we try to combine the solved subproblems to derive the original problem's solution.

Now, let us take up the example of Merge Sort and see how it works.

Merge Sort — A diagrammatic explanation

Let us assume that we have been given a list— [3,1,4,2] — and we are supposed to sort it in ascending order using a Divide and Conquer Strategy. To do this, we will use Merge Sort. However, for a second, let us assume that there is no such thing as Merge Sort. How will we do this? 🤔

Well, let us use the ‘Card example’ as a reference. When we were given 52 cards and were supposed to segregate all the Spades, what did we do?

• Firstly, we divided the deck into 2 halves.
• Then, we delegated each half to one of our friends.
• Finally, we collected the spades returned by each of the friends.

In the same way, we deal with the list given to us:

• Firstly we divide the list into 2 halves.
• Then, we will delegate each list to one of our friends.
• The friends will return a sorted list, and we will combine the list to form one sorted list.

However, there is something that we might have missed to realize. Our friend is also smart and follows the same divide and conquer strategy as we did. When the friends receive 26 cards, they divide them into 2 halves (each of 13 cards) and call their 2 other friends to find all the spades. This process of dividing into half and delegating the task continues till all the spades have not been found.

In this new scenario where our friend is smart as well, we realize that our duties are the same as our friends — both of us tend to apply a divide and conquer approach on the cards given to us.

Since the tasks/duties are the same, we realize that there is no need for us to call new friends again and again. In other words, I could say that there is no need to define new functions again and again. Instead, we can define a core function that relies on recursion. The core function should:

1. Take the input
2. Divide it into 2 halves — the left and the right half.
3. Recursively call itself twice — once on the left and then on the right half.
4. Appropriately combine both the halves together and return the result.

Till this point, there might be a few things that would be a bit unclear. However, let us go through the Merge Sort example and try to build a better understanding.

To recap, we have a list — [3,1,4,2], and we want to sort it in ascending order using Merge Sort.

Note: Moving on from this point, I might use the term list and array interchangeably. Arrays and Lists are different. However, this casual way of using one for the other does not prevent us from understanding the Divide and Conquer logic.

Let us make a core function and name it: sort (list), or sort(array), or sort(arr)
As relevant, the sort() function takes a list as an argument and then follows a divide and conquer approach.

Given below is a set of images that explain how the MergeSort works.

To begin with, we call the sort function as: sort([3,1,4,2]). The state, at this point, is shown in the figure below:

State 1

Then, the sort([3,1,4,2]) divides the array into 2 halves and recursively calls itself on the left half, i.e. [3,1]. After making the call, it waits for the recursion to get over. The state is shown in the ‘state 2’ figure below:

State 2

Then, the sort([3,1]) divides the array into 2 halves and recursively calls itself on the left half, i.e. [3]. After making the call, it waits for the recursion to get over. The state is shown in the state 3 figure below:

State 3

Now, sort([3]) realizes that it has just 1 element in the input. Since there is just 1 element, it cannot be divided and is therefore returned as it is. In other words, the sort([3]) does not make any recursive calls. Such a corner case is called the ‘Base Case.’ To put it more formally, the Base Case acts as the leaf of the recursion tree.

After the Base Case i.e. sort([3]) completes its execution and returns the value, the paused parent i.e. sort([3,1]) restarts its execution. This has been shown in the State 4 figure below:

State 4

After restarting the execution, the sort([3,1]) makes a recursive call to the right half, i.e., sort([1]). This is shown in the State 5 figure below:

State 5

Since sort([1]) is a Base Case, it returns the value as it is. This value is returned to the variable called right_sorted. This is shown in the State 6 figure below:

State 6

Once sort([3,1]) receives the value in right_sorted, it is pretty much done with all its recursive calls. Currently, the left_sorted stores the left half in the sorted order, and the right_sorted stores the right half in the sorted order. Now, we have to take the left and the right sorted halves and combine/merge them into one sorted array.

Merging 2 arrays or lists into 1 is a famous problem, and I expect the reader to be aware of the technique.

Now, the sort([3,1]) calls the Merge function to merge the left_sorted and the right_sorted lists/arrays into one. Once the merge is completed, the combined list is returned to the outer sort call, i.e., sort([3,1,4,2]).
sort([3,1,4,2]) receives the value in its left_sorted variable and restarts its execution. This is shown in the State 7 figure below:

State 7

After restarting the execution, the sort([3,1,4,2]) makes a recursive call to the right half i.e. sort([4,2]). This is shown in the State 8 figure below:

State 8

Now, the same steps — division, recursive calls, base cases, merges, etc. — that took place with sort([3,1]) will take place with sort([4,2]). In the end, the left_sorted and the right_sorted variables of the sort([3,1,4,2]) will be merged to produce the final result, i.e. [1,2,3,4]. This has been shown in the Final State figure below:

Final State

As we can see that once the final state is reached, we get the array in the sorted form.

Having understood this example, we can take a step towards the 3-step method. What are these 3 steps?

3 step method

After carefully analyzing the working of Merge sort, we observe that while dealing with Divide and Conquer, we need to think and implement the following 3 things:

1. Handling the base case.
2. Making Recursive calls to both the halves.
3. Combining the results obtained from the recursive calls.

If we try to use 3 step method for the Merge sort, we should think in the following way:

1. What is the base case?
   When the length of the list/array is 1, we hit the base case.
2. How to make recursive calls?
   Divide array/list into 2 and call sort() function on both. Store the output in the left_sorted and right_sorted variables.
3. How to combine results?
   Make a Merge function that helps us merge 2 sorted lists/arrays into 1 sorted list/array.

Once we have figured this out, we can design our core function — called sort(list). The sort function will implement the 3 steps in the same sequence as mentioned above, and the entire logic of Divide and Conquer will successfully work.

The figure below illustrates how the 3 step method helps us code the Merge Sort algorithm:

Drawing parallelism between Merge Sort’s diagrammatic representation and the code

Now, since we are familiar with how the core function, i.e., sort(), will be designed, let us jump to the coding section.

Merge Sort Code in Python

This is the link to the LeetCode question. DO TRY before you read the solution.

Sort an Array - LeetCode

LeetCode provides some initial code that looks like this:

We will follow our 3 step approach and start by coding the core function, called sort. The figure below shows the code for the sort function:

Once the core function has been formed, we just need to code the merge function. The code to the merge function looks like this:

Once the merge function has been coded, we just need to call the sort function from the function provided by LeetCode, i.e., the sortArray function. It would look like this:

Following is the GitHub link for the code:

shantanutrip/Blog_Codes

Complexity Analysis — Type 1

To analyze the complexity, let us look at the self.sort() function above. If we consider that:

• Time taken by self.sort(list) function to sort a list of length ‘n’ is T(n),
• Then the time taken by self.sort(left_half) will be T(n/2)
• And the time taken by self.sort(right_half) will also be T(n/2).

Further, we know that:

• self.merge() function has an overall time complexity of O(n)

Using this information, we can derive an equation for the time taken by self.sort(list). To have a better understanding, let us look at the figure below:

If we apply the master-method to the final equation that we achieved in the figure above, we will find out that the time complexity is O(n log n).

Complexity Analysis — Type 2

There is yet another way of analyzing the complexity. However, this needs more visualization as opposed to Type 1. In this method,

1. We imagine how the recursive tree looks like.
2. Then, at each level of the recursive tree, we add all the work done by the Combine/Merge calls.
3. Then we add the work done at each level of the recursive tree.

For a better understanding, have a look at the figure given below:

As we can see that at each level, the total amount of work adds up to N. So, the total work is:

What is the value of h??

If we observe the recursion tree shown above, we see that at each level, we divide the input by 2 until we reach the leaf node, where the input becomes 1. In other words, when we reach the leaf node, we would have already divided N by 2 for ‘h’ number of times and would have hence reduced the input size to 1.

To put it mathematically,

Thus, the overall time complexity for Merge Sort is:

Practice Problems:

I would like to thank my friend Deepankar for helping me in selecting the practice problems.

Though I have just taken Merge Sort to explain the concept, I hope that the readers will now be able to use the 3 step method to solve any problem that is given to them. For better practice, I am providing a few LeetCode links to the questions that can be solved using Divide and Conquer. There might be other approaches to solve the questions; however, I suggest that the reader should stick to Divide and Conquer to build a firm understanding of the topic.

I have also provided the code for the problems. The code comments should help one understand how to implement and code the divide and conquer for various questions.

Link to questions:

Maximum Subarray - LeetCode

Merge k Sorted Lists - LeetCode

Maximum subarray code:

shantanutrip/Blog_Codes

The Maximum Subarray mentioned above is O(n log n).

Do you want to solve Maximum Subarray in O(n) using Divide and Conquer? Refer to the following link:

Maximum Sum SubArray using Divide and Conquer | Set 2 - GeeksforGeeks

Merge K sorted lists code:

shantanutrip/Blog_Codes

Conclusion

In this blog, we discussed the topic of Divide and Conquer and also learned the versatile 3 step method to approach the questions that lie in the domain of this topic. To understand the concepts in a better way, we went through the Merge Sort algorithm in detail and explored the entire recursive tree. We also developed a practical understanding by learning how to code the Merge Sort algorithm. We went a step further and understood the process of analyzing the complexity of solutions that use the Divide and Conquer strategy. Finally, to help the readers enhance their implementation skills, we provided 2 LeetCode questions and links to their solutions.

I hope that the readers find the blog helpful. Thanks for your time. 😃

References:

1. LeetCode — Questions
2. Geeks for geeks — Enhanced Solutions