Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum among the subarrays is minimized.
Return the minimized largest sum of the split.
This problem demonstrates the powerful "Binary Search on Answer" technique, where instead of searching through the input, we search through the space of possible answers using a monotonic predicate.
Example 1:
Input:
nums = [7, 2, 5, 10, 8], k = 2
Output: 18
Explanation: Split into [7, 2, 5] (sum=14) and [10, 8] (sum=18). The largest sum is 18, which is the minimum possible.
Example 2:
Input:
nums = [1, 2, 3, 4, 5], k = 2
Output: 9
Explanation: Split into [1, 2, 3] (sum=6) and [4, 5] (sum=9). The largest sum is 9.
Understanding the Problem
We have an array of positive integers and need to split it into exactly k contiguous subarrays. Among all possible ways to split, we want to find the one where the maximum subarray sum is as small as possible.
Think of it like distributing work among k workers, where each worker handles a contiguous portion. We want to minimize the load on the most burdened worker.
Key Observation: The Answer Has Bounds
Before diving into the solution, let's think about what values the answer could take:
Minimum possible: At least max(nums) = 10. Each element must belong to some subarray.
Maximum possible: At most sum(nums) = 32. This happens when k=1.
So our answer lies in [10, 32].
Why Binary Search?
Here's the crucial observation: if we can split with max sum X, we can definitely split with any max sum > X.
This monotonic property is exactly what enables binary search! The search space is divided into two halves: values that don't work, and values that do. Binary search finds the boundary.
This is the "Binary Search on Answer" pattern. Instead of searching through the array for an element, we search through the space of possible answers to find the optimal one. The monotonic property guarantees binary search will find it.
The Binary Search Algorithm
Here's how the binary search works:
Initialize: left = max(nums), right = sum(nums)
Loop while left < right:
Pick mid = (left + right) / 2
If we can split with max sum ≤ mid: answer might be smaller → right = mid
If we can't: answer must be larger → left = mid + 1
Returnleft (the minimum valid answer)
The Feasibility Check (Helper Function)
For each mid, we need a helper function to check: "Can we split into ≤ k subarrays with max sum ≤ mid?"
Greedy approach (O(n) per check):
Iterate left to right, greedily adding elements
When sum would exceed maxSum, start a new subarray
Return subarrays_needed ≤ k
Walkthrough
Let's trace through nums = [7, 2, 5, 10, 8] with k = 2:
Visualization
Visualization
Python
def splitArray(nums, k):
def canSplit(maxSum):
subarrays = 1
currentSum = 0
for num in nums:
if currentSum + num > maxSum:
subarrays += 1
currentSum = num
else:
currentSum += num
return subarrays <= k
left = max(nums)
right = sum(nums)
while left < right:
mid = (left + right) // 2
if canSplit(mid):
right = mid
else:
left = mid + 1
return left
Binary search on the answer: find the minimum possible largest subarray sum
0 / 42
Solution
The algorithm combines binary search with a greedy feasibility check:
Initialize bounds: left = max(nums), right = sum(nums)
Binary search: While left < right
Calculate mid = (left + right) / 2
Check if we can split with max sum ≤ mid
If yes: answer might be smaller, set right = mid
If no: answer must be larger, set left = mid + 1
Returnleft as the answer
The greedy check runs in O(n) time, and binary search runs O(log(sum - max)) iterations, giving us O(n · log(sum)) total time complexity.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n · log(sum)) Binary search runs O(log(sum)) iterations, and each iteration does O(n) work for the greedy feasibility check.
Space Complexity: O(1) We only use a few variables regardless of input size.
When to Use Binary Search on Answer
This technique applies when:
The answer lies within a known range [lo, hi]
There's a monotonic predicate: if answer x is feasible, then all y > x (or y < x) are also feasible
You can efficiently check if a given candidate is feasible
Common problems using this pattern:
Minimize the maximum (or maximize the minimum) of something
Capacity/allocation problems
"Can we do X with budget Y?" questions
When you see "minimize the maximum" or "maximize the minimum", consider binary search on the answer. The key is identifying the monotonic property and designing an efficient feasibility check.
