Problem

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Examples

Example 1:

Input:
nums = [7,2,5,10,8], k = 2
Output:
 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Example 2:

Input:
nums = [1,2,3,4,5], k = 2
Output:
 9

Example 3:

Input:
nums = [1,4,4], k = 3
Output:
 4

Solution

Method 1 - Binary Search

Lets take eg. 1 to understand the problem. nums = [7,2,5,10,8], k = 2

Binary Search Setup

  1. Define the lower bound - The smallest possible value for the largest sum is the maximum value in the nums array (since each subarray must be non-empty and an individual element itself could be the largest). low = 10
  2. Define the upper bound - The largest possible value for the largest sum is the sum of all elements in the nums array (if we only had one subarray). high = 32

Binary Search Execution

  • Perform binary search between low and high.
  • Calculate the midpoint mid value.
  • Use the canSplit function to check if it is possible to split the array into k or fewer subarrays such that the sum of each subarray does not exceed mid.
  • Adjust low and high based on the result of canSplit.
nums = [7, 2, 5, 10, 8]
k = 2

low = max(nums) = 10
high = sum(nums) = 7 + 2 + 5 + 10 + 8 = 32
Iteration 1
low = 10, high = 32 => mid = (10 + 32) / 2 = 21
Can we split array with maxSum = 21

Initialize currentSuk = 0, subarrays = 1
- `7 + 2 + 5 = 14` (within 21)
- `10 + 8 = 18` (within 21)
- Total subarrays used: 2 (≤ k)

Since it is possible, update `high = mid - 1 = 20`
Iteration 2
low = 10, high = 20 => mid = (10 + 20) / 2 = 15
Can we split array with maxSum = 15

Initialize currentSuk = 0, subarrays = 1
- `7 + 2 + 5 = 14` (within 15)
- `10` (within 15)
- `8` (within 15)
- Total subarrays used: 3 (> k)

Since it is not possible, update `low = mid + 1 = 16`
Iteration 3
low = 16, high = 20 => mid = (16 + 20) / 2 = 18
Can we split array with maxSum = 18

Initialize currentSuk = 0, subarrays = 1
- `7 + 2 + 5 = 14` (within 18)
- `10 8` (within 18)
- Total subarrays used: 2 (≤ k)

Since it is possible, update `high = mid - 1 = 17`
Iteration 4
low = 15, high = 17 => mid = (15 + 17) / 2 = 16
Can we split array with maxSum = 18

Initialize currentSuk = 0, subarrays = 1
- `7 + 2 + 5 = 14` (within 16)
- `10` (within 16)
- `8` (within 211616
- Total subarrays used: 3 (> k)

Since it is not possible, update `low = mid + 1 = 17`
Iteration 5
low = 17, high = 17 => mid = (17 + 17) / 2 = 17
Can we split array with maxSum = 17

Initialize currentSuk = 0, subarrays = 1
- `7 + 2 + 5 = 14` (within 17)
- `10` (within 17)
- `8` (within 17)
- Total subarrays used: 3 (> k)

Since it is not possible, update `low = mid + 1 = 18`
Final Result

Since now low > high, we return low.

Code

Java
class Solution {

	public int splitArray(int[] nums, int k) {
		int low = 0, high = 0; // using long for sum
		for (int num: nums) {
			low = Math.max(num, low);
			high += num;
		}

		if (k == 1) {
			return high;
		}

		int ans = 0;

		while (low <= high) {
			int mid = (low + high) / 2;

			if (canSplit(nums, k, mid)) {
				ans = mid;
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}

		return ans;
	}

	private boolean canSplit(int[] nums, int k, int maxSum) {
		int currentSum = 0;
		int subarrays = 1; // Start with one subarray
		for (int num: nums) {
			// If adding this element to the current subarray exceeds maxSum
			// then start a new subarray
			if (currentSum + num > maxSum) {
				subarrays++;
				currentSum = num; // Start new subarray with the current number
				if (subarrays > k) {
					return false; // More subarrays than allowed
				}
			} else {
				currentSum += num;
			}
		}

		return true;
	}
}

Complexity

  • ⏰ Time complexity: O(log S * n), where S is the sum of all elements in nums and n is the number of elements in nums
    • The binary search runs in O(log S) iterations.
    • Each iteration of binary search involves checking if it is possible to split the array, which takes O(n) time.
  • 🧺 Space complexity: O(1)