Split Array Largest Sum — Hard Problem & Solution

Split nums into k non-empty contiguous subarrays so that the largest subarray sum is as small as possible. Return that minimised largest sum.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Greedy, Binary Search
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Split nums into k non-empty contiguous subarrays so that the largest subarray sum is as small as possible.

Return that minimised largest sum.

Example 1

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: [7,2,5] and [10,8] give sums 14 and 18.

Example 2

Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: [1,2,3] and [4,5].

Example 3

Input: nums = [1,4,4], k = 3
Output: 4

Constraints

1 <= nums.length <= 1000
0 <= nums[i] <= 1000000
1 <= k <= nums.length

How to solve Split Array Largest Sum

Binary search the answer. For a candidate cap, the greedy that keeps extending a part until it would overflow produces the fewest parts possible, so comparing that count with k decides feasibility exactly.

Approach

Set lo to max(nums) — no part can be smaller than its largest element — and hi to the total.
need(cap): sweep once, starting a new part whenever the next element would push the running sum past cap.
Binary search the smallest cap with need(cap) <= k.

Why it works

The greedy is optimal for a fixed cap: closing a part before it must can never reduce the number of parts, since the deferred element still has to go somewhere later. Raising the cap lets each part hold more, so need is non-increasing. And using fewer than k parts is fine — a part can always be split further without raising the maximum.

Complexity

Time — O(n log S) where S is the total sum
Space — O(1)

Pitfalls

The classic O(n² k) dynamic program also solves it but is far slower here.
lo must start at max(nums), or the greedy can loop on an element that fits in no part.
need(cap) <= k, not == k — extra splits are always available.

Reference solution

Python

from typing import List

def splitArray(nums: List[int], k: int) -> int:
    lo, hi = max(nums), sum(nums)

    def need(cap: int) -> int:
        cnt, cur = 1, 0
        for x in nums:
            if cur + x > cap:
                cnt += 1
                cur = 0
            cur += x
        return cnt

    while lo < hi:
        mid = (lo + hi) // 2
        if need(mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var splitArray = function(nums, k) {
    var lo = 0, hi = 0, i;
    for (i = 0; i < nums.length; i++) {
        if (nums[i] > lo) lo = nums[i];
        hi += nums[i];
    }
    var need = function(cap) {
        var cnt = 1, cur = 0;
        for (var j = 0; j < nums.length; j++) {
            if (cur + nums[j] > cap) { cnt++; cur = 0; }
            cur += nums[j];
        }
        return cnt;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (need(mid) <= k) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue