# (6) Binary Search: Split Array Largest Sum

[Question Link](https://leetcode.com/problems/split-array-largest-sum/)  and  [Solution Link](https://leetcode.com/submissions/detail/614336956/) 

**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](https://twitter.com/_Arsalaan_) ,  [GitHub](https://github.com/arsalanhub) ,  [LinkedIn](https://www.linkedin.com/in/mohammadarsalan/)  and  [Hashnode](https://hashnode.com/@mohdarsalan)