AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Divide and Conquer coding problems

Split the input, solve each half, combine the answers: merge sort, counting inversions, the closest pair, building a balanced tree from a sorted array.

27 problems · 4 easy · 14 medium · 9 hard · judged by hidden tests in 13 languages

27problems

4 easy

14 medium

9 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Majority Element

How it works

Divide and Conquer, step by step

Maximum subarray sum, with divide and conquer

nums = [-2, 1, -3, 4, -1, 2, 1, -5]

a-2011-3243-142516-57

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.

0:01 / 0:28Step 1 of 7
Transcript · 7 steps

Study plan

Learn divide and conquer in 8 days

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

  1. Day 1

    about 1 h 15 min

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

  2. Day 2

    about 55 min

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

  3. Day 3

    about 1 h 10 min

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

  4. Day 4

    about 1 h 10 min

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

  5. Day 5

    about 1 h 10 min

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

  6. Day 6

    about 50 min

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

  7. Day 7

    about 50 min

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

  8. Day 8

    about 50 min

    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 Coding Problems: 27 Questions with Solutions

27 divide and conquer coding problems — 4 easy · 14 medium · 9 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 27
  • By difficulty: 4 easy · 14 medium · 9 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

14 of the 27 Divide and Conquer problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 13 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 (4)

Medium (14)

Hard (9)

Companies that ask divide and conquer problems

  • Amazon 24 problems on divide and conquer
  • Google 19 problems on divide and conquer
  • Microsoft 15 problems on divide and conquer
  • Meta 11 problems on divide and conquer
  • Zomato 3 problems on divide and conquer
  • Bloomberg 2 problems on divide and conquer
  • Flipkart 2 problems on divide and conquer
  • Uber 2 problems on divide and conquer
  • Adobe 1 problem on divide and conquer
  • Apple 1 problem on divide and conquer
  • Arcesium 1 problem on divide and conquer
  • Atlassian 1 problem on divide and conquer

Next topic: Quickselect