410 Split Array Largest Sum

Techniques Used

• Binary Search

Difficulty Level

• Hard
• Non-Intuitive

Approach

• Find the range of Largest subArray sum possible.
  • Lower limit will be equal to the value of the largest element of the array.
  • Upper limit will be equal to the sum of all elements in the array
• Now, perform a binary search on the subArray Sums possible.
  • For every middle sum = (lower + higher)/2;
    • we find whether it is possible to have such a division of array that it gets divided into <= m parts with largest subarray sum being lesser than limit provided.
      • If possible, then we make the high limit as mid - 1 in order to minimize the largestSum possible.
      • If not, then we make the low limit as mid + 1, and look for to accomodate the possibility of dividing the array into m parts.
    • This limit will change based on the current sum that we are at in the binarysearch step.
• Return the low limit. This will indicate the minimized largestSum possible when we divide array into m parts.

Time Complexity

• Time Complexity: Nlog(S) - > S is the sum of input array
• Space Complexity: O(1)

Code: C++

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {

        int low = 0, high = 0;

        for(int i: nums){
            low = max(low, i);
            high += i;
        }

        while(low <= high){

            int mid = low + (high - low)/2;

            if(isPossible(nums, m, mid)){

                high = mid - 1;


            } else{

                low = mid + 1;

            }

        }

        return low;

    }

    int isPossible(vector<int> &nums, int m, int limit){

        int subArray = 1, sumOfCurrSubArray = 0;

        for(int i = 0; i < nums.size(); i++){

            sumOfCurrSubArray += nums[i];

            if(sumOfCurrSubArray > limit){
                sumOfCurrSubArray = nums[i];
                subArray++;

                if(subArray > m){
                    return false;
                }
            }

        }

        return true;
    }
};

Code: Java

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

        int low = 0, high = 0;

        for(int i:nums){
            low = Math.max(low,i);
            high += i;
        }

        while(low <= high){

            int mid = low + (high-low)/2;

            if(isPossible(nums,m,mid)){
                high = mid-1;
            } else{
                low = mid + 1;
            }    
        }

        return low;
    }


    boolean isPossible(int[] nums,int m,int limit){

        int subArray = 1, sumOfCurrSubArray = 0;

        for(int i = 0; i < nums.length; i++){
            sumOfCurrSubArray += nums[i];
            if(sumOfCurrSubArray > limit){
                subArray++;
                sumOfCurrSubArray = nums[i];

                if(subArray > m){
                    return false;
                }
            }
        }

        return true;
    }


}