Split Array Largest Sum [Hard] — Binary Search on Answer

Problem Statement

Split array into m non-empty subarrays to minimize the largest subarray sum.

Input: nums=[7,2,5,10,8], m=2 → Output: 18

Intuition

Binary search on the answer (min possible = max element, max = total sum). For each mid, greedily check if we can split into ≤ m groups each with sum ≤ mid.

Solutions

C++

bool canSplit(vector<int>& nums, int m, long long limit) {
    int groups=1; long long cur=0;
    for (int n:nums) { if(cur+n>limit){groups++;cur=0;} cur+=n; }
    return groups<=m;
}
int splitArray(vector<int>& nums, int m) {
    long long lo=*max_element(nums.begin(),nums.end()), hi=accumulate(nums.begin(),nums.end(),0LL);
    while(lo<hi){long long mid=(lo+hi)/2;canSplit(nums,m,mid)?hi=mid:lo=mid+1;}
    return lo;
}

Python

def splitArray(nums: list[int], m: int) -> int:
    def feasible(limit):
        groups, cur = 1, 0
        for n in nums:
            if cur + n > limit:
                groups += 1; cur = 0
            cur += n
        return groups <= m

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else: lo = mid + 1
    return lo

Complexity

Time: O(n log(sum))
Space: O(1)

DP Alternative: O(n²m)

dp[i][j] = min largest sum splitting first i elements into j groups.