56. Split Array Largest Sum

Topic :

binary search

Difficulty :

hard

Problem Link :

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)

solution

import java.io.*;
import java.util.*; 
class Split_Array_Largest_Sum
{
    public static void main (String args[]){
      int nums[]={7,2,5,10,8}; 
      int m=2;
      
      System.out.println(splitArray(nums,m));
    }
     static int splitArray(int[] nums, int m) {
        
     int minElement=Integer.MIN_VALUE;
     int sum=0;
     
     for(int ele:nums){
        minElement=Math.min(minElement,ele);
        sum+=ele;
     }   
        
        int low=minElement; 
        int high=sum;
        int minimalLargestSum=Integer.MAX_VALUE;
       
        while(low<=high){
            int mid=(high+low)/2;
            
            if(isPossible(nums,mid,m)){
                minimalLargestSum=mid;
                high=mid-1;
            }
            else
                low=mid+1;
            
        }
        
        return minimalLargestSum;
    }
    
    static boolean isPossible(int[] nums, int currSum,int m){
        int sum=0; int subArrays=1; 
        
        for(int i=0;i<nums.length;i++){
         
            if(nums[i]>currSum)
                return false;
          
            if(sum+nums[i]>currSum){
                subArrays++;
                sum=nums[i];
                
                if(subArrays>m)
                    return false;
            }
            else{
                sum+=nums[i];
            }
        }       
         return true;
    }
}