Command Palette

Search for a command to run...

Hectal
Problem 42.10 · Pattern Recognition DrillsHard

Split Array Largest Sum

What it teaches:

Practise it on judges as “Split Array Largest Sum”.

In plain words

Turn the question around: given a limit, can you cut the list into at most k pieces with no piece over the limit? That is easy to check by filling each piece until the next number would go over. A bigger limit never needs more pieces, so the possible limits split into "too small" then "works". Narrow down to the smallest limit that works, starting between the biggest single number and the total.

Return the smallest possible largest piece. Example: nums = [7,2,5,10,8], k = 2 → 18.

The problem

Split nums into k non-empty contiguous parts to minimise the largest part sum. Return that minimum.

Example 1

Input: nums = [7,2,5,10,8], k = 2
Output: 18

[7,2,5] and [10,8].

Constraints

  • 1 ≤ n ≤ 1000
  • 1 ≤ k ≤ min(50, n)

Pattern clues in the wording

  • → Minimise the largest
  • → If limit L works, any larger limit works

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public int splitArray(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums = [7,2,5,10,8]
k = 2
18
2
nums = [1,2,3,4,5]
k = 2
9
3
nums = [1,4,4]
k = 3
4

From slow to fast

Approaches

1. Binary search + greedy check · O(n log(sum))
1

Binary search + greedy check

Time O(n log(sum)) Space O(1)

parts(limit): start a new part whenever adding the next number would exceed the limit. Find the smallest limit with parts ≤ k.

▶ Dry run: Guess a limit, check it greedilynums = [7,2,5,10,8], k = 2
7
0
2
1
5
2
10
3
8
4

range(vars)

lo: 10hi: 32

Step 1/5No piece can be smaller than the biggest number (10) and one piece holds everything (32). The answer is in [10, 32].

Approach 1
class Solution {
    public int splitArray(int[] nums, int k) {
        long lo = 0, hi = 0;
        for (int x : nums) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (parts(nums, mid) <= k) hi = mid; else lo = mid + 1;
        }
        return (int) lo;
    }

    private int parts(int[] nums, long limit) {
        int count = 1;
        long run = 0;
        for (int x : nums) {
            if (run + x > limit) { count++; run = 0; }
            run += x;
        }
        return count;
    }
}

Verdict: Much simpler and faster than the O(k n²) DP.

Before you submit

Edge cases and common mistakes

Test these inputs

  • k = 1 (sum)
  • k = n (max element)

Mistakes people make

  • Starting lo at 0 or 1 (a limit below the largest element can't work).

Interview

Follow-up questions

Which other course problems share this shape?