Easy C++ binary search solution with explanation


  • 1
    I

    Since subarrays are non empty, and numbers are non-negative, result can be no less than max element in the array. It also can not be more than the sum of array elements. We now have min and max possible answers and can use binary search to get the exact result

        bool splits(vector<int>& nums, int m, long max_largest_sum)
        {
            long cur_subarray_sum = nums[0];
            int nsubarays = 1;
            for(int i = 1; i < nums.size(); ++i)
            {
                cur_subarray_sum += nums[i];
                if(cur_subarray_sum > max_largest_sum)
                {
                    ++nsubarays;
                    cur_subarray_sum = nums[i];
                }
            }
            if(nsubarays > m)
               return false;
            return true;
        }
        int splitArray(vector<int>& nums, int m) {
            int n = nums.size();
            long minres = nums[0], maxres = nums[0];
            for(int i = 1; i < n; ++i)
            {
                minres = max(minres,long(nums[i]));
                maxres += nums[i];
            }
            int res = 0;
            while(minres <= maxres)
            {
                long mid = (minres+maxres)/2;
                if(splits(nums,m,mid))
                {
                   maxres  = mid-1;
                   res = mid;
                }
                else
                   minres = mid+1;
            }
            return res;
        }
    

  • 0
    I
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.