Understanding Divide and Conquer

Core Concept

The divide and conquer strategy involves three key steps:

Decompose a large problem into two or more smaller subproblems Recursviely solve each subproblem until it becomes trivial to handle Combine the individual solutions to form the final answer

This approach has been foundational in solving numerous classic algorithmic challenges.

Common Applications

Several well-known algorithms leverage this paradigm:

Binary Search QuickSort MergeSort Merging K Sorted Lists - LeetCode 23

Binary Search Implementation

public static int binarySearch(int[] arr, int target) {
    return search(arr, target, 0, arr.length - 1);
}

private static int search(int[] arr, int target, int low, int high) {
    if (low > high) {
        return -1;
    }
    int mid = (low + high) >>> 1;
    if (target < arr[mid]) {
        return search(arr, target, low, mid - 1);
    } else if (arr[mid] < target) {
        return search(arr, target, mid + 1, high);
    } else {
        return mid;
    }
}

This technique reduces the search space by half with each iteration.

QuickSort Implementation

public static void sort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

The algorithm partitions the array around a pivot element, then reucrsively processes both resulting subarrays.

MergeSort Implementation

public static void sort(int[] source) {
    int[] buffer = new int[source.length];
    divide(source, 0, source.length - 1, buffer);
}

private static void divide(int[] source, int left, int right, int[] buffer) {
    if (left == right) {
        return;
    }
    int mid = (left + right) >>> 1;
    divide(source, left, mid, buffer);
    divide(source, mid + 1, right, buffer);
    merge(source, left, mid, mid + 1, right, buffer);
    System.arraycopy(buffer, left, source, left, right - left + 1);
}

The array is recursively split until single elements remain, then merged back in sorted order.

Merging K Sorted Lists - LeetCode 23

public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) {
        return null;
    }
    return divideAndMerge(lists, 0, lists.length - 1);
}

private ListNode divideAndMerge(ListNode[] lists, int start, int end) {
    if (end == start) {
        return lists[start];
    }
    int mid = (start + end) >>> 1;
    return mergeTwoLists(
        divideAndMerge(lists, start, mid),
        divideAndMerge(lists, mid + 1, end)
    );
}

Lists are paired and merged recursively until a single sorted list remains.

Comparison with Dynamic Programming

Both approaches break problems into subproblems, but differ significantly:

Dynamic programming handles overlapping subproblems and caches results to avoid redundant calculations Divide and conquer typically deals with independent subproblems without overlap

Quick Select Algorithm

public class SelectionUtil {
    static int select(int[] data, int left, int right, int targetIndex) {
        int pos = partition(data, left, right);
        if (pos == targetIndex) {
            return data[pos];
        }
        if (pos < targetIndex) {
            return select(data, pos + 1, right, targetIndex);
        } else {
            return select(data, left, pos - 1, targetIndex);
        }
    }

    static int partition(int[] data, int left, int right) {
        int randomIdx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(data, left, randomIdx);
        int pivot = data[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && data[i] < pivot) {
                i++;
            }
            while (i <= j && data[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(data, i, j);
                i++;
                j--;
            }
        }
        swap(data, j, left);
        return j;
    }

    static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

Kth Largest Element - LeetCode 215

public class KthLargestElement {
    /*
        Target index = 4
            3   2   1   5   6   4
        =>  3   2   1   4   5   6   (pivot at index 3)
        =>  3   2   1   4   5   6   (pivot at index 5)
        =>  3   2   1   4   5   6   (pivot at index 4)
     */

    public int findKthLargest(int[] nums, int k) {
        return SelectionUtil.select(nums, 0, nums.length - 1, nums.length - k);
    }

    public static void main(String[] args) {
        KthLargestElement solver = new KthLargestElement();
        System.out.println(solver.findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2)); // Expected: 5
        System.out.println(solver.findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4)); // Expected: 4
    }
}

Finding Median of Array

public class MedianFinder {
    /*
        Even length:  3   1   5   4
        Odd length:   4   5   1
        Odd length:   4   5   1   6   3
     */
    
    public static double findMedian(int[] nums) {
        if (nums.length % 2 != 0) {
            return SelectionUtil.select(nums, 0, nums.length - 1, nums.length / 2);
        } else {
            int a = SelectionUtil.select(nums, 0, nums.length - 1, nums.length / 2);
            int b = SelectionUtil.select(nums, 0, nums.length - 1, nums.length / 2 - 1);
            return (a + b) / 2.0;
        }
    }

    public static void main(String[] args) {
        System.out.println(findMedian(new int[]{3, 1, 5, 4}));
        System.out.println(findMedian(new int[]{3, 1, 5, 4, 7, 8}));
        System.out.println(findMedian(new int[]{4, 5, 1}));
        System.out.println(findMedian(new int[]{4, 5, 1, 6, 3}));
    }
}

Exponentiation by Squaring - LeetCode 50

public class PowerCalculator {

    /*
                  2^10
              /         \
            2^5         2^5
           /  \        /  \
        2 2^2 2^2    2 2^2 2^2
         / \  / \     / \  / \
        2  2  2  2   2  2  2  2

                  256          n=1 base=65536 result=1024
              /         \
            16          16          n=2 base=256 result=4
           /  \        /  \
        2 4    4    2  4    4       n=5  base=16 result=4
         / \  / \     / \  / \
        2  2  2  2   2  2  2  2     n=10  base=4  result=1
     */

    static double power(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        double result = 1;
        long exp = exponent;
        if (exponent < 0) {
            exp = -exp;
        }
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base = base * base;
            exp = exp >> 1;
        }
        return exponent > 0 ? result : 1 / result;
    }
    
    static double powerRecursive(double base, int exponent) {
        long exp = exponent;
        if (exp < 0) {
            return 1.0 / recursivePower(base, -exp);
        }
        return recursivePower(base, exp);
    }

    static double recursivePower(double base, long exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp == 1) {
            return base;
        }
        double half = recursivePower(base, exp / 2);
        if ((exp & 1) == 1) {
            return base * half * half;
        }
        return half * half;
    }

    public static void main(String[] args) {
        System.out.println(power(2, 10));  // 1024.0
        System.out.println(power(2.1, 3)); // 9.261
        System.out.println(power(2, -2));  // 0.25
        System.out.println(power(2, 0));   // 1.0
        System.out.println(power(2, -2147483648)); // 1.0
    }
}

Integer Square Root - LeetCode 69

public class IntegerSqrt {
    static int sqrt(int num) {
        int low = 1, high = num;
        int answer = 0;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (num / mid >= mid) {
                answer = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(sqrt(1));
        System.out.println(sqrt(2));
        System.out.println(sqrt(4));
        System.out.println(sqrt(8));
        System.out.println(sqrt(9));
    }
}

Key observations:

The condition while(low <= high) ensures all potential candidates are examined The answer variable stores the largest value where m² ≤ x Division is used instead of multiplication to prevent integer overflow with large numbers

Longest Substring with At Least K Repeating Characters - LeetCode 395

public class LongestRepeatingSubstring {

    static int longestSubstring(String str, int k) {
        if (str.length() < k) {
            return 0;
        }
        int[] frequency = new int[26];
        char[] chars = str.toCharArray();
        for (char c : chars) {
            frequency[c - 'a']++;
        }
        System.out.println(Arrays.toString(frequency));
        for (int i = 0; i < chars.length; i++) {
            char current = chars[i];
            int count = frequency[current - 'a'];
            if (count > 0 && count < k) {
                int j = i + 1;
                while (j < str.length() && frequency[chars[j] - 'a'] < k) {
                    j++;
                }
                System.out.println(str.substring(0, i) + "\t" + str.substring(j));
                return Integer.max(
                    longestSubstring(str.substring(0, i), k),
                    longestSubstring(str.substring(j), k)
                );
            }
        }
        return str.length();
    }

    public static void main(String[] args) {
        System.out.println(longestSubstring("aaaccbbb", 3)); // 5
        System.out.println(longestSubstring("dddxaabaaabaacciiiiefbff", 3));
    }
}

The algorithm works by:

Counting character frequencies across the entire string Identifying positions where characters appear fewer than k times Splitting the string at these positions and recursively processing segments Returning the maximum valid substring length found