Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Divide & Conquer
DSA

Divide & Conquer

Understand how problems can be divided into smaller subproblems, solved recursively, and combined.

Recognition Cheat Sheet

If you see…Think…
Split array into halvesDivide & Conquer
Sort by splittingMerge Sort / Quick Sort
Count inversionsMerge Sort
Partition around a pivotQuick Sort / Quickselect
Solve left + right and combineDivide & Conquer
Range-based problemSplit range + combine

Main Trigger

Split → Solve smaller problems → Combine

The Basic Idea

Divide & Conquer breaks one big problem into smaller independent problems.

Merge sort is the canonical example — split down to singletons, merge back up sorted:

Merge Sort (Recursion Tree)

Watch merge sort split an array to singletons, then merge back sorted.

The recursion tree splits top-down until each subarray is length 1 (base case), then merges bottom-up. Merging two sorted halves is O(n), and there are log n levels, giving O(n log n) total. The animation lights the tree downward (split) then upward (merge).

TREE VISUALIZER
Steps –
[4,2,3,1][4,2][3,1][4][2][3][1]
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        sort(a):
                      
                        2
                          if len(a) <= 1: return a
                      
                        3
                          mid = len(a) / 2
                      
                        4
                          left = sort(first half)
                      
                        5
                          right = sort(second half)
                      
                        6
                          return merge(left, right)   // both sorted!
                      
          Problem
          /     \
      Left       Right
       ↓           ↓
    Solve        Solve
       \           /
        \         /
         Combine

The three steps are:

1. Divide
2. Solve recursively
3. Combine

1. Generic Divide & Conquer

Java Template

public int solve(int[] nums, int left, int right) {

    // Base case
    if (left >= right)
        return 0;

    int mid = left + (right - left) / 2;

    // Solve left half
    int leftResult =
        solve(nums, left, mid);

    // Solve right half
    int rightResult =
        solve(nums, mid + 1, right);

    // Combine
    return combine(leftResult, rightResult);
}
def solve(nums, left, right):

    # Base case
    if left >= right:
        return 0

    mid = left + (right - left) // 2

    # Solve left half
    left_result = solve(nums, left, mid)

    # Solve right half
    right_result = solve(nums, mid + 1, right)

    # Combine
    return combine(left_result, right_result)
int solve(vector<int>& nums, int left, int right) {

    // Base case
    if (left >= right)
        return 0;

    int mid = left + (right - left) / 2;

    // Solve left half
    int leftResult = solve(nums, left, mid);

    // Solve right half
    int rightResult = solve(nums, mid + 1, right);

    // Combine
    return combine(leftResult, rightResult);
}
function solve(nums, left, right) {

  // Base case
  if (left >= right)
    return 0;

  const mid = left + Math.floor((right - left) / 2);

  // Solve left half
  const leftResult = solve(nums, left, mid);

  // Solve right half
  const rightResult = solve(nums, mid + 1, right);

  // Combine
  return combine(leftResult, rightResult);
}

Pattern

Range
 ↓
Split at mid
 ↓
Solve left
 ↓
Solve right
 ↓
Combine

Recognition

Problem can be divided into smaller independent ranges → Divide & Conquer

2. Merge Sort

Merge Sort splits the array into halves, sorts both halves, then merges them.

[5, 2, 8, 1]

      Split
     /     \
 [5,2]    [8,1]
   ↓        ↓
 [2,5]    [1,8]
     \     /
      Merge
        ↓
 [1,2,5,8]

Java

public void mergeSort(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
}

private void mergeSort(
        int[] nums,
        int left,
        int right) {

    if (left >= right)
        return;

    int mid =
        left + (right - left) / 2;

    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    merge(nums, left, mid, right);
}

private void merge(
        int[] nums,
        int left,
        int mid,
        int right) {

    int[] temp =
        new int[right - left + 1];

    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {

        if (nums[i] <= nums[j])
            temp[k++] = nums[i++];
        else
            temp[k++] = nums[j++];
    }

    while (i <= mid)
        temp[k++] = nums[i++];

    while (j <= right)
        temp[k++] = nums[j++];

    System.arraycopy(
        temp,
        0,
        nums,
        left,
        temp.length
    );
}
def merge_sort(nums):
    _merge_sort(nums, 0, len(nums) - 1)

def _merge_sort(nums, left, right):
    if left >= right:
        return

    mid = left + (right - left) // 2

    _merge_sort(nums, left, mid)
    _merge_sort(nums, mid + 1, right)

    _merge(nums, left, mid, right)

def _merge(nums, left, mid, right):
    temp = []

    i, j = left, mid + 1

    while i <= mid and j <= right:

        if nums[i] <= nums[j]:
            temp.append(nums[i])
            i += 1
        else:
            temp.append(nums[j])
            j += 1

    while i <= mid:
        temp.append(nums[i])
        i += 1

    while j <= right:
        temp.append(nums[j])
        j += 1

    nums[left:left + len(temp)] = temp
void mergeSort(vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;

    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    merge(nums, left, mid, right);
}

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp;
    temp.reserve(right - left + 1);

    int i = left;
    int j = mid + 1;

    while (i <= mid && j <= right) {

        if (nums[i] <= nums[j])
            temp.push_back(nums[i++]);
        else
            temp.push_back(nums[j++]);
    }

    while (i <= mid)
        temp.push_back(nums[i++]);

    while (j <= right)
        temp.push_back(nums[j++]);

    for (int t = 0; t < (int)temp.size(); t++)
        nums[left + t] = temp[t];
}
function mergeSort(nums) {
  mergeSortRange(nums, 0, nums.length - 1);
}

function mergeSortRange(nums, left, right) {
  if (left >= right)
    return;

  const mid = left + Math.floor((right - left) / 2);

  mergeSortRange(nums, left, mid);
  mergeSortRange(nums, mid + 1, right);

  merge(nums, left, mid, right);
}

function merge(nums, left, mid, right) {
  const temp = [];

  let i = left;
  let j = mid + 1;

  while (i <= mid && j <= right) {

    if (nums[i] <= nums[j])
      temp.push(nums[i++]);
    else
      temp.push(nums[j++]);
  }

  while (i <= mid)
    temp.push(nums[i++]);

  while (j <= right)
    temp.push(nums[j++]);

  for (let t = 0; t < temp.length; t++)
    nums[left + t] = temp[t];
}

Recognition

Sort + split into halves + merge → Merge Sort

Complexity

Time:  O(n log n)
Space: O(n)

3. Count Inversions

Merge Sort can also count inversions.

An inversion is:

i < j
nums[i] > nums[j]

Example:

[2, 4, 1, 3]

Inversions:
(2,1)
(4,1)
(4,3)

Answer = 3

During merging, if the right value is smaller:

left[i] > right[j]

then all remaining elements in the left half are also greater.

Java

public long countInversions(int[] nums) {
    return mergeSort(nums, 0, nums.length - 1);
}

private long mergeSort(
        int[] nums,
        int left,
        int right) {

    if (left >= right)
        return 0;

    int mid =
        left + (right - left) / 2;

    long count = 0;

    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);

    count += mergeAndCount(
        nums,
        left,
        mid,
        right
    );

    return count;
}

private long mergeAndCount(
        int[] nums,
        int left,
        int mid,
        int right) {

    int[] temp =
        new int[right - left + 1];

    int i = left;
    int j = mid + 1;
    int k = 0;

    long count = 0;

    while (i <= mid && j <= right) {

        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];

            // All remaining left elements
            // are greater than nums[j].
            count += mid - i + 1;
        }
    }

    while (i <= mid)
        temp[k++] = nums[i++];

    while (j <= right)
        temp[k++] = nums[j++];

    System.arraycopy(
        temp,
        0,
        nums,
        left,
        temp.length
    );

    return count;
}
def count_inversions(nums):
    return _merge_sort(nums, 0, len(nums) - 1)

def _merge_sort(nums, left, right):
    if left >= right:
        return 0

    mid = left + (right - left) // 2

    count = 0

    count += _merge_sort(nums, left, mid)
    count += _merge_sort(nums, mid + 1, right)

    count += _merge_and_count(nums, left, mid, right)

    return count

def _merge_and_count(nums, left, mid, right):
    temp = []

    i, j = left, mid + 1

    count = 0

    while i <= mid and j <= right:

        if nums[i] <= nums[j]:
            temp.append(nums[i])
            i += 1
        else:
            temp.append(nums[j])
            j += 1

            # All remaining left elements
            # are greater than nums[j].
            count += mid - i + 1

    while i <= mid:
        temp.append(nums[i])
        i += 1

    while j <= right:
        temp.append(nums[j])
        j += 1

    nums[left:left + len(temp)] = temp

    return count
long countInversions(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}

long mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right)
        return 0;

    int mid = left + (right - left) / 2;

    long count = 0;

    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);

    count += mergeAndCount(nums, left, mid, right);

    return count;
}

long mergeAndCount(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp;
    temp.reserve(right - left + 1);

    int i = left;
    int j = mid + 1;

    long count = 0;

    while (i <= mid && j <= right) {

        if (nums[i] <= nums[j]) {
            temp.push_back(nums[i++]);
        } else {
            temp.push_back(nums[j++]);

            // All remaining left elements
            // are greater than nums[j].
            count += mid - i + 1;
        }
    }

    while (i <= mid)
        temp.push_back(nums[i++]);

    while (j <= right)
        temp.push_back(nums[j++]);

    for (int t = 0; t < (int)temp.size(); t++)
        nums[left + t] = temp[t];

    return count;
}
function countInversions(nums) {
  return mergeSortCount(nums, 0, nums.length - 1);
}

function mergeSortCount(nums, left, right) {
  if (left >= right)
    return 0;

  const mid = left + Math.floor((right - left) / 2);

  let count = 0;

  count += mergeSortCount(nums, left, mid);
  count += mergeSortCount(nums, mid + 1, right);

  count += mergeAndCount(nums, left, mid, right);

  return count;
}

function mergeAndCount(nums, left, mid, right) {
  const temp = [];

  let i = left;
  let j = mid + 1;

  let count = 0;

  while (i <= mid && j <= right) {

    if (nums[i] <= nums[j]) {
      temp.push(nums[i++]);
    } else {
      temp.push(nums[j++]);

      // All remaining left elements
      // are greater than nums[j].
      count += mid - i + 1;
    }
  }

  while (i <= mid)
    temp.push(nums[i++]);

  while (j <= right)
    temp.push(nums[j++]);

  for (let t = 0; t < temp.length; t++)
    nums[left + t] = temp[t];

  return count;
}

Recognition

Count pairs where left value > right value → Merge Sort + counting during merge

4. Quick Sort

Quick Sort also uses Divide & Conquer, but instead of merging two sorted halves, it partitions around a pivot.

Choose pivot
     ↓
Partition
     ↓
Smaller | Pivot | Larger
     ↓
 Recurse

Java

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

private void quickSort(
        int[] nums,
        int left,
        int right) {

    if (left >= right)
        return;

    int pivotIndex =
        partition(nums, left, right);

    quickSort(nums, left, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, right);
}

private int partition(
        int[] nums,
        int left,
        int right) {

    int pivot = nums[right];

    int i = left;

    for (int j = left; j < right; j++) {

        if (nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
    }

    swap(nums, i, right);

    return i;
}

private void swap(
        int[] nums,
        int i,
        int j) {

    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
def quick_sort(nums):
    _quick_sort(nums, 0, len(nums) - 1)

def _quick_sort(nums, left, right):
    if left >= right:
        return

    pivot_index = partition(nums, left, right)

    _quick_sort(nums, left, pivot_index - 1)
    _quick_sort(nums, pivot_index + 1, right)

def partition(nums, left, right):
    pivot = nums[right]

    i = left

    for j in range(left, right):
        if nums[j] <= pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

    nums[i], nums[right] = nums[right], nums[i]

    return i
void quickSort(vector<int>& nums) {
    quickSort(nums, 0, nums.size() - 1);
}

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right)
        return;

    int pivotIndex = partition(nums, left, right);

    quickSort(nums, left, pivotIndex - 1);
    quickSort(nums, pivotIndex + 1, right);
}

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];

    int i = left;

    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }

    swap(nums[i], nums[right]);

    return i;
}
function quickSort(nums) {
  quickSortRange(nums, 0, nums.length - 1);
}

function quickSortRange(nums, left, right) {
  if (left >= right)
    return;

  const pivotIndex = partition(nums, left, right);

  quickSortRange(nums, left, pivotIndex - 1);
  quickSortRange(nums, pivotIndex + 1, right);
}

function partition(nums, left, right) {
  const pivot = nums[right];

  let i = left;

  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }

  [nums[i], nums[right]] = [nums[right], nums[i]];

  return i;
}

Recognition

Pivot + partition + recursively sort both sides → Quick Sort

Complexity

Average: O(n log n)
Worst:   O(n²)
Space:   O(log n) average recursion

5. Quickselect

Quickselect uses the same partition idea as Quick Sort, but only explores the side containing the Kth element.

Partition
    ↓
Is pivot at K?
  /       \
 Yes       No
 ↓         ↓
Return   Search one side

Java — Kth Largest

public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k;

    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {

        int pivotIndex =
            partition(nums, left, right);

        if (pivotIndex == target)
            return nums[pivotIndex];

        if (pivotIndex < target)
            left = pivotIndex + 1;
        else
            right = pivotIndex - 1;
    }

    return -1;
}
def find_kth_largest(nums, k):
    target = len(nums) - k

    left = 0
    right = len(nums) - 1

    while left <= right:

        pivot_index = partition(nums, left, right)

        if pivot_index == target:
            return nums[pivot_index]

        if pivot_index < target:
            left = pivot_index + 1
        else:
            right = pivot_index - 1

    return -1
int findKthLargest(vector<int>& nums, int k) {
    int target = nums.size() - k;

    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {

        int pivotIndex = partition(nums, left, right);

        if (pivotIndex == target)
            return nums[pivotIndex];

        if (pivotIndex < target)
            left = pivotIndex + 1;
        else
            right = pivotIndex - 1;
    }

    return -1;
}
function findKthLargest(nums, k) {
  const target = nums.length - k;

  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {

    const pivotIndex = partition(nums, left, right);

    if (pivotIndex === target)
      return nums[pivotIndex];

    if (pivotIndex < target)
      left = pivotIndex + 1;
    else
      right = pivotIndex - 1;
  }

  return -1;
}

Recognition

Need Kth element, not the whole sorted array → Quickselect

Average:

O(n)

Divide & Conquer vs Backtracking

They can look similar, but the goal is different.

Divide & Conquer

Split into independent problems
        ↓
Solve both
        ↓
Combine

Example:

Merge Sort

Backtracking

Make a choice
      ↓
Explore
      ↓
Undo
      ↓
Try another choice

Example:

N-Queens / Subsets

Quick Rule

Split the problem → Divide & Conquer

Try different choices → Backtracking

Common Mistakes

1. Wrong base case

For an array range:

if (left >= right)
    return;

This stops when the range contains zero or one element.

2. Wrong midpoint

Prefer:

int mid =
    left + (right - left) / 2;

instead of:

int mid = (left + right) / 2;

The first avoids integer overflow.

3. Forgetting the combine step

For Merge Sort:

Split
 ↓
Sort left
 ↓
Sort right
 ↓
Merge

The merge is what produces the sorted result.

4. Using Quick Sort when you only need K

If the problem asks:

Kth smallest
Kth largest

you usually don’t need to fully sort the array.

Think:

Quickselect / Heap

Pattern Summary

Split + merge
→ Merge Sort

Split + count during merge
→ Count Inversions

Pivot + partition
→ Quick Sort

Kth element + partition
→ Quickselect

Split range + combine results
→ Divide & Conquer

Quick Rule

Split → Solve → Combine = Divide & Conquer

My Private Notes

Notes are auto-saved locally to this device.