Divide and Conquer

Divide and Conquer is a problem-solving strategy that involves breaking down a complex problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. It is a widely used algorithmic technique in computer science and mathematics.

Example: In the Merge Sort algorithm, the “Divide and Conquer” strategy is used to sort a list of elements. Below image illustrate the dividing and merging states to sort the array using Merge Sort.

What is Divide and Conquer?

Divide and Conquer is a problem-solving technique that involves breaking a larger problem into subproblems, solving the subproblems independently and combining the solutions of those subproblems to get the solution of the larger problem.

Stages of Divide and Conquer:

Divide and Conquer Algorithm can be divided into three stages: Divide, Conquer and Merge.

1. Divide:

• Break down the original problem into smaller subproblems.
• Each subproblem should represent a part of the overall problem.
• The goal is to divide the problem until no further division is possible.

2. Conquer:

• Solve each of the smaller subproblems individually.
• If a subproblem is small enough (often referred to as the “base case”), we solve it directly without further recursion.
• The goal is to find solutions for these subproblems independently.

3. Merge:

• Combine the sub-problems to get the final solution of the whole problem.
• Once the smaller subproblems are solved, we recursively combine their solutions to get the solution of larger problem.
• The goal is to formulate a solution for the original problem by merging the results from the subproblems.

Applications of Divide and Conquer:

• Merge Sort: Merge sort is a classic example of a divide and conquer sorting algorithm. It breaks down the array into smaller subarrays, sorts them individually, and then merges them to obtain the sorted array.
• Median Finding: The median of a set of numbers can be found using a divide and conquer approach. By recursively dividing the set into smaller subsets, the median can be determined efficiently.
• Min and Max finding: Divide and Conquer algorithm can be used to find both the minimum and maximum elements in an array simultaneously. By splitting the array into halves and comparing the min-max pairs from each half, the overall min and max can be identified in logarithmic time complexity.
• Matrix Multiplication: Strassen’s algorithm for matrix multiplication is a divide and conquer technique that reduces the number of multiplications required for large matrices by breaking down the matrices into smaller submatrices and combining their products.
• Closest Pair problem: The closest pair problem involves finding the two closest points in a set of points in a multidimensional space. A divide and conquer algorithm, such as the “divide and conquer closest pair” algorithm, can efficiently solve this problem by recursively dividing the points and merging the solutions from the subproblems.

Basics of Divide and Conquer:

• Introduction to Divide and Conquer
• Dynamic Programming vs Divide-and-Conquer
• Decrease and Conquer
• Advanced master theorem for divide and conquer recurrences

Standard Algorithms on Divide and Conquer:

• Binary Search
• Merge Sort
• Quick Sort
• Calculate pow(x, n)
• Karatsuba algorithm for fast multiplication
• Strassen’s Matrix Multiplication
• Convex Hull (Simple Divide and Conquer Algorithm)
• Quickhull Algorithm for Convex Hull

Binary Search based problems:

• Find a peak element in a given array
• Check for Majority Element in a sorted array
• K-th Element of Two Sorted Arrays
• Find the number of zeroes
• Find the Rotation Count in Rotated Sorted array
• Find the point where a monotonically increasing function becomes positive first time
• Median of two sorted arrays
• Median of two sorted arrays of different sizes
• The painter’s partition problem using Binary Search

Practice problems on Divide and Conquer:

• Square root of an integer
• Maximum and minimum of an array using minimum number of comparisons
• Find frequency of each element in a limited range array in less than O(n) time
• Tiling Problem
• Count Inversions
• The Skyline Problem
• Search in a Row-wise and Column-wise Sorted 2D Array
• Allocate minimum number of pages
• Modular Exponentiation (Power in Modular Arithmetic)

Quick Links :

• Learn Data Structure and Algorithms | DSA Tutorial
• ‘Practice Problems’ on Divide and Conquer
• ‘Quizzes’ on Divide and Conquer