410. Split Array Largest Sum(Solution || Leetcode hard || Java)

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)

SOLUTION:

class Solution {
public int splitArray(int[] nums, int k) {

//determining ranage for binary search
int start = 0;
int end = 0;

//as the minimum answer wee can get is the larget element from the array when value of k is equal to the length of array, and maximum answer we can obtain is the sum of total array when the value of k is 1
for(int i = 0; i < nums.length; i++){
start = Math.max(start,nums[i]);
end += nums[i];
}

//binary sarch
while(start < end){
int mid = start + (end — start)/2;
int pieces = 1;
int sum = 0;

for(int i = 0; i < nums.length; i++){
sum += nums[i];

if(sum > mid){
sum = nums[i];
pieces++;
}
}

if(pieces > k){
start = mid+1;
}
else{
end = mid;
}
}
return start;
}
}

Thank you for reading. If you have any queries then, please let me know in the comment section. I will surely be responsive toward it.