Skip to content
Coding Patterns - Guide to 30 Core Algorithm Patterns
Divide and Conquer: Complete Guide with Examples
Divide and Conquer: Practice Problems with Solutions

Divide and Conquer: Practice Problems with Solutions

Welcome to the practice problems for divide and conquer. If you need a refresher on the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

  1. Merge Two Sorted Lists isolates the combine step. Until the merge makes sense, the rest of the pattern will not.
  2. Sort an Array puts the full merge sort together: split, recurse, merge. This is the template problem for the pattern.
  3. Longest Substring with At Least K Repeating Characters splits by a condition instead of an index. Same skeleton, different divide step.
  4. Kth Largest Element in an Array shows the pruning variant. Quickselect follows only one branch, which is how the cost drops to linear.
  5. Merge K Sorted Lists divides by the number of lists instead of their sizes. Pairwise merging is merge sort applied to the top level.
  6. Count of Smaller Numbers After Self modifies the combine step to carry extra state. The merge counts jumps as it goes.
  7. The Skyline Problem has the hardest combine step in the set. It merges two geometric outlines instead of two arrays.
The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Merge Two Sorted Lists

LeetCode 21 | Difficulty: Easy

Brief: Merge two sorted linked lists into one sorted list.

Why this pattern: This is the combine step of merge sort, isolated from everything else. You pick the smaller current head, link it, and merge the rest.

Key Insight: The smaller of the two current heads must be the next element of the result. Once you pick it, the problem shrinks to the same merge with one fewer node, which is exactly what the recursion does.

Visual:

    graph TD
    A["List 1: 1, 2, 4"] --> C["Compare heads: 1 <= 1"]
    B["List 2: 1, 3, 4"] --> C
    C --> D["Take 1 from list 2"]
    D --> E["2 vs 3, take 2"]
    E --> F["Continue until one list empties"]
    F --> G["Merged: 1, 1, 2, 3, 4, 4"]

Code:

var mergeTwoLists = function(list1, list2) {
    if (!list1) return list2; // one side is empty, the other is done
    if (!list2) return list1;

    if (list1.val <= list2.val) {
        // list1's head wins, merge the rest behind it
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};

The base cases handle the moment one list empties, at which point the other list is the answer. The recursive call is the combine step from the merge sort template , applied to one fewer node each time. This problem also appears on the linked list page, where it is framed as pointer manipulation rather than a combine step. Runs in

O(N + M)
time, with
O(N + M)
space for the recursion stack.

Medium Problems

2. Sort an Array

LeetCode 912 | Difficulty: Medium

Brief: Sort an integer array in ascending order.

Why this pattern: This is the merge sort template applied end to end. Split the input in half, sort both halves recursively, then merge the sorted halves.

Key Insight: The merge step is where the sortedness happens. Each level of the recursion hands up two sorted halves, and the merge interleaves them into one sorted array in a single linear pass.

Visual:

    graph TD
    A["5 2 3 1"] --> B["5 2"]
    A --> C["3 1"]
    B --> D["5"]
    B --> E["2"]
    C --> F["3"]
    C --> G["1"]
    D --> H["2 5"]
    E --> H
    F --> I["1 3"]
    G --> I
    H --> J["1 2 3 5"]
    I --> J

Code:

var sortArray = function(nums) {
    const mergeSort = (arr, left, right) => {
        if (left >= right) return; // base case: empty or single element

        const mid = Math.floor((left + right) / 2);
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    };

    const merge = (arr, left, mid, right) => {
        // Snapshot both halves before writing over the range
        const leftArr = arr.slice(left, mid + 1);
        const rightArr = arr.slice(mid + 1, right + 1);

        let i = 0, j = 0, k = left;
        // Interleave the halves by always taking the smaller head
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
            else arr[k++] = rightArr[j++];
        }
        while (i < leftArr.length) arr[k++] = leftArr[i++];
        while (j < rightArr.length) arr[k++] = rightArr[j++];
    };

    mergeSort(nums, 0, nums.length - 1);
    return nums;
};

The only detail worth losing sleep over is the merge loop. Each element moves exactly once per level of the recursion tree, and the tree has log N levels, so the whole sort costs

O(N log N)
time and
O(N)
space for the temporary arrays. The trailing loops are not dead code: after one half is exhausted, the rest of the other half is already in order and gets appended directly.

3. Longest Substring with At Least K Repeating Characters

LeetCode 395 | Difficulty: Medium

Brief: Find the longest substring where every character appears at least k times.

Why this pattern: The divide step is driven by a condition instead of an index. A character that appears fewer than k times can never be inside a valid substring, so it acts as a barrier that splits the string into independent segments.

Key Insight: Any character with a count below k divides the problem. Every valid substring must avoid it, so the answer is the best result across the segments it creates, and each segment is the same problem with less input.

Visual:

    graph TD
    A["ababbc, k=2"] --> B["Counts: a=2, b=3, c=1"]
    B --> C["c is rare, split on it"]
    C --> D["Segment: ababb"]
    C --> E["Segment: empty"]
    D --> F["a=2, b=3, all >= k, length 5"]
    E --> G["rejected"]
    F --> H["Answer: 5"]

Code:

var longestSubstring = function(s, k) {
    if (!s) return 0;

    const counts = {};
    for (const ch of s) counts[ch] = (counts[ch] || 0) + 1;

    for (const ch in counts) {
        if (counts[ch] < k) {
            // A rare character can never appear in a valid substring,
            // so the answer lives entirely inside one of the segments
            // between its occurrences
            let best = 0;
            for (const segment of s.split(ch)) {
                best = Math.max(best, longestSubstring(segment, k));
            }
            return best;
        }
    }

    // Every character appears at least k times, the whole string works
    return s.length;
};

The divide step here is unusual: the split point comes from the data, not from the midpoint. Each recursion level removes at least one distinct character, so the depth is bounded by the alphabet size, and every character is counted at each level. That keeps the total cost at

O(N)
time with
O(N)
space for the recursion stack, since the alphabet is bounded.

4. Kth Largest Element in an Array

LeetCode 215 | Difficulty: Medium

Brief: Return the kth largest element of an unsorted array.

Why this pattern: Quickselect partitions around a pivot and then recurses into only the side that contains the target index. It is quick sort with every branch except one cut away.

Key Insight: The kth largest value sits at index n - k in sorted order. After a partition, the pivot is in its final position, so comparing the pivot index with the target tells you which half to search next.

Visual:

    graph TD
    A["3 2 1 5 6 4, k=2"] --> B["Pivot 4 lands at index 3"]
    B --> C["Target index 4 (6 - 2)"]
    C --> D["Index 3 < 4, search right half"]
    D --> E["Partition 5 6: pivot 6 lands at index 5"]
    E --> F["Index 5 > 4, search left"]
    F --> G["5 sits at index 4, return 5"]

Code:

var findKthLargest = function(nums, k) {
    // The kth largest value lands at index n-k in sorted order
    const target = nums.length - k;
    let low = 0, high = nums.length - 1;

    while (low <= high) {
        const pivotIndex = partition(nums, low, high);
        if (pivotIndex === target) return nums[pivotIndex];
        // Only the half containing the target index is worth searching
        if (pivotIndex < target) low = pivotIndex + 1;
        else high = pivotIndex - 1;
    }
};

function partition(nums, low, high) {
    const pivot = nums[high];
    let i = low;
    for (let j = low; j < high; j++) {
        if (nums[j] < pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }
    [nums[i], nums[high]] = [nums[high], nums[i]];
    return i;
}

The partition is identical to quick sort’s, but the recursion is not: one side is discarded after every partition, so the expected work is N plus N/2 plus N/4 and so on, which sums to

O(N)
average time with
O(1)
extra space in the iterative version. With unlucky pivots it degrades to
O(N^2)
, the same worst case as quick sort. The heap page covers the same problem with a priority queue, which is the alternative interviewers accept.

Hard Problems

5. Merge K Sorted Lists

LeetCode 23 | Difficulty: Hard

Brief: Merge k sorted linked lists into one sorted list.

Why this pattern: Merge pairs of lists, then merge the results, until one list remains. This divides by the number of lists rather than by element count, so the merge depth is log k instead of k.

Key Insight: Merging two lists at a time costs linear work per level, and the pairing halves the list count at every level. The total is the same N log k shape as merge sort, with k playing the role of the array size.

Visual:

    graph TD
    A["L1, L2, L3, L4"] --> B["merge(L1, L2)"]
    A --> C["merge(L3, L4)"]
    B --> D["M12"]
    C --> E["M34"]
    D --> F["merge(M12, M34)"]
    E --> F
    F --> G["Fully sorted"]

Code:

var mergeKLists = function(lists) {
    if (lists.length === 0) return null;

    // Merge neighbors pairwise until one list remains. Each round
    // halves the list count, so the depth is log k.
    while (lists.length > 1) {
        const merged = [];
        for (let i = 0; i < lists.length; i += 2) {
            const a = lists[i];
            const b = i + 1 < lists.length ? lists[i + 1] : null;
            merged.push(mergeTwo(a, b));
        }
        lists = merged;
    }
    return lists[0];
};

function mergeTwo(a, b) {
    const dummy = new ListNode(0);
    let tail = dummy;

    // Link the smaller head, advance only that list
    while (a && b) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a || b; // the leftover list is already sorted
    return dummy.next;
}

The dummy node removes the special case where the merged list starts empty. Pairing neighbors instead of merging every list into one big accumulator keeps the tree balanced, so with N total nodes the cost is

O(N log K)
time and
O(1)
space beyond the output, since nodes are relinked rather than copied. The same problem appears on the heap page , where a priority queue merges all k heads at once.

6. Count of Smaller Numbers After Self

LeetCode 315 | Difficulty: Hard

Brief: For each element, count how many elements to its right are smaller.

Why this pattern: Merge sort’s combine step can carry extra information. When a right-half element is placed before a left-half element during the merge, every remaining left-half element has that right element as a smaller number on its right.

Key Insight: Track the original indices during the merge, not just the values. When a right-half element is placed, it is smaller than every still-unplaced left-half element, so those counts all increase by one.

Visual:

    graph TD
    A["Left: 2 4 | Right: 1 3"] --> B["Pick 1 from right: rightCounter = 1"]
    B --> C["Pick 2 from left: count[2] += 1"]
    C --> D["Pick 3 from right: rightCounter = 2"]
    D --> E["Pick 4 from left: count[4] += 2"]
    E --> F["counts recorded: 1, 2, 0, 0"]

Code:

var countSmaller = function(nums) {
    const counts = new Array(nums.length).fill(0);
    const indices = nums.map((_, i) => i); // original positions to update

    const mergeSort = (left, right) => {
        if (left >= right) return;
        const mid = Math.floor((left + right) / 2);
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    };

    const merge = (left, mid, right) => {
        const leftArr = indices.slice(left, mid + 1);
        const rightArr = indices.slice(mid + 1, right + 1);

        let i = 0, j = 0, k = left;
        let rightCounter = 0; // right-half elements placed so far

        while (i < leftArr.length && j < rightArr.length) {
            if (nums[leftArr[i]] <= nums[rightArr[j]]) {
                // Every placed right element is smaller than this
                // left element, so they all count for it
                counts[leftArr[i]] += rightCounter;
                indices[k++] = leftArr[i++];
            } else {
                rightCounter++;
                indices[k++] = rightArr[j++];
            }
        }
        while (i < leftArr.length) {
            counts[leftArr[i]] += rightCounter;
            indices[k++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            indices[k++] = rightArr[j++];
        }
    };

    mergeSort(0, nums.length - 1);
    return counts;
};

The trick is merging indices while comparing values, so the original position of every element survives the sort. The rightCounter is the insight: it holds how many right-half elements have already been placed, and when a left-half element is finally placed, all of those are smaller numbers to its right. Each placement is constant work, so the sort still runs in

O(N log N)
time with
O(N)
space. This is the same counting machinery behind the related inversion-count question, so worth drilling until it is reflex.

7. The Skyline Problem

LeetCode 218 | Difficulty: Hard

Brief: Return the key points that trace the skyline formed by a set of rectangular buildings.

Why this pattern: Split the buildings in half, compute each half’s skyline, then merge the two skylines like two sorted lists. The combine step is what makes this problem hard.

Key Insight: Two skylines merge by walking both lists in x order, tracking the current height of each skyline, and emitting a point only when the maximum height changes. Equal x positions are consumed together.

Visual:

    graph TD
    A["Left skyline"] --> M["Walk both skylines by x"]
    B["Right skyline"] --> M
    M --> C["x=1: max(10, 0) = 10, emit point"]
    C --> D["x=2: max(10, 6) = 10, no change"]
    D --> E["x=4: max(10, 0) = 10, no change"]
    E --> F["x=5: max(0, 0) = 0, emit point"]
    F --> G["Merged skyline"]

Code:

var getSkyline = function(buildings) {
    if (buildings.length === 0) return [];
    if (buildings.length === 1) {
        const [l, r, h] = buildings[0];
        return [[l, h], [r, 0]]; // one building: up at l, down at r
    }

    const mid = Math.floor(buildings.length / 2);
    const left = getSkyline(buildings.slice(0, mid));
    const right = getSkyline(buildings.slice(mid));
    return merge(left, right);
};

function merge(left, right) {
    const res = [];
    let h1 = 0, h2 = 0; // current height of each skyline
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        let x, h;
        if (left[i][0] < right[j][0]) {
            x = left[i][0];
            h1 = left[i][1];
            i++;
        } else if (left[i][0] > right[j][0]) {
            x = right[j][0];
            h2 = right[j][1];
            j++;
        } else {
            // Same x: both heights update before deciding
            x = left[i][0];
            h1 = left[i][1];
            h2 = right[j][1];
            i++;
            j++;
        }
        h = Math.max(h1, h2);
        // Emit only when the combined height actually changes
        if (res.length === 0 || res[res.length - 1][1] !== h) {
            res.push([x, h]);
        }
    }
    while (i < left.length) res.push(left[i++]);
    while (j < right.length) res.push(right[j++]);
    return res;
}

The recursion itself is standard: base case for a single building, split in half, merge the two skylines. The merge is where the difficulty hides. Each skyline point carries the height that is in effect from that x onward, so the merge compares the two current heights and emits a point only when their maximum changes. Points with the same x must be consumed together, or the heights update out of order. With N buildings the recursion is

O(N log N)
time and
O(N)
space, and the merge step is the same pairwise-interleave skill from every other problem on this page.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover the full range of divide and conquer. Start with the combine step in Merge Two Sorted Lists, build up to the full merge sort in Sort an Array, and finish with the modified combine steps in Count of Smaller Numbers After Self and The Skyline Problem. By the end, you should be able to spot when a problem can be split into independent halves and reach for the right template.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .