Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Split Array Largest Sum

Cut an array into k contiguous parts so the largest part sum is as small as possible: brute force, dynamic programming, then binary search on the limit.

Updated Long read: 11 min read

Approaches at a glance

ApproachTimeSpace
Try every way to cutO(n^k)O(k)
Dynamic programmingO(k × n²)O(k × n)
Binary search on the limitO(n log S)O(1)

The problem

You are given an array of non-negative integers and a number k. Cut the array into exactly k parts. Each part must be a run of neighbouring elements, no part may be empty, and the order of the elements cannot be changed.

Every way of cutting has a largest part: the part whose elements add up to the most. Choose the cuts so that this largest sum is as small as possible, and return that sum. k is never more than the length of the array.

numbers = [6, 2, 5, 8, 3], k = 3
 
[6, 2, 5 | 8 | 3]    sums 13, 8, 3    largest 13
[6 | 2, 5 | 8, 3]    sums 6, 7, 11    largest 11
[6, 2 | 5 | 8, 3]    sums 8, 5, 11    largest 11
[6, 2 | 5, 8 | 3]    sums 8, 13, 3    largest 13
...
 
→ 11    (no way of cutting gets the largest part below 11)

Think of it as sharing a row of tasks among k people, where each person takes a block of neighbouring tasks and you want the busiest person to have as little as possible.

Approach 1: try every way to cut

Choose where the first part ends, then solve the same problem for the rest of the array with one part fewer. Take the best result over every choice.

JavaScript

function splitArrayBruteForce(numbers, k) {
  // Smallest possible largest sum when numbers[start..] is cut into `parts` parts.
  function best(start, parts) {
    if (parts === 1) {
      let rest = 0;
      for (let i = start; i < numbers.length; i++) rest += numbers[i];
      return rest;
    }
 
    let result = Infinity;
    let first = 0;
    // The first part ends at `end`. Leave at least one element for each later part.
    for (let end = start; end <= numbers.length - parts; end++) {
      first += numbers[end];
      result = Math.min(result, Math.max(first, best(end + 1, parts - 1)));
    }
    return result;
  }
 
  return best(0, k);
}

Python

def split_array_brute_force(numbers, k):
    # Smallest possible largest sum when numbers[start:] is cut into `parts` parts.
    def best(start, parts):
        if parts == 1:
            return sum(numbers[start:])
 
        result = float("inf")
        first = 0
        # The first part ends at `end`. Leave at least one element for each later part.
        for end in range(start, len(numbers) - parts + 1):
            first += numbers[end]
            result = min(result, max(first, best(end + 1, parts - 1)))
        return result
 
    return best(0, k)

There are k - 1 cuts to place among n - 1 gaps, and the number of ways to do that grows very quickly: for 30 elements and 10 parts it is about ten million, and for 50 elements and 25 parts it is more than sixty million million.

Time O(n^k) as an upper limit. Space O(k) for the recursion.

Approach 2: dynamic programming

The brute force solves the same sub-problem many times: "the best way to cut the last 4 elements into 2 parts" is recalculated for every arrangement of the elements before them. Dynamic programming stores each of those answers in a table and works it out once.

Let best[p][i] be the answer for the first i elements cut into p parts. The last part must start somewhere: say it covers elements j to i - 1. Then the first j elements form p - 1 parts, and the largest sum is the bigger of best[p - 1][j] and the sum of the last part. Try every j and keep the smallest. The sum of any run comes from a prefix sum array in one subtraction.

JavaScript

function splitArrayDp(numbers, k) {
  const n = numbers.length;
 
  // prefix[i] is the sum of the first i elements.
  const prefix = [0];
  for (const value of numbers) prefix.push(prefix[prefix.length - 1] + value);
 
  const best = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(Infinity));
  best[0][0] = 0;
 
  for (let p = 1; p <= k; p++) {
    for (let i = p; i <= n; i++) {
      // The last part is numbers[j..i-1].
      for (let j = p - 1; j < i; j++) {
        const largest = Math.max(best[p - 1][j], prefix[i] - prefix[j]);
        best[p][i] = Math.min(best[p][i], largest);
      }
    }
  }
  return best[k][n];
}

Python

def split_array_dp(numbers, k):
    n = len(numbers)
 
    # prefix[i] is the sum of the first i elements.
    prefix = [0]
    for value in numbers:
        prefix.append(prefix[-1] + value)
 
    best = [[float("inf")] * (n + 1) for _ in range(k + 1)]
    best[0][0] = 0
 
    for p in range(1, k + 1):
        for i in range(p, n + 1):
            # The last part is numbers[j:i].
            for j in range(p - 1, i):
                largest = max(best[p - 1][j], prefix[i] - prefix[j])
                best[p][i] = min(best[p][i], largest)
    return best[k][n]

The table has k × n cells and each takes up to n steps to fill.

Time O(k × n²). Space O(k × n).

For 1,000 elements and 50 parts that is around 25 million steps, which is acceptable. The next approach needs a few tens of thousands.

Approach 3: binary search on the limit

Turn the question round. Do not ask "where should the cuts go?". Ask: "if no part may add up to more than limit, how many parts are needed?"

That question is easy. Walk along the array, adding elements to the current part. When the next element would push the part over the limit, close the part and start a new one with that element. Packing each part as full as possible uses the fewest parts, because closing a part early can never reduce the work left for the later ones.

JavaScript

// Fewest parts when no part may add up to more than limit.
// limit must be at least the largest element.
function partsNeededWithin(numbers, limit) {
  let parts = 1;
  let running = 0;
 
  for (const value of numbers) {
    if (running + value > limit) {
      parts++;           // close the current part and start a new one
      running = value;
    } else {
      running += value;
    }
  }
  return parts;
}

Python

# Fewest parts when no part may add up to more than limit.
# limit must be at least the largest element.
def parts_needed_within(numbers, limit):
    parts = 1
    running = 0
 
    for value in numbers:
        if running + value > limit:
            parts += 1         # close the current part and start a new one
            running = value
        else:
            running += value
    return parts

A limit "works" if it needs k parts or fewer. Fewer is fine: any part with two or more elements can be cut again, which adds a part without making any sum larger, and since k is at most the array's length this can be repeated until there are exactly k.

Now look at how the test behaves as the limit grows, for numbers = [6, 2, 5, 8, 3] and k = 3:

limit:         8    9    10   11   12   13   14   ...  24
parts needed:  4    4    4    3    3    2    2    ...  1
at most 3?     no   no   no   yes  yes  yes  yes  ...  yes
                              ↑
                   the smallest limit that works

A more generous limit never needs more parts, so the answers switch from "no" to "yes" once. The smallest limit that works is the answer to the original question, and binary search finds it. This is the "smallest value that passes" form of the binary search on the answer pattern.

  • Range. The limit cannot be below the largest element, since that element has to sit in some part. It never needs to exceed the sum of the whole array, which is one part holding everything.
  • Test. partsNeededWithin(numbers, limit) <= k.
  • Direction. Failures first, so a passing middle is kept with hi = mid.

JavaScript

function splitArray(numbers, k) {
  let lo = Math.max(...numbers);
  let hi = numbers.reduce((total, value) => total + value, 0);
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (partsNeededWithin(numbers, mid) <= k) {
      hi = mid;        // this limit works: try a smaller one
    } else {
      lo = mid + 1;    // too tight: the limit must be larger
    }
  }
  return lo;
}

Python

def split_array(numbers, k):
    lo = max(numbers)
    hi = sum(numbers)
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if parts_needed_within(numbers, mid) <= k:
            hi = mid        # this limit works: try a smaller one
        else:
            lo = mid + 1    # too tight: the limit must be larger
    return lo

Walkthrough

numbers = [6, 2, 5, 8, 3], k = 3. The largest element is 8 and the total is 24.

lo hi mid Greedy parts under limit mid Count At most 3? Action
8 24 16 [6, 2, 5] [8, 3] 2 Yes hi = 16
8 16 12 [6, 2] [5] [8, 3] 3 Yes hi = 12
8 12 10 [6, 2] [5] [8] [3] 4 No lo = 11
11 12 11 [6, 2] [5] [8, 3] 3 Yes hi = 11
11 11 lo equals hi: return 11

With a limit of 10 the 8 and the 3 cannot share a part, which forces a fourth part. With 11 they can.

The search always lands on a sum that some real split produces. If the smallest working limit were larger than every part in its greedy split, the limit could be lowered by one and still work, so it would not have been the smallest.

With S as the sum of the array, the range holds at most S values, so there are about log S tests of n steps each.

Time O(n log S). Space O(1).

Comparing the approaches

Approach Time Space Notes
Try every way to cut O(n^k) O(k) Only for very small inputs; useful for checking the others
Dynamic programming O(k × n²) O(k × n) Does not depend on how large the values are
Binary search on the limit O(n log S) O(1) Fastest; depends on the values being whole numbers

The binary search is tied to the size of the numbers, not only to how many there are, but the tie is weak: a total of a million million still means only about 40 tests.

The same method solves any "share a row of items among k groups so the heaviest group is as light as possible" question. Koko Eating Bananas is a gentler exercise with the same loop and a simpler test.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python. splitArray calls partsNeededWithin, so copy that function as well.

JavaScript

console.log(partsNeededWithin([6, 2, 5, 8, 3], 10)); // 4
console.log(splitArray([6, 2, 5, 8, 3], 3)); // 11
console.log(splitArray([6, 2, 5, 8, 3], 1)); // 24
console.log(splitArray([6, 2, 5, 8, 3], 5)); // 8
console.log(splitArrayDp([6, 2, 5, 8, 3], 2)); // 13

Python

print(parts_needed_within([6, 2, 5, 8, 3], 10))  # 4
print(split_array([6, 2, 5, 8, 3], 3))  # 11
print(split_array([6, 2, 5, 8, 3], 1))  # 24
print(split_array([6, 2, 5, 8, 3], 5))  # 8
print(split_array_dp([6, 2, 5, 8, 3], 2))  # 13

The comment after each line is the result you should see.

Common mistakes

  • Starting the range at 0 or 1. With a limit below the largest element, the greedy count is meaningless: it puts that element in a part on its own and carries on as if the part were within the limit. Start at the largest element.
  • Testing for exactly k parts. Using === k breaks the search, because a generous limit needs fewer than k parts and would be marked as failing. The test is "k or fewer".
  • Starting the count at 0. The first part is open before any element is read, so parts starts at 1.
  • Using >= in the greedy check. A part may add up to exactly the limit. Only going over it forces a new part.
  • Sorting the array. The parts must be runs of neighbours in the original order. Sorting solves a different problem.
  • Assuming it works with negative numbers. With negative values a larger limit can need more parts, the test stops being monotonic, and only the dynamic programming approach remains correct.
  • Overflow in other languages. The total of the array can exceed a 32-bit integer. Use a 64-bit type for hi, mid and the running sum in Java or C++.

Original problem: LeetCode 410: Split Array Largest Sum