Largest Subarray Sum Minimized

Hard
0/120
Average time to solve is 30m
profile
Contributed by
108 upvotes

Problem statement

Given an integer array ‘A’ of size ‘N’ and an integer ‘K'.


Split the array ‘A’ into ‘K’ non-empty subarrays such that the largest sum of any subarray is minimized.


Your task is to return the minimized largest sum of the split.


A subarray is a contiguous part of the array.


Example: 
Input: ‘N’ = 5, ‘A’ = [1, 2, 3, 4, 5], ‘K’ = 3

Output: 6

Explanation: There are many ways to split the array ‘A’ into K consecutive subarrays. The best way to do this is to split the array ‘A’ into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.


Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains one integer, ‘N’, denoting the size of the array ‘A’.

The second line contains ‘N’ integers denoting the elements of the array ‘A’.

The third line contains one integer, ‘K’, denoting the number in which array ‘A’ should be split.


Output format: 
Return the minimized largest sum of the split.


Note:- 
You don't need to print anything. Just implement the given function.
Sample Input 1:
5
1 2 3 4 5
3


Sample Output 1:
6


Explanation Of Sample Input 1:
Input: ‘N’ = 5, ‘A’ = [1, 2, 3, 4, 5], ‘K’ = 3

Output: 6

Explanation: There are many ways to split the array ‘A’ into K consecutive subarrays. 

The best way to do this is to split the array ‘A’ into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.


Sample Input 2:
3
3 5 1
3


Sample Output 2:
5


Explanation Of Sample Input 2:


Input: ‘N’ = 3, ‘A’ = [3, 5, 1], ‘K’ = 3

Output: 5

Explanation: There is only one way to split the array ‘A’ into 3 subarrays, i.e., [3], [5], and [1]. The largest sum among these subarrays is 5.


Sample Input 3:
6
10 4 5 10 9 10 
4


Sample Output 3:
15


Constraints:
1 <= N <= 1e4
1 <= A[i] <= 1e5
1 <= K <= N

Time Limit: 1-sec
Hint

Apply Binary Search on the maximum sum which we want to be minimized.

Approaches (1)
Binary Search

We will use Binary Search here. Binary Search will minimize the maximized sum we can get from the array ‘A’ after breaking it into ‘K’ consecutive subarrays. 

We will keep two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively. When applying the binary search algorithm, suppose we find the ‘mid’ as ‘(s + e) / 2’. Now, We will determine whether it is possible to array ‘A’ into subarrays such that the sum of each subarray is less than or equal to ‘mid’. Suppose, satisfying this condition, the number of subarrays that will be generated is equal to ‘num’. If ‘num’ is equal to ‘K’, then the answer will be ‘mid’, and to get a smaller answer, we will do ‘e’ = ‘mid - 1’. If ‘num’ is less than ‘K’, we have to increase the number of subarrays that will be generated, so for that, we will do ‘e’ = mid - 1. 

Otherwise, We would do ‘s’ = mid + 1, which means ‘num’ is greater than ‘K’, so to decrease the number of subarrays that will be generated, we would increase s, or ‘s’ = mid + 1.
 

The steps are as follows:-

 

// Function to check whether we can split the array into subarrays with maximum sum ‘mid’

function isValid(int[] a, int k, int mid):

  1. Initialize a variable ‘sum’ and assign it to ‘0’.
  2. Initialize a variable ‘cnt’ ans assign it to ‘0’.
  3. Iterate over the array ‘a’ using a variable ‘i’:
    • Initialize a variable ‘cur’ and assign it to the current array element ‘a’.
    • If cur > mid:
      • Return false.
    • If sum + a[i] > mid:
      • Increment ‘cnt’ by 1.
      • Initialize ‘sum’ by ‘cur’.
      • If cnt >= m:
        • Return false.
    • Else:
      • Add ‘cur’ to ‘sum’.
  4. Return true.


// Function to find the minimized largest sum of the split.

function largestSubarraySumMinimized(int n, int[] a, int k):

  1. Int n is the number of elements in the array ‘a’.
  2. Declare two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively.
  3. Initialize a variable ‘ans’, which will store our final answer.
  4. While s <= e:
    • Initialize a variable ‘mid’ and assign it to ‘(s + e) / 2’.
    • Initialize a variable ‘ok’ and assign it to isValid(a, k, mid).
    • If ok == true:
      • Assign ‘mid’ to ‘ans’.
      • Assign ‘e’ to ‘mid - 1’.
    • Else:
      • Assign ‘s’ to ‘mid + 1’.
  5. Return ‘ans’.
Time Complexity

O( N * logM ), where N is the number of elements, and M is the integer(1e9).

 

We are traversing over the array ‘A’ at most logM times.

 

Hence the time complexity is O( N * logM ).

Space Complexity

O( 1 ).

 

We store our answers and other things in 2-3 variables.

 

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Largest Subarray Sum Minimized
Full screen
Console