(6) Binary Search: Split Array Largest Sum

Question Link and Solution Link

Difficulty: Hard

Problem Statement: Given an array of elements you need to split it into m subarrays such that the maximum sum of the subarray is minimized.

Approach: Let mid be the maximum sum a particular sub-array can have. Now we will include all elements such that total+nums[i] <= mid otherwise we will require another sub-array.

bool ok(vector<int> nums, int m, int mid)
{
    int sub_array = 0, total = 0, n = nums.size();
    for (int i = 0; i < n; i++)
    {
        if (nums[i] > mid)
            return false;
        else if (total + nums[i] <= mid)
            total += nums[i];
        else
        {
            sub_array++;
            total = nums[i];
        }
    }
    sub_array++;
    return (sub_array <= m);
}
int splitArray(vector<int> &nums, int m)
{
    int low = 0, high = 1e9 + 1, mid;
    while (low < high)
    {
        mid = low + (high - low) / 2;
        if (ok(nums, m, mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

Subscribe to the newsletter so that you never miss any post or update just like this one.

You can follow me on Hashnode for:

• Daily Data Structure and Algorithm based questions

• Getting knowledge of various development-related tools, concepts, and practices

  Twitter , GitHub , LinkedIn and Hashnode