Get started

Divide and Conquer Coding Problems: 17 Questions with Solutions

17 divide and conquer coding problems — 3 easy · 8 medium · 6 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 17
  • By difficulty: 3 easy · 8 medium · 6 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Split the input, solve each half, combine the answers: merge sort, counting inversions, the closest pair, building a balanced tree from a sorted array. The problems here practise writing the recursion so the combine step is cheap and the recursion depth stays logarithmic.

How divide and conquer works, step by step

wholehalvespairs1442136a-2011-3243-142516-57
Maximum subarray sum, with divide and conquer. Example: nums = [-2, 1, -3, 4, -1, 2, 1, -5]
  1. The best subarray lies wholly in the left half, wholly in the right half, or crosses the middle. The first two are the same problem on half the array, so solve them recursively, then compare them with the best sum that crosses.
  2. Split the array in half, then each half in half again, until every piece is a single element: 3 levels of splitting for 8 values, 15 pieces in all, each one waiting for an answer.
  3. A single element is its own best subarray, so the 8 pieces at the bottom are already solved. From here on everything is combining two answers into one on the way back up.
  4. Pairs combine, each taking the largest of its left best, its right best and its crossing sum: [-2, 1] → max(-2, 1, cross -1) = 1, [-3, 4] → max(-3, 4, cross 1) = 4, [-1, 2] → max(-1, 2, cross 1) = 2 and [1, -5] → max(1, -5, cross -4) = 1.
  5. The two halves combine the same way: [-2, 1, -3, 4] → max(1, 4, cross 2) = 4 and [-1, 2, 1, -5] → max(2, 1, cross 3) = 3.
  6. For the whole array the halves give 4 and 3. A crossing subarray must contain a[3] and a[4]: summing leftwards from the middle the best is 4 (from index 3), and rightwards 2 (up to index 6).
  7. So the answer is max(4, 3, 4 + 2) = 6, for [4, -1, 2, 1], which crosses the middle where neither half could see it. Each level does O(n) crossing work over log n levels: O(n log n).

Divide and Conquer study plan

13 of the 17 Divide and Conquer problems (3 easy, 7 medium and 3 hard) over 8 days, about 7 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 4 in the full list below are practice at your own pace. Then move on to Quickselect.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Quickselect

Divide and Conquer: the essentials

When to reach for it

A question about pairs (i, j) with i < j that a nested loop answers in O(n²) — count the inversions, the pairs with nums[i] > 2 * nums[j], the smaller elements to the right of each — where splitting the array lets each half be sorted and the pairs that cross the split be counted in a linear merge. Also searches that can throw away half, or a quadrant, at every step.

The pattern

Recurse on each half, then combine. In the merge-sort family both halves come back sorted, so for each element of the left half the cross pairs it forms are counted by a pointer that only ever moves forward through the right half — before or during the merge, while each element's side is still known.

def sort_count(a):                  # (sorted copy of a, inversion count)
    if len(a) <= 1: return a, 0
    h = len(a) // 2
    (left, x), (right, y) = sort_count(a[:h]), sort_count(a[h:])
    merged, inv, j = [], x + y, 0
    for v in left:
        while j < len(right) and right[j] < v:
            merged.append(right[j])
            j += 1
        inv += j                    # right[:j] are all smaller than v
        merged.append(v)
    return merged + right[j:], inv

Cost

The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n), with recursion O(log n) deep and O(n) for the merge buffers. A combine step that sorts instead of merging costs O(n log n) per level, making the whole O(n log² n).

Common mistakes

  • Counting cross pairs after the merge, when it is no longer known which side an element came from.
  • Using <= where the pair condition is strict, which counts equal elements as inversions.
  • Overflow: n = 10⁵ allows about 5 × 10⁹ inversions, beyond a 32-bit int.
  • A split that does not shrink the range, which recurses until the stack runs out.

Start with

All divide and conquer problems

Easy (3)

Medium (8)

Hard (6)

Companies that ask divide and conquer problems

  • Amazon 14 problems on divide and conquer
  • Google 12 problems on divide and conquer
  • Meta 7 problems on divide and conquer
  • Microsoft 6 problems on divide and conquer
  • Adobe 1 problem on divide and conquer
  • Apple 1 problem on divide and conquer
  • Flipkart 1 problem on divide and conquer
  • Uber 1 problem on divide and conquer

Next topic: Quickselect