Divide and conquer is a recursive problem-solving approach in data structure and algorithms that divide the problem into smaller subproblems, recursively solve each subproblem, and combine the solutions to the subproblems to get the solution of the original problem. So, there are three parts of problem-solving using divide and conquer:

**Divide:** We divide the problem into one or more than one smaller sub-problems, where sub-problems are the smaller versions of the same problem for less input size.

**Conquer:** We solve each sub-problem recursively i.e. calling the same function for a smaller input size. Here recursion will automatically do the work for us.

**Combine:** We combine the solutions to subproblems to build the solution to the original problem.

We need to take care of several critical steps during the implementation of the divide and conquer approach:

- There could be several sub-problems to a problem. So we need to choose the correct sub-problems involved in the solution. In most situations, we divide the problems into two equal parts.
- We solve each sub-problems recursively. So we need to carefully decide the input parameters for the recursive call of each sub-problem.
- The correct base case is essential for the correctness of the divide and conquers solution. We need to identify the smallest or trivial version of the sub-problem for which we already know the solution.
- To implement the conquer stage, we need to identify the correct operation to combine the solutions of sub-problems to get the final solution.

Based on comparison with the middle value, we search recursively on either the left or right half until we find the key or reach the base case.

**Base case:** When the left end crosses the right end, the subarray size shrinks to zero, i.e., if (l > r), return -1.

**Divide:** Calculate the middle index i.e., mid = l + (r — l)/2

**Conquer**

- If (X[mid] == key): Return the value mid.
- If (X[mid] > key): Recursively search the key in the left half.
- If (X[mid] < key): Recursively search the key in the right half.

**Combine:** No need for this step. Think!

Input array will look like this after the partition process similar to quicksort: X[ l…pos — 1] < pivot < X[pos + 1…r ]. The pivot element is present at index pos, and pos — l elements are smaller than the pivot. So pivot element is (pos — l + 1)th smallest element in the array.

- If (pos — l + 1 == k): return X[pos].
- If (pos — l + 1 > k): kth smallest is present on the left subarray.
- If (pos — l + 1 < k): kth smallest is present on the right subarray.

We recur for either the left or right side based on comparing k and pivot position. In other words, we solve the problem using only one sub-problem.

- Recursive algorithm of searching an element in a BST
- Recursive solution of calculating power function
- Euclidean algorithm of finding GCD of two numbers
- Median of two sorted arrays of the same size

We divide the input array of size n into two equal sub-array of size n/2, recursively sort both subarrays and merge the sorted halves to sort the complete array.

**Base case:**When l == r during the recursive calls, the sub-array has one element left, which is trivially sorted.**Divide:**Calculating the middle index i.e., mid = l + (r — l)/2**Conquer:**Recursively Sort both the smaller halves.**Combine:**Merge both the sorted halves to sort the whole array.

We divide the input array into two sub-arrays using the partition process and sort each sub-problems recursively to get the final sorted array.

**Base case:**When l ≥ r during the recursive calls, the sub-array would be either empty or have one value left.**Divide**the problem into two smaller sub-problems by partitioning the array X[l…r] into smaller subarrays around the pivot. The partition process returns the pivotIndex i.e. index of the pivot in the sorted array.**Conquer**: Recursively sort both subarrays.**Combine:**This is a trivial case because our whole array will get sorted after sorting both smaller arrays.

**Divide**the array into two equal parts around mid-value.**Conquer:**Recursively find the min and max of both left and right parts.**Combine:**Compare the max and min of both halves to get the max and min of the whole array.**Base case 1:**If subarray size is 1, return the element as both max and min.**Base case 2:**If subarray size is 2, compare both elements and return max and min among them.

We divide the array into two equal subarrays: **X[l … mid]** and **X [mid + 1 … r]**. Then the sub-array **X[i … j]** with maximum sum must lie in one of these places: 1) Entirely in the left sub-array X[l…mid] 2) Entirely in the right sub-array X[mid+1…r] 3) Subarray crossing the mid-point. This includes some rightmost elements of the left subarray and some leftmost elements of the right subarray.

**Divide**: Calculate the middle index i.e., mid = l + (r — l)/2.**Conquer:**Recursively find the max sub-array sum of left and right halves.**Combine:**Calculate the maximum sub-array that crosses the mid-point and takes the maximum of all three possibilities.**Base case:**When l == r, there is only one element in the array, and we can directly return the max subarray sum as X[l] or X[r].

**Divide:**Calculate the middle index i.e., mid = l + (r — l)/2.**Conquer:**Recursively find the majority element of the left and right halves.**Combine:**If the majority elements of the left and right halves are equal, then it must be the overall majority element. Otherwise, one of them must be equal to the overall majority element. To determine this, count the frequency of the leftMajority and rightMajority in the input array and return the value with maximum frequency as the final output.**Base case:**This is the case of a single element array i.e. if (l == r), return X[l] or X[r].

- Divide and conquer solution of finding the max difference
- Finding the closest pair of points
- Building segment tree for range query operations
- Divide and conquer solution of the convex hull
- Divide and conquer solution of merging k sorted list
- Constructing binary tree from preorder and inorder
- Converting a sorted array to a balanced BST
- Divide and conquer solution of fast Fourier transform

There are a few cases where we use more than two subproblems to get the solution to the final problem. We will add detailed insights about this idea later.

We use recurrence relation to define the time complexity of divide and conquer algorithms. If T(n) is the time complexity for input size n, then T(n) = Time complexity of the divide part + Time complexity of the conquer part + Time complexity of the combine part.

- The time complexity of the divide part is O(1) in most of the scenarios because it calculates the middle index. However, there are a few exceptions! For example, the quicksort divide part is a partition process, which requires O(n) operations.
- Suppose we divide the problem into k number of different sub-problems and solve each sub-problem recursively. So time complexity of the conquer part = T(Input size of subproblem 1) + T(Input size of subproblem 2)….+ T(Input size of subproblem k).
- The time complexity of the combine part depends on the cost of extra operations to combine the solution of smaller sub-problems. It can be O(1), O(n), O(n^2), etc., based on the nature of the operation.

The above approach provides a way to define the recurrence relation of the divide and conquer algorithm. Now we solve the recurrence relation and calculate the overall time complexity in terms of Big-O notation.

There are two popular ways to solve such recurrence relations: The **recursion tree method** and the **Master method**. You can explore this blog to understand how to analyze divide and conquer algorithms: Analysis of recursion in programming.

We implement a divide and conquer algorithm using recursion, which uses a call stack. So space complexity depends on the size of the recursion call stack, which is equal to the depth of the recursion tree.

One must ensure that the memory allocated for the recursion stack is sufficient. Otherwise, the execution may fail because of stack overflow. In other words, time-efficient divide and conquer algorithms often have relatively small recursion depth.

Since the sub-problems are independent, they can be computed in parallel. It is a natural parallel algorithmic approach, leading to a large amount of parallelism. Even if we only divide our problem into two sub-problems, each sub-problem will generate two more smaller sub-problems, and so on.

Due to this property, divide-and-conquer algorithms can be used for execution in multi-processor or shared-memory systems. Data communication between processors does not need to be planned in advance because distinct sub-problems can be executed on different processors.

It can also make efficient use of memory caches. The idea is simple: once a sub-problem is small enough, it can be solved within the cache without accessing the main memory.

Sometimes, recursion with small base cases may lead to many recursive calls and huge recursive stacks. This may lead to an increase in time and space complexity. On the other hand, we can choose the base case smartly to terminate the recursion after fewer steps. This can improve efficiency by a significant factor.

For example, a quicksort algorithm could stop when a single input or input is empty. To improve efficiency, we can switch to a simple loop-based insertion sort algorithm once the number of items to be sorted is sufficiently small. The idea is simple: a base case larger than two can reduce many recursive calls and recursion stack size.

The following recursion tree diagram is an example of finding max and min for input size 16 elements. We can observe that the total number of recursive calls will reduce if we terminate at a larger base case.

Sometimes, we can also optimize the divide and conquer solution by reducing the total number of sub-problems count. The idea is simple: it will reduce the count of recursive calls by a significant margin. The best example of this is calculating the power function, Karatsuba algorithm, and Strassen matrix multiplication. We will add more insights in detail related to this idea.

- Divide-and-conquer algorithms can also be implemented by a non-recursive algorithm using an explicit stack data structure. We recommend exploring the stack-based implementation of the merge sort and quicksort.
- The risk of stack overflow can also be reduced by minimizing the parameters and internal variables of the recursive calls to the sub-problems.
- Divide and conquer solve several challenging problems with less time complexity than its brute-force solution. However, to be efficient, one must ensure that the divide and combine steps are efficient.
- There is a difference between the recursive solution of divide and conquer and the dynamic programming problems. Understanding this difference is important for mastering the dynamic programming approach. Note: later, we will write a separate blog to highlight this difference in detail.
- We can solve several coding problems using the divide and conquer idea of binary search and merge sort.

We will keep updating this blog to add more insights. Please share your feedback or insights to improve this further. Enjoy learning, Enjoy algorithms!

Find Majority Element in an Array

You are given an array X[] consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.

Iterative Binary Tree Traversal using Stack: Preorder, Inorder and Postorder

In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.

Hashing and Hash Table in Data Structures and Algorithms

Hashing is a technique to map (key, value) pairs into the hash table using a hash function. It uses an array of size proportional to the number of keys and calculates an array index from the key using a hash function. Explore this blog to learn how hash tables work in programming?

Maximum difference in an array

Given an array A[] of integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. This is an excellent problem to learn problem-solving using divide and conquer, transform and conquer and a single loop.

Why Learn Data Structures and Algorithms?

There can be four reasons to learn data structures and algorithms: 1) An algorithm is a technology in itself! 2) It is at the core of library functions and APIs 3) It is important for cracking the coding interview 4) Algorithms are beautiful! This blog will help you develop a long-term motivation for learning DSA.

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.