Given an array nums of non-negative integers and an integer k, split nums into exactly k non-empty contiguous subarrays. Among all possible splits, minimise the largest subarray sum, and return that minimised largest sum.
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 10^6
- 1 <= k <= min(50, nums.length)
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every way to place k - 1 cuts is exponential, and the DP over (index, pieces) is O(k * n^2). The faster idea is to binary search on the answer. For a fixed limit, a greedy pass that starts a new piece only when the next number would push the sum above limit uses the fewest possible pieces. If that count is at most k, the limit is achievable (we can always split a piece further to reach exactly k, because pieces only need to be non-empty). Feasibility is monotonic in limit, so the smallest feasible limit is found in O(n log(sum)). It is the same pattern as Capacity To Ship Packages.
Algorithm
- Set
lo = max(nums)andhi = sum(nums). - While
lo < hi, takemidand greedily count the pieces needed so no piece exceedsmid. - If pieces
<= k,midis achievable:hi = mid. - Otherwise
midis too small:lo = mid + 1. - Return
lo.
O(n log S), where S = sum(nums)Space: O(1)k elements. This problem is also known as the Book Allocation or Painter's Partition problem in Indian placement rounds.class Solution: def splitArray(self, nums: List[int], k: int) -> int: def pieces_needed(limit): pieces, total = 1, 0 for x in nums: if total + x > limit: # start a new piece pieces += 1 total = 0 total += x return piecesΒ lo, hi = max(nums), sum(nums) while lo < hi: mid = (lo + hi) // 2 if pieces_needed(mid) <= k: hi = mid # achievable, try smaller else: lo = mid + 1 # too small return lo