Problem Description

Given an array of non-negative integers nums and an integer k, split the array into k non-empty continuous subarrays such that the largest sum among these subarrays is minimized.

• Every element of nums must be included in exactly one subarray.
• Each subarray must be continuous (i.e., a contiguous segment of nums).
• Your goal is to minimize the largest sum among these k subarrays.
• It is guaranteed that at least one valid solution exists.

For example, given nums = [7,2,5,10,8] and k = 2, the optimal split is [7,2,5] | [10,8], where the largest sum is 18.

Thought Process

The brute-force way to solve this problem is to try every possible way to split the array into k continuous subarrays, calculate the largest sum for each split, and find the minimum among them. However, this approach is highly inefficient, especially for larger arrays, because the number of possible splits grows exponentially.

To optimize, we need to realize that the problem is about partitioning the array so that the largest sum is as small as possible. This hints at a binary search on the answer: if we could check whether a particular value is a possible answer (i.e., can we split the array into k subarrays such that no subarray has a sum greater than this value?), we could efficiently find the minimum possible largest sum.

Thus, the key insight is to use binary search to find the smallest maximum subarray sum, and use a greedy method to check if a given candidate sum is feasible.

Solution Approach

Here’s how we solve the problem step by step:

1. Define the Search Space:
   • The minimum possible largest sum is the largest single element in nums (because every subarray must contain at least one element).
   • The maximum possible largest sum is the sum of all elements in nums (if we don't split at all).
2. Binary Search:
   • We perform binary search between these two limits.
   • For a mid-value, we check: can we split the array into at most k subarrays so that no subarray sum exceeds mid?
3. Feasibility Check (Greedy):
   • Iterate through nums, accumulating a running sum. If adding the next number would exceed the current mid-value, start a new subarray.
   • Count how many subarrays are formed. If this number is greater than k, mid is too small.
4. Update Binary Search:
   • If it is possible to split with the current mid-value, try a smaller value (move left).
   • If not, try a larger value (move right).
5. Return the Answer:
   • The smallest mid-value that passes the check is the answer.

This approach is efficient because binary search reduces the number of checks, and the greedy check is linear in the size of nums.

Example Walkthrough

Let's use nums = [7,2,5,10,8] and k = 2 as our example.

1. Search Space:
   • Lowest possible largest sum: max(nums) = 10
   • Highest possible largest sum: sum(nums) = 32
2. Binary Search Iterations:
   • Mid = (10 + 32) // 2 = 21
   • Can we split into ≤2 parts with largest sum ≤21?
   • Try: [7,2,5] (sum=14), add 10 (sum=24 > 21), so split. New subarray: [10] (sum=10), add 8 (sum=18). Total splits: 2 (valid).
   • Try smaller: right = 21
   • Mid = (10 + 21) // 2 = 15
   • Try: [7,2,5] (sum=14), add 10 (sum=24 > 15), split. [10] (sum=10), add 8 (sum=18 > 15), split. [8] (sum=8). Splits: 3 (>2, invalid).
   • Try larger: left = 16
   • Mid = (16 + 21) // 2 = 18
   • Try: [7,2,5] (sum=14), add 10 (sum=24 > 18), split. [10] (sum=10), add 8 (sum=18). Splits: 2 (valid).
   • Try smaller: right = 18
   • Mid = (16 + 18) // 2 = 17
   • Try: [7,2,5] (sum=14), add 10 (sum=24 > 17), split. [10] (sum=10), add 8 (sum=18 > 17), split. [8] (sum=8). Splits: 3 (>2, invalid).
   • Try larger: left = 18
3. Final Answer:
   • Left = 18, right = 18. Done. Minimum largest sum is 18.

Code Implementation

class Solution:
    def splitArray(self, nums, k):
        def can_split(max_sum):
            count, curr = 1, 0
            for num in nums:
                if curr + num > max_sum:
                    count += 1
                    curr = num
                else:
                    curr += num
            return count <= k

        left, right = max(nums), sum(nums)
        while left < right:
            mid = (left + right) // 2
            if can_split(mid):
                right = mid
            else:
                left = mid + 1
        return left
      

class Solution {
public:
    bool canSplit(vector<int>& nums, int k, int maxSum) {
        int count = 1, curr = 0;
        for (int num : nums) {
            if (curr + num > maxSum) {
                count++;
                curr = num;
            } else {
                curr += num;
            }
        }
        return count <= k;
    }

    int splitArray(vector<int>& nums, int k) {
        int left = *max_element(nums.begin(), nums.end());
        int right = accumulate(nums.begin(), nums.end(), 0);
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};
      

class Solution {
    private boolean canSplit(int[] nums, int k, int maxSum) {
        int count = 1, curr = 0;
        for (int num : nums) {
            if (curr + num > maxSum) {
                count++;
                curr = num;
            } else {
                curr += num;
            }
        }
        return count <= k;
    }

    public int splitArray(int[] nums, int k) {
        int left = Arrays.stream(nums).max().getAsInt();
        int right = Arrays.stream(nums).sum();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
      

var splitArray = function(nums, k) {
    function canSplit(maxSum) {
        let count = 1, curr = 0;
        for (let num of nums) {
            if (curr + num > maxSum) {
                count++;
                curr = num;
            } else {
                curr += num;
            }
        }
        return count <= k;
    }
    let left = Math.max(...nums);
    let right = nums.reduce((a, b) => a + b, 0);
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canSplit(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};
      

Time and Space Complexity

• Brute-force approach:
  • Time: Exponential, as it tries all possible ways to split the array into k parts.
  • Space: Exponential, due to recursion stack or storage of all possible splits.
• Optimized (Binary Search + Greedy):
  • Time: O(n log S), where n is the length of nums, and S is the difference between the sum of nums and the maximum element. For each binary search step (log S), we do a linear scan (O(n)).
  • Space: O(1) (excluding input), as we use only a few variables for counting.

Summary

The "Split Array Largest Sum" problem challenges us to partition an array into k continuous subarrays so that the largest sum among them is minimized. While brute-force is infeasible, we achieve an efficient solution by combining binary search (to find the minimal feasible largest sum) with a greedy check (to verify feasibility). This approach is elegant because it leverages the monotonic nature of the problem and transforms a seemingly complex partitioning problem into a series of manageable checks.