Split Array Largest Sum

Problem

Split a non-negative integer array into k non-empty contiguous subarrays. Return the smallest possible value of the largest subarray sum among the k pieces.

Constraints

• 1 ≤ nums.length ≤ 1000
• 0 ≤ nums[i] ≤ 10⁶
• 1 ≤ k ≤ min(50, n)

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def splitArray(self, nums, k):
        def need(cap):
            parts, cur = 1, 0
            for x in nums:
                if cur + x > cap:
                    parts += 1
                    cur = 0
                cur += x
            return parts
        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if need(mid) <= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

Java

class Solution {
    public int splitArray(int[] nums, int k) {
        int lo = 0, hi = 0;
        for (int x : nums) { lo = Math.max(lo, x); hi += x; }
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            int pieces = 1, cur = 0;
            for (int x : nums) {
                if (cur + x > m) { pieces++; cur = 0; }
                cur += x;
            }
            if (pieces <= k) hi = m;
            else             lo = m + 1;
        }
        return lo;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.