Facebook Pixel

You are on level: Student

0%
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section

Divide and Conquer

Divide and conquer solves one large problem by repeatedly breaking it into smaller subproblems of the same type, solving those subproblems, then combining their answers.

A common template is: split, solve recursively, then merge.

Merge sort is a classic example. Suppose the input is [7, 2, 5, 1]. We split it into [7, 2] and [5, 1], then split again until each piece has one element. A single element is already sorted, so recursion can stop there. We then merge sorted pieces back together: [7] with [2] becomes [2, 7], [5] with [1] becomes [1, 5], and finally [2, 7] with [1, 5] becomes [1, 2, 5, 7].

The important idea is that each recursive call works on a smaller version of the same task, and the merge step converts two solved halves into the full answer.

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro