What Is Divide and Conquer?

The name says it all—this approach splits a large problem into smaller subproblems, solves each subproblem independently, and then merges those solutions to produce the final answer.

When to Apply Divide and Conquer

This technique works well when a problem can be clearly divided into identical subproblems of reduced scale, and those subproblems are straightforward to solve.

Problem-Solving Process

Divide and conquer follows a consistent pattern:

1. Base case identification: Solve the smallest subproblems directly without further decomposition.
2. Problem decomposition: Split the main problem into smaller subproblems—typically by halving—and recursively solve each part.
3. Solution merging: Combine the solutions from subproblems to construct the answer for the original problem.

Comparing Divide and Conquer to Dynamic Programming

Both methods decompose problems into smaller subproblems, but they differ fundamentally:

Example: Finding the Majority Element

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume the array is non-empty and always contains a majority element.

Example:
Input: nums = [3,2,3]
Output: 3

Analysis:

1. Finding the majority element in an array of size n directly is difficult, but the task becomes trivial when the array size is 1.
2. Using divide and conquer, split the array of size n into two arrays of size n/2, find the majority element in each half, then merge the results.
3. If both halves have the same majority element, that value is the overall majority. Otherwise, count occurrences of each candidate across the entire range and return whichever appears more frequently.

Implementation:

class Solution {
    public int majorityElement(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }
    
    private int divide(int[] nums, int start, int end) {
        if (start == end)
            return nums[start];
        
        int mid = (start + end) / 2;
        int left = divide(nums, start, mid);
        int right = divide(nums, mid + 1, end);
        
        if (left == right)
            return left;
        
        return combine(nums, left, right, start, end);
    }
    
    private int combine(int[] nums, int a, int b, int start, int end) {
        int countA = 0, countB = 0;
        for (int i = start; i <= end; i++) {
            if (nums[i] == a) countA++;
            if (nums[i] == b) countB++;
        }
        return countA >= countB ? a : b;
    }
}