Split Array Largest Sum
Asked at Google, Amazon, Uber
Problem
Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays. The largest sum of these subarrays is minimized. Return the largest sum of the split. This is a classic "minimize the maximum" binary search problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Amazon | Hard | View all Amazon questions → |
| Uber | Hard | View all Uber questions → |
How to Think About It
Brute force: try all possible ways to split the array into k subarrays. There are C(n-1, k-1) ways, which is exponential. Not feasible.
DP approach: dp[i][j] = minimum largest sum when splitting nums[0..i-1] into j subarrays. Transition: dp[i][j] = min over all valid p of max(dp[p][j-1], sum(p+1..i)). Time: O(n^2 * k). Works for small n but too slow for large inputs.
Binary search on the answer: the answer (minimum largest sum) is between max(nums) (each element in its own subarray) and sum(nums) (all elements in one subarray). Binary search this range. For each candidate sum, check if we can split into <= k subarrays where each subarray sum <= candidate.
Greedy check function: given a max sum limit, iterate through the array, greedily forming subarrays. Start a new subarray when adding the next element would exceed the limit. Count the number of subarrays needed. If count <= k, the candidate works (try smaller). If count > k, the candidate is too small (try larger).
Visual walkthrough for nums = [7, 2, 5, 10, 8], k = 2:
Binary search: lo=10 (max element), hi=32 (sum).
mid=21: [7,2,5]=14<=21, next 10, 14+10=24>21, start new: [10]=10, 10+8=18<=21. 2 subarrays. Works. hi=21.
mid=15: [7,2,5]=14<=15, next 10, 14+10=24>15, start new: [10]=10, 10+8=18>15, start new: [8]=8. 3 > 2. lo=16.
mid=18: [7,2,5]=14<=18, next 10, 14+10=24>18, start new: [10]=10, 10+8=18<=18. 2 <= 2. Works. hi=18.
mid=17: [7,2,5]=14<=17, next 10, 14+10=24>17, start new: [10]=10, 10+8=18>17, start new: [8]=8. 3 > 2. lo=18.
lo=hi=18. Answer: 18.
Time: O(n * log(sum - max)). Space: O(1) for the greedy check.
Optimal Approach
Binary search on the answer. Set lo = max(nums), hi = sum(nums). While lo < hi: compute mid = (lo + hi) // 2. Greedy check: can we split into <= k subarrays with each sum <= mid? If yes, hi = mid (try smaller). If no, lo = mid + 1 (need larger). Return lo.
Greedy check: iterate through nums, maintain current subarray sum. If adding the next element exceeds mid, start a new subarray. Count subarrays.
Walkthrough: nums = [7, 2, 5, 10, 8], k = 2.
lo=10, hi=32, mid=21. Greedy: [7,2,5]=14, [10,8]=18. 2 <= 2.hi=21.lo=10, hi=21, mid=15. Greedy: [7,2,5]=14, [10]=10, [8]=8. 3 > 2.lo=16.lo=16, hi=21, mid=18. Greedy: [7,2,5]=14, [10,8]=18. 2 <= 2.hi=18.lo=16, hi=18, mid=17. Greedy: [7,2,5]=14, [10]=10, [8]=8. 3 > 2.lo=18.lo=hi=18. Return 18.
Time: O(n * log(sum)). Space: O(1).
What Trips People Up in Real Interviews
Setting the binary search bounds incorrectly. lo must be max(nums) (not 0 or 1) because each subarray must contain at least one element. hi must be sum(nums) (not infinity) because the worst case is one subarray containing everything.
Off-by-one in the greedy check: starting a new subarray when current + num >= maxSum instead of > maxSum. If the current subarray sum equals the limit, it is valid. Only exceed the limit triggers a new subarray.
Confusing "minimize the largest sum" with "minimize the number of subarrays." The problem asks to minimize the maximum subarray sum given exactly k subarrays. The binary search approach finds the minimum feasible maximum.
Using int for the sum in C++/Java. The sum of the array can exceed Integer.MAX_VALUE for large arrays. Use long for the binary search bounds and the running sum in the greedy check.
Not verifying the greedy check correctly. After the loop, the count of subarrays must be <= k. If you forget to count the last subarray (it is counted at the start when count = 1), the check will be off by one.
Solution Code
def splitArray(nums, k):
def canSplit(maxSum):
count, current = 1, 0
for num in nums:
if current + num > maxSum:
count += 1
current = num
else:
current += num
return count <= k
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
if canSplit(mid):
hi = mid
else:
lo = mid + 1
return loFrequently Asked Questions
What is the Split Array Largest Sum problem?
Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays. The largest sum of these subarrays is minimized. Return the largest sum of the split. This is a classic "minimize the maximum" binary search problem.
How do you solve Split Array Largest Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Split Array Largest Sum?
Split Array Largest Sum is asked at Google, Amazon, Uber. It is a hard difficulty problem.
What are common mistakes on Split Array Largest Sum?
- Setting the binary search bounds incorrectly. `lo` must be `max(nums)` (not 0 or 1) because each subarray must contain at least one element. `hi` must be `sum(nums)` (not infinity) because the worst case is one subarray containing everything.
- Off-by-one in the greedy check: starting a new subarray when `current + num >= maxSum` instead of `> maxSum`. If the current subarray sum equals the limit, it is valid. Only exceed the limit triggers a new subarray.
- Confusing "minimize the largest sum" with "minimize the number of subarrays." The problem asks to minimize the maximum subarray sum given exactly k subarrays. The binary search approach finds the minimum feasible maximum.
- Using `int` for the sum in C++/Java. The sum of the array can exceed `Integer.MAX_VALUE` for large arrays. Use `long` for the binary search bounds and the running sum in the greedy check.
- Not verifying the greedy check correctly. After the loop, the count of subarrays must be <= k. If you forget to count the last subarray (it is counted at the start when `count = 1`), the check will be off by one.