Split Array Largest Sum

How it works

We can optimize the feasibility check using prefix sums and binary search. Instead of linearly scanning to find where each subarray should end, we use binary search on the prefix sum array to find the farthest index where the subarray sum stays within the target. This speeds up the check from O(n) to O(k log n) for each candidate.

Steps

1. Build a prefix sum array where prefix[i] is the sum of elements from index 0 to i-1.
2. Binary search on the answer as before.
3. In the feasibility check:
   • For each subarray start, binary search for the rightmost end where prefix[end] - prefix[start] <= target.
   • Count subarrays and verify it does not exceed k.
4. Return the smallest feasible value.

Complexity

• Time complexity: O(n + (k * log n * log s))
• Space complexity: O(n)

Where n is the size of the array nums, s is the sum of all the elements in the array, and k is the number of sub-arrays to form.

Things to watch for

Setting Incorrect Binary Search Bounds

The lower bound must be max(nums) (not 0 or 1) because no subarray sum can be smaller than the largest single element. The upper bound is sum(nums) representing the case where all elements are in one subarray. Using incorrect bounds leads to invalid answers or infinite loops.

Off-by-One in Subarray Counting

When checking if a target sum is feasible, starting the subarray count at 0 instead of 1 causes the algorithm to allow one extra split. The count should start at 1 since we always have at least one subarray before any splits occur.

Integer Overflow in Sum Calculations

For large arrays with large values, the sum of elements can overflow 32-bit integers. Using long or equivalent 64-bit types for prefix sums and running totals prevents incorrect comparisons and ensures the binary search operates on valid values.

Greedy Check Not Resetting Current Sum

In the feasibility check, when the current sum exceeds the target and a new subarray begins, the current sum must be reset to the current element (not to 0). Resetting to 0 loses the current element and produces incorrect subarray counts.

Confusing Minimizing Maximum with Maximizing Minimum

This problem asks to minimize the largest subarray sum, which means we want the smallest possible value that still allows a valid k-way split. Binary searching in the wrong direction (trying to maximize instead of minimize) yields incorrect results.

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        def canSplit(largest):
            subarrays = 0
            i = 0
            while i < n:
                l, r = i + 1, n
                while l <= r:
                    mid = l + (r - l) // 2
                    if prefix[mid] - prefix[i] <= largest:
                        l = mid + 1
                    else:
                        r = mid - 1
                subarrays += 1
                i = r
                if subarrays > k:
                    return False
            return True

        l, r = max(nums), sum(nums)
        res = r
        while l <= r:
            mid = l + (r - l) // 2
            if canSplit(mid):
                res = mid
                r = mid - 1
            else:
                l = mid + 1

        return res

class Solution {
private:
    vector<int> prefix;
    int n;

public:
    int splitArray(vector<int>& nums, int k) {
        n = nums.size();
        prefix.resize(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int l = *max_element(nums.begin(), nums.end());
        int r = accumulate(nums.begin(), nums.end(), 0);
        int res = r;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (canSplit(mid, k)) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return res;
    }

private:
    bool canSplit(int largest, int k) {
        int subarrays = 0, i = 0;
        while (i < n) {
            int l = i + 1, r = n;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (prefix[mid] - prefix[i] <= largest) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            subarrays++;
            i = r;
            if (subarrays > k) {
                return false;
            }
        }
        return true;
    }
};