Split Array Largest Sum

Hard
0/120
Average time to solve is 15m
profile
Contributed by
36 upvotes
Asked in companies
AmazonTekion CorpTrilogy Innovations

Problem statement

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]].


Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3 2
1 1 2
Sample Output 1:
2
Explanation of Sample Input 1:

Alt text

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]].
Sample Input 2:
4 3
1 2 3 4
Sample Output 2:
4
Explanation of Sample Input 2:

Alt text

If we want to make three subarrays, there are three possibilities: [[1], [2], [3, 4]], [[1], [2, 3], [4]], and [[1, 2], [3], [4]]. We can see that the maximum sum of any subarray is minimized in the third case. Hence, the answer is 4, which is the maximum sum of any subarray in [[1, 2], [3], [4]].
Hint

Check all possible ways of partitioning the given array into ‘k’ subarrays.

Approaches (2)
Brute-Force

In this approach, we will check all the possible ways of partitioning the given array into ‘k’ subarrays. 

 

Algorithm:

  1. 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.
  2. 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'.
  3. 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’.
  4. 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.
  5. 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.
Time Complexity

O((n - 1) C (k - 1)), where ‘n’ is the number of elements in the array, ‘k’ is the number of sub-arrays such that the maximum sum achieved from the ‘k’ subarrays formed must be the minimum possible and C is the binomial coefficient.

 

Since there are (n - 1) C (k - 1) ways to divide the given array into ‘k’ subarrays, hence the final time complexity will be O((n - 1) C (k - 1)).

Space Complexity

O(n), where ‘n’ is the number of elements in the array.

 

In the worst case, there can be at most ‘n’ elements in the recursive stack. Hence the final space complexity will be O(n).

Code Solution
(100% EXP penalty)
Split Array Largest Sum
Full screen
Console