Split Array Largest Sum

Hard
832.

Split Array Largest Sum

Split Array Largest Sum is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Split Array Largest Sum — Solution in Python, Java & C++

Split Array Largest Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Split Array Largest Sum is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Microsoft interviews.

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

Hints for Split Array Largest Sum

  1. Hint 1

    If a cap on the largest sum is achievable with k parts, any larger cap is too — the feasibility is monotone.

  2. Hint 2

    For a candidate cap, greedily extend each part until the next element would overflow it.

  3. Hint 3

    The search range runs from the largest element to the total sum.

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

  1. Set lo to max(nums) — no part can be smaller than its largest element — and hi to the total.
  2. need(cap): sweep once, starting a new part whenever the next element would push the running sum past cap.
  3. 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

Java

private static int partsNeeded(int[] nums, int cap) {
    int cnt = 1, cur = 0;
    for (int x : nums) {
        if (cur + x > cap) {
            cnt++;
            cur = 0;
        }
        cur += x;
    }
    return cnt;
}

public static int splitArray(int[] nums, int k) {
    int lo = 0;
    long hi = 0;
    for (int x : nums) {
        lo = Math.max(lo, x);
        hi += x;
    }
    int right = (int) hi;
    while (lo < right) {
        int mid = lo + (right - lo) / 2;
        if (partsNeeded(nums, mid) <= k) right = mid; else lo = mid + 1;
    }
    return lo;
}

C++

static int partsNeeded(vector<int>& nums, int cap) {
    int cnt = 1, cur = 0;
    for (int x : nums) {
        if (cur + x > cap) {
            cnt++;
            cur = 0;
        }
        cur += x;
    }
    return cnt;
}

int splitArray(vector<int>& nums, int k) {
    int lo = 0;
    long long total = 0;
    for (int x : nums) {
        lo = max(lo, x);
        total += x;
    }
    int hi = (int) total;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (partsNeeded(nums, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming