Search⌘ K
Home
Courses
Data Science Interview Handbook

Divide and Conquer

Explore the divide and conquer technique to break complex problems into smaller subproblems, solve them recursively, and combine results. Understand applications such as binary search and merge sort, and learn how to optimize solutions for efficiency using this approach.

We'll cover the following...

In divide and conquer, we divide the original problem into subproblems that have similar objectives as the original problem. We solve these subproblems recursively and combine the solution to solve the original problem. We can think of three parts for solving of the problem using divide and conquer.

  • Divide: Divide the problem into smaller problems that have the same objective as the original problem.
  • Conquer: Solve the small subproblems recursively. If they are small enough and cannot be broken further, solve them as base cases.
  • Combine : Combine the solutions of the subproblems to get the solution of the original problem.

    • Let’s consider a simple example of summing numbers. We have been given 8 numbers:

    5      8      7      9      1    ...