Last Updated: 5 Mar, 2021
Split Array Largest Sum
Hard
Asked in companies
You’re given an array 'arr' of size 'n' and an integer 'k'.
Your task is to split 'arr' into 'k' sub-arrays such that the maximum sum achieved from the 'k' subarrays formed must be the minimum possible.
A subarray is a contiguous part of the array.
Return the minimum possible value of the maximum sum obtained after splitting the array into 'k' partitions.
Example:
Input: ‘arr’ = [1, 1, 2] and ‘k’ = 2
Output: 2
Explanation: If we want to make two subarrays, there are two possibilities: [[1], [1, 2]] and [[1, 1], [2]]. We can see that the maximum sum of any subarray is minimized in the second case. Hence, the answer is 2, which is the maximum sum of any subarray in [[1, 1], [2]].
Input Format:
The first line contains two integers denoting 'n' and 'k', representing the number of array elements and the number of sub-arrays we need to split the array into.
The second line contains 'n' space-separated integers denoting the elements of the array.
Output Format:
Return the minimum possible value of the maximum sum obtained after splitting the array into 'k' partitions.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function and return the sum.
Constraints:
1 <= 'n' <= 10^4
1 <= 'k' <= N
1 <= 'arr[i]' <= 10^4
Time limit: 1 sec
Expected time complexity:
The expected time complexity is O(n * log(sum)), where 'n' is the number of elements in the array and 'sum' is the sum of elements of the array.
Approaches
In this approach, we will check all the possible ways of partitioning the given array into ‘k’ subarrays.
Algorithm:
- For this, we will make a recursive function splitArrayHelper(arr, index, partitions, 'currentMax') where ‘arr’ is the input array, the ‘index’ is the current index in the array, ‘partitions’ are the number of partition remaining to do, 'currentMax' is the current Maximum sum.
- The base condition will be when the current index becomes equal to the array’s size, which means we have traversed the whole array, then we’ll return 'currentMax'.
- At each call, we have to decide how long we want the current subarray to be. It can have a minimum size equal to 1, and the maximum size will be the index such that the remaining elements in the array are equal to ‘partitions’.
- While checking all the subarrays sizes that we can get by fixing the starting point of the subarray at the current index, if the sum of the elements of these sub-arrays is greater than the Maximum current sum, we will update the Current Maximum sum with this sum.
- At each call, for the current subarray, we will run a loop (loop variable ‘i’) from the current index till n - partitions - 1, and at each iteration, we’ll recursively call the function by updating the index to the i, updating the partitions to (partitions - 1) and also updating the current maximum sum as we discussed in point 4. We will find the minimum answer among all the subarrays starting at the current index and return that minimum answer.
If we get one valid value of sum, where the valid value of sum is that sum value which will not be exceeded by any of the ‘k’ subarray sums then, all other values that are greater than it will be valid as well, but we want only the minimum valid sum. Hence, an efficient way to find the minimum sum is to use a binary search.
Algorithm:
- The maximum sum can be equal to all the elements, while the minimum sum will be the largest element in the array.
- In binary search, for checking if the particular value is valid or not, we will divide the array into different subarrays such that the sum of elements of each subarray will not exceed this particular value. If the number of partitions is less than the ‘k’, then we can call this a valid arrangement; otherwise, it is not a valid value.
- If we get a valid value, then it means we have found one of the possible answers, but not sure if this answer is minimum or not. We will continue our search, but we update the search space’s endpoint with this value.
- If we don’t get a valid value, then we require a higher value, and it is not beneficial to search below this value. Hence, we will update the starting point of the search space with this value.
- When the starting point becomes equal to the endpoint, we have reached our answer and then return either the starting point or endpoint, which is equal to our answer.