Searching: Given an array, split into n arrays to minimize the maximum sum of all sub arrays

Problem Statement:

You are given an array and value k.

You need to split the array in to k sub arrays such that, maximum subarray sum is achieved out of k subarrays.

Example:

Input: arr = [1, 1, 2] k =2.

Output: 2

You can divide into [1, 1] [2]. So the max sum of all the sub array is 2 and is minimum.

Solution 1: Binary search

We will use binary search to solve the problem.

We will assign low as the min value of the array.

high as the total sum of the array,

Calculate the mid and call one more function (named feasible) to check if its feasible to split the array into k sub arrays with the mid.

feasible function:

It will iterate through the array while maintaining the current sum.

Then while adding an element will increase the sum to mid, then create a new sub array.

Then check accordingly and return false or true.

Time Complexity: O(n * log(sum))
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <numeric>

using namespace std;

bool feasible(vector<int>& arr, int k,int mid,int n)
{
    int cnt=1;
    int sum=0;

    for(int i=0;i<n;i++)
    {
        if (arr[i] > mid) 
        {
            return false; 
        }
        if(arr[i]+sum>mid)
        {
            cnt++;
            sum=arr[i];
        }
        else
        {
            sum+=arr[i];
        }
    }
    return cnt <= k;
}


int solution(vector<int>& arr, int k) 
{
    int n = arr.size();

    int low = min(arr[0],arr[n-1]);
    int high = accumulate(arr.begin(),arr.end(),0);

    while(low <= high)
    {
        int mid = (low+high)/2;
        if(feasible(arr,k,mid,n) == true)
        {
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    return low;
}

int main() 
{

    vector<int> arr = {1, 1, 2};
    int k = 2;
    cout << solution(arr, k);
}

Output

2