410. Split Array Largest Sum

Problem Statement

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

https://leetcode.com/problems/split-array-largest-sum/description/

Video Links

https://www.youtube.com/watch?v=thUd_WJn6wk&ab_channel=takeUforward

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;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems