☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Split array - largest sum

Hard TUF ID 79 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of non-negative integers and an integer k. Cut the array into exactly k non-empty, contiguous pieces. Every split has a “largest piece sum”, the biggest total among its k pieces. Among all possible splits, return the smallest possible largest piece sum. If k is larger than the number of elements, no split exists; return -1.

Constraints: 1 ≤ n ≤ 1000, 0 ≤ nums[i] ≤ 10^6, 1 ≤ k ≤ 50. The total of all elements fits in an int under these limits.

Example 1

nums = [7, 2, 5, 10, 8], k = 2
answer = 18          // [7, 2, 5] and [10, 8]: sums 14 and 18, the 18 cannot be lowered

Example 2

nums = [1, 2, 3, 4, 5], k = 2
answer = 9           // [1, 2, 3] and [4, 5]: sums 6 and 9

Example 3

nums = [1, 2, 3], k = 4
answer = -1          // four non-empty pieces cannot be cut from three elements

This is the same problem as the Book Allocation problem and the Painter’s Partition problem, just with different nouns. The whole family is solved by one idea: instead of searching for the split, search for the answer.

The check that every approach shares

Suppose someone hands us a limit L and asks: “can the array be cut into at most k pieces so that no piece sums to more than L?” That question is easy. Walk left to right and keep adding elements to the current piece; the moment the next element would push the piece over L, close the piece and start a new one. Being greedy here is safe: closing a piece later never helps, because a piece that is already as full as it can be leaves the most room for everything that follows.

static int piecesNeeded(int[] nums, int limit) {
    int pieces = 1;
    long sum = 0;
    for (int x : nums) {
        if (sum + x > limit) { pieces++; sum = 0; }
        sum += x;
    }
    return pieces;
}

The function assumes limit is at least the largest element, so that a single element always fits in a piece on its own. Every caller below guarantees that. If piecesNeeded(nums, L) <= k, the limit L is achievable: we can always merge nothing and leave some pieces unused, or, equivalently, split a piece further, which never increases the largest sum.

Approach 1: Brute force over the answer

Intuition. The answer is a piece sum, so it lies between the largest single element (no piece can be smaller than its biggest member) and the total of the whole array (one piece holding everything). Try every candidate limit in that range in increasing order; the first one that needs at most k pieces is the smallest achievable limit, which is exactly what is asked.

Algorithm.

  1. If k > n, return -1.
  2. Compute max and sum of the array.
  3. For limit = max, max + 1, ..., sum: if piecesNeeded(nums, limit) <= k, return limit.
static int bruteForce(int[] nums, int k) {
    int n = nums.length;
    if (k > n) return -1;
    int max = 0, sum = 0;
    for (int x : nums) { max = Math.max(max, x); sum += x; }
    for (int limit = max; limit <= sum; limit++) {
        if (piecesNeeded(nums, limit) <= k) return limit;
    }
    return sum;
}

Complexity. Time O(n × (sum − max)): up to sum − max + 1 candidates, each checked in a linear pass. Space O(1).

With sum as large as 10^9 this is hopeless, but it establishes the two facts the optimal approach needs: the answer lives in [max, sum], and we can test any candidate in linear time.

Approach 2: Dynamic programming

Intuition. A classical alternative that does not search the answer space at all. Let dp[i][j] be the smallest possible largest-piece sum when the first i elements are cut into exactly j pieces. The last piece must be some suffix nums[p .. i-1]; everything before it is a smaller instance of the same problem with j − 1 pieces. Trying every p gives the recurrence

dp[i][j] = min over p of max(dp[p][j-1], sum(nums[p .. i-1])).

Prefix sums make each piece sum O(1).

Algorithm.

  1. If k > n, return -1.
  2. Build prefix[i] = nums[0] + ... + nums[i-1].
  3. Fill a table of size (n+1) × (k+1) with “infinity”; set dp[0][0] = 0.
  4. For every i from 1 to n and every j from 1 to min(i, k), try every cut position p from j − 1 to i − 1 (there must be at least j − 1 elements before the last piece) and keep the minimum of max(dp[p][j-1], prefix[i] − prefix[p]).
  5. Return dp[n][k].
static int better(int[] nums, int k) {
    int n = nums.length;
    if (k > n) return -1;
    long[] prefix = new long[n + 1];
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
    long[][] dp = new long[n + 1][k + 1];
    for (long[] row : dp) Arrays.fill(row, Long.MAX_VALUE);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= Math.min(i, k); j++) {
            for (int p = j - 1; p < i; p++) {               // last piece is nums[p .. i-1]
                if (dp[p][j - 1] == Long.MAX_VALUE) continue;
                long candidate = Math.max(dp[p][j - 1], prefix[i] - prefix[p]);
                dp[i][j] = Math.min(dp[i][j], candidate);
            }
        }
    }
    return (int) dp[n][k];
}

Complexity. Time O(k × n^2): for each of the n × k states we scan up to n cut positions. Space O(n × k) for the table.

The DP is worth knowing because it generalises to variants where the greedy check breaks down (for example when pieces have individual costs), but for this exact problem it is slower than what follows, and the n^2 factor hurts on long arrays.

Approach 3: Optimal, binary search on the answer

Intuition. Look at how piecesNeeded behaves as the limit grows: a larger limit can only let pieces hold more, so the number of pieces never increases. That makes the predicate “piecesNeeded(nums, L) <= k” monotone: false for every L below some threshold and true for every L at or above it. A monotone predicate over a range of integers is exactly what binary search finds the boundary of. The brute force scanned the range [max, sum] linearly; binary search covers it in about 30 probes.

Algorithm.

  1. If k > n, return -1.
  2. Set lo = max, hi = sum, ans = sum.
  3. While lo <= hi: compute mid.
    • If piecesNeeded(nums, mid) <= k, the limit mid works; record ans = mid and look for something smaller with hi = mid − 1.
    • Otherwise mid is too tight; set lo = mid + 1.
  4. Return ans.
static int optimal(int[] nums, int k) {
    int n = nums.length;
    if (k > n) return -1;
    int max = 0, sum = 0;
    for (int x : nums) { max = Math.max(max, x); sum += x; }
    int lo = max, hi = sum, ans = sum;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (piecesNeeded(nums, mid) <= k) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on nums = [7, 2, 5, 10, 8], k = 2. Here max = 10, sum = 32.

lo hi mid pieces at limit mid pieces ≤ 2? action
10 32 21 [7,2,5] [10,8] → 2 yes ans = 21, hi = 20
10 20 15 [7,2,5] [10] [8] → 3 no lo = 16
16 20 18 [7,2,5] [10,8] → 2 yes ans = 18, hi = 17
16 17 16 [7,2,5] [10] [8] → 3 no lo = 17
17 17 17 [7,2,5] [10] [8] → 3 no lo = 18

lo > hi, so the answer is 18.

Complexity. Time O(n log(sum)): about log2(sum − max) probes, each a linear pass. Space O(1).

Why is the boundary the true optimum and not just “some achievable limit”? Every achievable limit L corresponds to a real split whose largest piece is at most L, and the smallest achievable L can be met with equality: if the best split had largest piece S < L, then S itself would be achievable, contradicting minimality. So the smallest L passing the check is the exact largest piece sum of an optimal split.

Edge cases and pitfalls