Split Array Largest Sum

Hard Binary Search Binary Search on Answer Space Original on LeetCode

Split Array Largest Sum is a hard binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the answer), runs in O(n · log(sum)) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dp over the last cut) up.

Problem

You get an integer array nums of non-negative numbers and an integer k. Cut nums into exactly k non-empty contiguous pieces, keeping the original order.

Each piece has a sum; the cost of a cut is the largest of those sums. Return the smallest possible cost.

Examples

Example 1

Input
nums = [4,2,7,1,5], k = 2
Output
13
Why
Cutting into [4,2,7] and [1,5] gives sums 13 and 6. No cut makes both pieces 12 or less.

Example 2

Input
nums = [3,3,3,3], k = 4
Output
3
Why
Each element becomes its own piece.

Example 3

Input
nums = [10,0,0,1], k = 3
Output
10
Why
The piece holding 10 always has a sum of at least 10, and [10], [0,0], [1] reaches it.

Constraints

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= min(50, nums.length)

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (DP over the last cut)O(k · n²)O(k · n)
Optimal (binary search on the answer)O(n · log(sum))O(1)

1Brute force (DP over the last cut)

TimeO(k · n²)k · n states, each trying up to n positions for the last cut.
SpaceO(k · n)The dp table (plus O(n) prefix sums).

Let dp[j][i] be the best possible largest sum when the first i elements are cut into exactly j pieces. The last piece is nums[p..i-1] for some p, so dp[j][i] = min over p of max(dp[j-1][p], sum(p..i-1)). Prefix sums give each piece sum in O(1).

  1. Build prefix sums pre[0..n].
  2. Set dp[0][0] = 0 and everything else to infinity.
  3. For j = 1..k and i = 1..n, try every start p of the last piece (j - 1 <= p < i): dp[j][i] = min(dp[j][i], max(dp[j - 1][p], pre[i] - pre[p])).
  4. Return dp[k][n].
class Solution {
    public int splitArray(int[] nums, int k) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
        int[][] dp = new int[k + 1][n + 1];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        dp[0][0] = 0;
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i <= n; i++) {
                for (int p = j - 1; p < i; p++) {
                    if (dp[j - 1][p] == Integer.MAX_VALUE) continue;
                    int cand = Math.max(dp[j - 1][p], pre[i] - pre[p]);
                    dp[j][i] = Math.min(dp[j][i], cand);
                }
            }
        }
        return dp[k][n];
    }
}

2Optimal (binary search on the answer)

TimeO(n · log(sum))About log2(10^9) ≈ 30 rounds of binary search, each an O(n) greedy scan.
SpaceO(1)Only a few counters.

Guess a cap on the largest piece sum. Greedily extend the current piece while it stays within the cap and start a new piece otherwise; this uses the fewest pieces possible for that cap. If the count is at most k, the cap is achievable (extra cuts never raise a sum). Feasibility is monotonic in the cap, so binary search between max(nums) and sum(nums).

  1. lo = max(nums), hi = sum(nums).
  2. While lo < hi: mid = lo + (hi - lo) / 2.
  3. Count pieces greedily with cap mid. If pieces <= k, hi = mid; else lo = mid + 1.
  4. Return lo.
class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0, hi = 0;
        for (int x : nums) {
            lo = Math.max(lo, x);
            hi += x;
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (pieces(nums, mid) <= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    private int pieces(int[] nums, int cap) {
        int count = 1, cur = 0;
        for (int x : nums) {
            if (cur + x > cap) {
                count++;
                cur = 0;
            }
            cur += x;
        }
        return count;
    }
}

Edge cases to test

  • k = 1: the answer is the sum of the whole array
  • k = nums.length: every element stands alone, so the answer is the maximum element
  • Zeros in the array: pieces may have sum 0
  • One huge element dominates: the answer is never below max(nums)

Hints

Hint 1

The answer always lies between max(nums) and sum(nums).

Hint 2

Flip the question: given a cap, can the array be cut into at most k pieces whose sums never exceed it? A greedy left-to-right scan answers that in O(n).

Hint 3

If a cap works, every larger cap works too. Binary search the smallest cap that works.

FAQ

What is the best time complexity for Split Array Largest Sum?

Optimal (binary search on the answer) runs in O(n · log(sum)) time and O(1) extra space. About log2(10^9) ≈ 30 rounds of binary search, each an O(n) greedy scan.

Which pattern does Split Array Largest Sum use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.

Is there a brute force solution for Split Array Largest Sum?

Yes. Brute force (DP over the last cut) takes O(k · n²) time and O(k · n) space. Let dp[j][i] be the best possible largest sum when the first i elements are cut into exactly j pieces.

Which edge cases should I test for Split Array Largest Sum?

k = 1: the answer is the sum of the whole array; k = nums.length: every element stands alone, so the answer is the maximum element; Zeros in the array: pieces may have sum 0; One huge element dominates: the answer is never below max(nums).