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.
A subarray is a contiguous part of the array.
Example 1:
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
Example 2:
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= k <= min(50, nums.length)
Intuition
Approach:
Try for a range of minSum
Here, we have to minimize the max_sum for various splits
1 2 3 4 5 Let k=2
1 | 2 3 4 5
1 2 | 3 4 5
1 2 3 | 4 5
1 2 3 4 | 5
Min split at 9
So, low = max_element , Because, if we take minimum of arr as low
Then, other will not be alloted, or added to sum
high = arr_sum
For each value,
Try to find ,
if k groups are possible
1 2 3 | 4 5
1-> 1 2 3
2-> 4 5
like that
Now if we took low as min
let 1 here
1-> 1
2-> --
so on
Not allocated to any array
Links
Video Links
Approach 1:
Instead we can also return low
C++
class Solution {
public:
int check_split(vector<int>& arr, int mid){
int sum = 0;
int count=1;
for(auto &it: arr){
if(sum + it <= mid)
sum += it;
else{
count++;
sum = it;
}
}
return count;
}
int splitArray(vector<int>& arr, int k) {
int low=*max_element(arr.begin(), arr.end());
int high=accumulate(arr.begin(), arr.end(), 0);
int ans;
while(low <= high){
int mid = low + (high-low)/2;
int sum = check_split(arr, mid);
if(sum > k){
low = mid+1;
}
else{
ans = mid;
high = mid-1;
}
}
return low;
}
};