Split Array Largest Sum

hard array binary search dp greedy

Problem

Partition nums into k non-empty contiguous subarrays so that the largest subarray sum is minimized. Return that minimum.

Inputnums = [7, 2, 5, 10, 8], k = 2

Output18

Split into [7,2,5] and [10,8]; largest sum 18 is smaller than any other split's largest.

nums (comma-separated)

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

function splitArray(nums, k) {
  const pieces = (cap) => {
    let p = 1, cur = 0;
    for (const x of nums) {
      if (cur + x > cap) { p++; cur = 0; }
      cur += x;
    }
    return p;
  };
  let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b,0);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (pieces(mid) <= k) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

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 mid = (lo + hi) >>> 1;
            if (pieces(nums, mid) <= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private int pieces(int[] a, int cap) {
        int p = 1, cur = 0;
        for (int x : a) {
            if (cur + x > cap) { p++; cur = 0; }
            cur += x;
        }
        return p;
    }
}

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        long lo = 0, hi = 0;
        for (int x : nums) { lo = max(lo, (long)x); hi += x; }
        auto pieces = [&](long cap) {
            long p = 1, cur = 0;
            for (int x : nums) {
                if (cur + x > cap) { p++; cur = 0; }
                cur += x;
            }
            return p;
        };
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (pieces(mid) <= k) hi = mid;
            else lo = mid + 1;
        }
        return (int)lo;
    }
};

Explanation

We want to split the array into k contiguous pieces so the largest piece-sum is as small as possible. Instead of trying every split, we binary search on the answer — the largest allowed sum itself.

The trick is to flip the question into a yes/no check: "if no piece may exceed cap, can we do it in at most k pieces?" A simple greedy answers this — walk through the numbers adding to the current piece, and start a new piece whenever adding the next number would exceed cap. The function pieces(cap) returns how many pieces that takes.

This check is monotonic: a bigger cap needs fewer or equal pieces. So we binary search cap in the range [max(nums), sum(nums)] — the smallest legal cap is the biggest single element, the largest is the whole sum. If pieces(mid) <= k the cap works, so we try smaller (hi = mid); otherwise we need a bigger cap (lo = mid + 1).

Example: nums = [7,2,5,10,8], k = 2. The search settles on 18: the greedy split with cap 18 produces [7,2,5] (sum 14) and [10,8] (sum 18), exactly 2 pieces, and no smaller cap fits in two.

Each greedy check is O(n) and the binary search runs log(sum) times, giving an efficient O(n log S) solution.

Time: O(n log S) where S = sum(nums) Space: O(1)