Split Array Largest Sum

Problem Statement

Split nums into k non-empty contiguous subarrays to minimise the largest subarray sum. Return that minimised largest sum.

Example

Input:  nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: [7,2,5] and [10,8] -> max sum 18.

Approach

Binary search the answer (the largest allowed sum) in [max(nums), sum(nums)]. For a candidate limit, greedily count how many pieces are needed so no piece exceeds it; pieces <= k means feasible. Minimise toward the smallest feasible limit.

Complexity

• Time: O(n log(sum - max))
• Space: O(1)

Solution Code

Python

def splitArray(nums, k):
    left, right = max(nums), sum(nums)
    while left < right:
        mid = (left + right) // 2
        pieces, cur = 1, 0
        for n in nums:
            if cur + n > mid:
                pieces += 1
                cur = 0
            cur += n
        if pieces <= k:
            right = mid
        else:
            left = mid + 1
    return left

Java

int splitArray(int[] nums, int k) {
    int left = 0, right = 0;
    for (int n : nums) { left = Math.max(left, n); right += n; }
    while (left < right) {
        int mid = left + (right - left) / 2;
        int pieces = 1, cur = 0;
        for (int n : nums) {
            if (cur + n > mid) { pieces++; cur = 0; }
            cur += n;
        }
        if (pieces <= k) right = mid;
        else left = mid + 1;
    }
    return left;
}

C++

int splitArray(vector<int>& nums, int k) {
    long long left = 0, right = 0;
    for (int n : nums) { left = max(left, (long long)n); right += n; }
    while (left < right) {
        long long mid = left + (right - left) / 2;
        int pieces = 1; long long cur = 0;
        for (int n : nums) {
            if (cur + n > mid) { pieces++; cur = 0; }
            cur += n;
        }
        if (pieces <= k) right = mid;
        else left = mid + 1;
    }
    return (int) left;
}

Key Takeaways

• Identical pattern to Ship Packages — only the wording changes.
• The greedy piece-count is monotone in the allowed limit.
• Reference: LeetCode 410 (Split Array Largest Sum).