Back to Problem
Official 455 views

Editorial: Split Array Largest Sum

by admin ·

27

1 Intuition

Binary search on the answer: is it possible with largest sum ≤ X?

2 Approach

For a candidate X, greedily cut whenever the running sum would exceed X and count parts. Fewer parts than k is fine (you can always split further).

3 Complexity Analysis

Time O(n log(sum)), Space O(1).

4 Solution Code 

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def parts(limit):
            count, cur = 1, 0
            for x in nums:
                if cur + x > limit:
                    count += 1
                    cur = 0
                cur += x
            return count
        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if parts(mid) <= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

5 Code Walkthrough

The reference solution below implements the approach step by step.