Coding Interview PatternsSplit Array Largest Sum
HardModified Binary Search
Split Array Largest Sum
Explanation & Solution
Description
Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.
Return the minimized largest sum of the split.
Input:nums = [7, 2, 5, 10, 8], k = 2
0
7
1
2
2
5
3
10
4
8
Output: 18
Explanation: The best split is [7, 2, 5] and [10, 8], where the largest sum is 18.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= k <= min(50, nums.length)
Approach
Modified Binary Search pattern
1. Define the Search Space
- Minimum possible answer:
max(nums)— each subarray must contain at least one element. - Maximum possible answer:
sum(nums)— everything in one subarray.
2. Binary Search on the Answer
- For candidate max sum
mid, greedily count how many subarrays are needed: keep adding elements to the current subarray until it would exceedmid, then start a new subarray.
3. Feasibility Check
- If the number of subarrays needed
<= k, the candidate works → try smaller:hi = mid. - Otherwise, need more splits than allowed:
lo = mid + 1.
4. Return the Answer
- When
lo === hi, return the minimized largest sum.
🧠 Key Insight
- The greedy feasibility check works because if a max sum of
midrequires at mostksubarrays, any value larger thanmidalso works. This monotonic property enables binary search.
Time
O(n · log(sum - max)).Space
O(1).Visualization
Input:
[7, 2, 5, 10, 8], k = 2
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
27 steps