Split Array Largest Sum

Problem

You are given an array nums and an integer k. nums represents the weights of n consecutive tasks while k represents the number of workers. Tasks are assigned to the workers as contiguous blocks.

Your goal is to distribute the work so that the heaviest workload (sum of task weights for any single worker) is as small as possible.

Return the minimum possible value of the maximum workload.

Example 1

Input:

nums = [4, 8, 15, 7, 3], k = 3

Output: 15

Explanation: One optimal split is [4, 8] (sum=12), [15] (sum=15), [7, 3] (sum=10). The maximum workload among workers is 15.

Example 2

Input:

nums = [6, 3, 9, 2, 1, 8], k = 2

Output: 18

Explanation: Split into [6, 3, 9] (sum=18) and [2, 1, 8] (sum=11). The heaviest workload is 18. Any other split with 2 groups results in a higher maximum.

Understanding the Problem

We have an array of positive integers and need to split it into exactly k contiguous subarrays. Among all possible ways to split, we want to find the one where the maximum subarray sum is as small as possible.

Think of it like distributing work among k workers, where each worker handles a contiguous portion. We want to minimize the maximum load on any single worker.

Key Observation: The Answer Has Bounds

Before diving into the solution, let’s think about what values the answer could possibly take:

• Minimum possible: At least max(nums) = 10. Why? Because every element has to land in some subarray, and a subarray containing the largest element will have a sum of at least that element’s value. If we tried a max sum of, say, 9, the element 10 couldn’t fit in any subarray at all — the split would be impossible. So max(nums) is the smallest max-sum that’s even worth considering.
• Maximum possible: At most sum(nums) = 32. This happens when k = 1 (one big subarray).

So our answer lies in the range [10, 32].

Why Binary Search?

Here’s the crucial observation: if we can split with max sum X, we can definitely split with any max sum greater than X.

This monotonic property is exactly what enables binary search! The search space is divided into two halves: values that don’t work, and values that do. Binary search finds the boundary.

This is the “Binary Search on Answer” pattern. Instead of searching through the array for an element, we search through the space of possible answers to find the optimal one. The monotonic property guarantees binary search will find it.

The Binary Search Algorithm

Here’s how the binary search works:

• Initialize: left = max(nums), right = sum(nums)
• Loop while left < right: Pick mid = (left + right) / 2
• If we can split with max sum ≤ mid: answer might be smaller → right = mid
• If we can’t: answer must be larger → left = mid + 1
• Return left (the minimum valid answer)

The Feasibility Check (Helper Function)

For each mid, we need a helper function to check: “Can we split into ≤ k subarrays with max sum ≤ mid?”

Greedy approach (O(n) per check):

• Iterate left to right, greedily adding elements to the current subarray
• When the sum would exceed maxSum, start a new subarray
• Return true if subarrays_needed ≤ k, else false

Walkthrough

Let’s trace through nums = [7, 2, 5, 10, 8] with k = 2 to see how the binary search narrows down the answer.

Step 1: Initialize the search bounds

First, we establish the range of possible answers. The minimum possible max-sum is max(nums) = 10 — no matter how we split, the subarray containing 10 will have a sum of at least 10, so there’s no point trying anything smaller. The maximum is sum(nums) = 32 (if we put everything in one subarray).

Our search space is [10, 32]. Now we start binary searching for the minimum valid max-sum.

Step 2: First binary search iteration

We try mid = (10 + 32) / 2 = 21. Can we split into ≤ 2 subarrays where each has sum ≤ 21?

Using the greedy check: [7, 2, 5] has sum 14 ≤ 21 ✓, then [10, 8] has sum 18 ≤ 21 ✓. That’s only 2 subarrays, so yes, it’s feasible!

Since mid = 21 works, the answer might be even smaller. We set right = mid = 21 to search the lower half.

Step 3: Second binary search iteration

Now left = 10, right = 21. We try mid = (10 + 21) / 2 = 15. Can we split with max sum ≤ 15?

Greedy check: [7, 2, 5] sum = 14 ≤ 15 ✓, but [10] alone is already 10 ≤ 15 ✓, then [8] is 8 ≤ 15 ✓. Wait, that’s 3 subarrays! We only have k = 2.

Actually, let’s be more careful: [7, 2] sum = 9, adding 5 gives 14 ≤ 15 ✓. Adding 10 would give 24 > 15 ✗, so start new subarray. [10] sum = 10 ≤ 15 ✓. Adding 8 would give 18 > 15 ✗, so start new subarray. [8] sum = 8. That’s 3 subarrays, but we need ≤ 2. Not feasible!

Since mid = 15 doesn’t work, the answer must be larger. We set left = mid + 1 = 16.

Step 4: Continue narrowing

Now left = 16, right = 21. We continue binary searching:

• mid = 18: Can we split with max ≤ 18? [7, 2, 5] = 14 ≤ 18 ✓, [10, 8] = 18 ≤ 18 ✓. Yes! Set right = 18.
• mid = 17: Can we split with max ≤ 17? [7, 2, 5] = 14 ≤ 17 ✓, [10] = 10 ≤ 17 ✓, [8] = 8 ≤ 17 ✓. That’s 3 subarrays. No! Set left = 18.

Now left = right = 18, so we’re done!

Result: 18

The minimum possible max-subarray-sum is 18, achieved by splitting [7, 2, 5] (sum = 14) and [10, 8] (sum = 18).

Visualization

def splitArray(nums, k):
    def canSplit(maxSum):
        subarrays = 1
        currentSum = 0
        for num in nums:
            if currentSum + num > maxSum:
                subarrays += 1
                currentSum = num
            else:
                currentSum += num
        return subarrays <= k
    
    left = max(nums)
    right = sum(nums)
    
    while left < right:
        mid = (left + right) // 2
        if canSplit(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0;
        int right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private boolean canSplit(int[] nums, int k, int maxSum) {
        int subarrays = 1;
        int currentSum = 0;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                subarrays++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return subarrays <= k;
    }
}

func splitArray(nums []int, k int) int {
    left, right := 0, 0
    for _, num := range nums {
        if num > left {
            left = num
        }
        right += num
    }
    
    canSplit := func(maxSum int) bool {
        subarrays := 1
        currentSum := 0
        for _, num := range nums {
            if currentSum + num > maxSum {
                subarrays++
                currentSum = num
            } else {
                currentSum += num
            }
        }
        return subarrays <= k
    }
    
    for left < right {
        mid := left + (right - left) / 2
        if canSplit(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

function splitArray(nums: number[], k: number): number {
    function canSplit(maxSum: number): boolean {
        let subarrays = 1;
        let currentSum = 0;
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                subarrays++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return subarrays <= k;
    }
    
    let left = Math.max(...nums);
    let right = nums.reduce((a, b) => a + b, 0);
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canSplit(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

Solution

The algorithm combines binary search with a greedy feasibility check:

• Initialize bounds: left = max(nums), right = sum(nums)
• Binary search: While left < right Calculate mid = (left + right) / 2
• Use the greedy helper to check if we can split with max sum ≤ mid
• If yes: answer might be smaller, set right = mid
• If no: answer must be larger, set left = mid + 1
• Return left as the answer

The greedy check runs in O(n) time, and binary search runs O(log(sum - max)) iterations, giving us O(n * log(sum)) total time complexity.

When to Use Binary Search on Answer

This technique applies when:

• The answer lies within a known range [lo, hi]
• There’s a monotonic predicate: if answer x is feasible, then all values > x (or < x) are also feasible
• You can efficiently check if a given candidate is feasible

Common problems using this pattern:

• Minimize the maximum (or maximize the minimum) of something
• Capacity/allocation problems
• “Can we do X with budget Y?” questions

When you see “minimize the maximum” or “maximize the minimum”, consider binary search on the answer. The key is identifying the monotonic property and designing an efficient feasibility check.