Split Array

Moderate
0/80
profile
Contributed by
15 upvotes
Asked in companies
SprinklrAdobeSalesforce

Problem statement

You are given an array ‘ARR’ of size ‘N’ and an integer ‘M’. You have to split the array into ‘M’ non-overlapping, non-empty subarrays such that the maximum of all the subarray’s sum is the minimum possible. Your task is to return the minimum of the maximum of all the subarray’s sum.

For example: 
You are given ‘ARR’ = [7, 2, 6, 10, 8] and ‘M’ = 2. We split the array as [ 7, 2, 6] and [10, 8], the maximum of 7 + 2 + 6  and 10 + 8 is 18, which is the minimum possible.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the size of ‘ARR’ and the given integer.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format: 
For each test case, print a single integer representing the minimum of the maximum of all the subarray’s sum.

Print a separate line for each test case.
Constraints 
1 <= T <= 10
1 <= N <= 10^5
1 <= M <= 100
0 <= ARR[i] <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
5 2
7 2 6 10 8
3 3
1 4 4
Sample Output 1:
18
4
Explanation:
For the first test case, ‘ARR’= [7, 2, 6, 10,8] and M=’2’ when we split the array as [ 7, 2, 6] and [10, 8], the maximum of 7 + 2 + 6  and 10 + 8, is 18, which is the minimum possible.

For the first test case, ‘ARR’= [1, 4, 4] and M = 3 when we split the array as [1], [4], and [4], the maximum of 1, 4  and 4, is 4, which is the minimum possible.
Sample Input 2:
2
5 2
1 2 3 4 5
2 2
1 2
Sample Output 2:
 9
 2
Hint

Try the recursive approach.

Approaches (3)
Recursion

In this approach, we will create a recursive function; at each step, we will try to split the array at every position available position, then we will take the sum of the left half of the split and call the recursive function on the right half of the array. We will create a function recursiveSplit(arrRem, currentM), where arrRem is the current array, and currentM is the remaining subarrays to be formed.
 

Algorithm:

  • In the function recursiveSplit(arrRem, currentM)
    • If length of arrRem is 0, return 0
    • If currentM is 1 return sum of arrRem
    • Set minResult as infinity
    • Iterate j from 1 to length of arrRem
      • Set leftSum as the sum of elements of arrRem from index 0 to j - 1
      • Call the recursiveSplit function on the array of elements with index from j in arrRem and currentM - 1 and set it as rightSum
      • rightSum as recursiveSplit(arrRem[j: ], currentM - 1)
      • Update minResult as minimum of minResult and sum of leftSum and rightSum
    • Return minResult
  • Return recursiveSplit(arr, m)
Time Complexity

O(N^M), Where N and M are the sizes of the array and the given integer.
 

We are iterating through every possible split of the array, and for each split, we are calculating the sum of the left half, which will cost O(N). We are repeating the process until M is 0. Hence the overall time complexity is O(N^M).

Space Complexity

O(M), Where M is the integer given.

 

The space complexity of the recursive stack will take O(M) space. Hence the overall space complexity is O(M).

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