Split Array Largest Sum

Intuition

The answer must be at least the biggest single element (that element has to fit inside some piece) and at most the total sum (one piece holding everything). For any candidate limit, a simple greedy pass tells us the fewest pieces needed to keep every piece sum at or below that limit. As the limit grows, the number of required pieces only shrinks, so feasibility is monotonic. That monotonic yes/no boundary is exactly what binary search exploits, letting us converge on the smallest limit that still fits in k pieces.

Algorithm walkthrough

1. 1Set lo to the maximum element and hi to the sum of all elements; the answer lives in [lo, hi].
2. 2Take mid = (lo + hi) / 2 as a candidate for the largest allowed piece sum.
3. 3Greedily walk the array, starting a new piece whenever adding the next element would exceed mid, and count how many pieces result.
4. 4If the count is at most k, mid is achievable, so move hi down to mid; otherwise raise lo to mid + 1.
5. 5When lo meets hi, that value is the minimized largest piece sum.

Implementation

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def canSplit(limit: int) -> bool:
            pieces, current = 1, 0
            for num in nums:
                if current + num > limit:
                    pieces += 1
                    current = num
                    if pieces > k:
                        return False
                else:
                    current += num
            return True

        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if canSplit(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo