Published: Jul 22, 2022

## Problem Description

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

## Examples

```
example 1:
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: splitted array: [[7,2,5],[10,8]], sums: [14, 18]
18 is the minimized largest sum when the array is splitted into 2 groups
```

```
example 2:
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: splitted array: [[1,2,3],[4,5]], sums: [6, 9]
9 is the minimized largest sum when the array is splitted into 2 groups
```

```
example 3:
Input: nums = [1,4,4], k = 3
Output: 4
Explanation: splitted array: [[1],[4],[4]], sums: [1,4,4]
4 is the minimized largest sum when the array is splitted into 3 groups
```

## How to Solve

Some algorithm questions ask this sort – minimize the maximum. In general, problems give an array and a value or values which will be a clue to split the array. The key to solve this type is to figure out what is the criteria to split. The patterns are similar, but we see many variations.

Well, how to solve this kind? At a glance, it looks like a dynamic programming problem. Using memoization, bottom-up manner would lead to an answer. However, surprisingly, the binary search approach works very well.

To solve this problem, the given array should be divided into groups based on a certain criteria. In this case, the criteria is the subarray sum. It lies between the largest value in the array (left) and total sum of the array (right). The iteration starts off from the middle of those left and right values. Based on the middle value, the array will be split comparing the sum so far and the middle value. In the end, some number of subarrays will be created.

Next step is to adjust the left or right values. If the number of subarrays is less than the specified value, the middle value should be smaller to create more subarrays. If the number of subarrays is greater than the specified value, the middle value should be greater to create less subarrays. This way, we will get the answer.

## Solution

```
#include <numeric>
#include <vector>
using namespace std;
class SplitArrayLargestSum {
private:
bool check(vector<int> &nums, int k, int mid) {
int count = 1, cur = 0;
for (int v : nums) {
if (cur + v <= mid) {
cur += v;
} else {
count++;
cur = v;
}
}
return count <= k;
}
public:
int splitArray(vector<int>& nums, int k) {
int left = *max_element(nums.begin(), nums.end());
int right = accumulate(nums.begin(), nums.end(), 0);
while (left <= right) {
int mid = (left + right) / 2;
if (check(nums, k, mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
};
```

```
import java.util.Arrays;
public class SplitArrayLargestSum {
private boolean check(int[] nums, int k, int mid) {
int count = 1, cur = 0;
for (int v : nums) {
if (cur + v <= mid) {
cur += v;
} else {
count++;
cur = v;
}
}
return count <= k;
}
public int splitArray(int[] nums, int k) {
int left = Arrays.stream(nums).max().getAsInt();
int right = Arrays.stream(nums).sum();
while (left <= right) {
int mid = (left + right) / 2;
if (check(nums, k, mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
```

```
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var splitArray = function(nums, k) {
const check = (mid) => {
let count = 1, cur = 0;
for (let v of nums) {
if (cur + v <= mid) {
cur += v;
} else {
count += 1;
cur = v;
}
}
return count <= k;
}
let left = Math.max(...nums);
let right = nums.reduce((acc, v) => acc + v, 0);
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (check(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
};
```

```
from typing import List
class SplitArrayLargestSum:
def splitArray(self, nums: List[int], k: int) -> int:
def check(mid):
count, cur = 1, 0
for v in nums:
if cur + v <= mid:
cur += v
else:
count += 1
cur = v
return count <= k
left, right = max(nums), sum(nums)
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left
```

```
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def split_array(nums, k)
check = lambda do |mid|
count, cur = 1, 0
nums.each do |v|
if cur + v <= mid
cur += v
else
count += 1
cur = v
end
end
count <= k
end
left, right = nums.max, nums.sum
while left <= right
mid = (left + right) / 2
if check.call(mid)
right = mid - 1
else
left = mid + 1
end
end
left
end
```

## Complexities

- Time: O(n log(s)) – s: sum of elements in the array
- Space: O(1)