Split Array Largest Sum
The key idea
Don't search for the split — search for the answer. The largest subarray sum is a number between
max(nums) (no piece can be smaller than its biggest element) and sum(nums) (one piece holds everything). For a candidate cap mid, a greedy left-to-right pass tells you the fewest pieces whose sums all stay <= mid. That piece count only goes DOWN as mid grows, so the smallest feasible cap is found by binary search on mid.Problem
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that each element belongs to exactly one subarray, and each subarray is a contiguous slice of nums.
Let the largest sum of any subarray be the maximum, over the k subarrays, of the sum of that subarray's elements.
Return the minimized largest sum of the split. In other words, choose the split that makes the largest subarray sum as small as possible.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= k <= min(50, nums.length)
Examples
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Input: nums = [1,4,4], k = 3
Output: 4
Complexity
Time: O(n * log(sum)) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD