70. Split Array Largest Sum
🔗 LeetCode Problem: 410. Split Array Largest Sum
📊 Difficulty: Hard
🏷️ Topics: Array, Binary Search, Dynamic Programming, Greedy
Problem Statement
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.
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
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3,4] and [5], where the largest sum among the two subarrays is only 9.
Example 3:
Input: nums = [1,4,4], k = 3
Output: 4
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 10^6
- 1 <= k <= min(50, nums.length)
🎨 Visual Understanding
The Problem Visualized
Example 1: nums = [7,2,5,10,8], k = 2
Different ways to split into 2 subarrays:
Option 1: [7] | [2,5,10,8]
Sums: 7, 25
Largest: 25
Option 2: [7,2] | [5,10,8]
Sums: 9, 23
Largest: 23
Option 3: [7,2,5] | [10,8]
Sums: 14, 18
Largest: 18 ✓ Best!
Option 4: [7,2,5,10] | [8]
Sums: 24, 8
Largest: 24
Minimum largest sum = 18
Example 2: nums = [1,2,3,4,5], k = 2
Options:
[1] | [2,3,4,5] → max(1, 14) = 14
[1,2] | [3,4,5] → max(3, 12) = 12
[1,2,3] | [4,5] → max(6, 9) = 9 ✓
[1,2,3,4] | [5] → max(10, 5) = 10
Minimum largest sum = 9
Example 3: nums = [1,4,4], k = 3
Only one way (k = length):
[1] | [4] | [4]
Sums: 1, 4, 4
Largest: 4
Visual representation of split:
nums = [7, 2, 5, 10, 8], k = 2, trying maxSum = 18
Can we split with no subarray sum > 18?
Current sum = 0, splits = 0
7: 0+7=7 ≤ 18, add to current
2: 7+2=9 ≤ 18, add to current
5: 9+5=14 ≤ 18, add to current
10: 14+10=24 > 18, must split here!
splits++, current = 10
8: 10+8=18 ≤ 18, add to current
Total splits: 1 (created 2 subarrays)
1 ≤ k-1? Yes! ✓
maxSum = 18 works!
🚨 CRITICAL INSIGHT - Binary Search on Answer!
The Key Pattern!
This is "Binary Search on Answer" pattern!
Same family as:
- Koko Eating Bananas
- Ship Packages
- Make Bouquets
What are we searching?
NOT searching in the array
Searching for MINIMUM possible largest sum
Search Space:
Minimum: max(nums) (largest single element)
Maximum: sum(nums) (entire array as one subarray)
Range: [max(nums), sum(nums)]
Key Property (Monotonic):
If we can split with maxSum = M:
→ We can split with any maxSum > M
(More capacity = easier to split)
If we can't split with maxSum = M:
→ We can't split with any maxSum < M
(Less capacity = harder to split)
Pattern: [NO NO NO NO | YES YES YES YES]
[too small | large enough ]
↑
Find this boundary!
We want: MINIMUM maxSum that allows k splits
= Find FIRST "YES"
= Binary search for leftmost valid!
How to Check if maxSum Works
For a given maxSum, can we split into ≤ k subarrays?
Greedy approach:
currentSum = 0
subarrays = 1 (start with first subarray)
For each number:
If currentSum + num > maxSum:
Start new subarray
subarrays++
currentSum = num
Else:
Add to current subarray
currentSum += num
If subarrays ≤ k: maxSum works! ✓
Else: maxSum too small ✗
Example: nums = [7,2,5,10,8], k = 2, maxSum = 18
currentSum = 0, subarrays = 1
7: 0+7=7 ≤ 18, currentSum = 7
2: 7+2=9 ≤ 18, currentSum = 9
5: 9+5=14 ≤ 18, currentSum = 14
10: 14+10=24 > 18, split! subarrays = 2, currentSum = 10
8: 10+8=18 ≤ 18, currentSum = 18
Total subarrays: 2
2 ≤ 2? Yes! ✓ maxSum = 18 works!
Why Binary Search Works
Example: nums = [7,2,5,10,8], k = 2
Search space: maxSum ∈ [10, 32]
min = max(nums) = 10
max = sum(nums) = 32
Test different maxSum values:
maxSum = 10: Can split? [7,2] [5] [10] [8] = 4 subarrays > 2 ✗
maxSum = 15: Can split? [7,2,5] [10] [8] = 3 subarrays > 2 ✗
maxSum = 17: Can split? [7,2,5] [10] [8] = 3 subarrays > 2 ✗
maxSum = 18: Can split? [7,2,5] [10,8] = 2 subarrays ≤ 2 ✓
maxSum = 20: Can split? [7,2,5] [10,8] = 2 subarrays ≤ 2 ✓
...
maxSum = 32: Can split? [7,2,5,10,8] = 1 subarray ≤ 2 ✓
Pattern: [✗ ✗ ✗ | ✓ ✓ ✓ ...]
[10..17 | 18..32 ]
↑
Find this first YES!
Binary search finds boundary in O(log n)!
🎯 Approach 1: Try All Splits (Brute Force with Recursion)
The Most Natural Thinking 💭
Core Logic:
Try all possible ways to split array into k parts
Track minimum of maximum sums
Implementation
public int splitArray(int[] nums, int k) {
return split(nums, 0, k);
}
private int split(int[] nums, int start, int k) {
// Base case: last subarray
if (k == 1) {
int sum = 0;
for (int i = start; i < nums.length; i++) {
sum += nums[i];
}
return sum;
}
int minLargestSum = Integer.MAX_VALUE;
int currentSum = 0;
// Try each position as end of first subarray
for (int i = start; i < nums.length - k + 1; i++) {
currentSum += nums[i];
// Recursively split remaining into k-1 parts
int largestInRest = split(nums, i + 1, k - 1);
// Largest sum in this split configuration
int currentLargest = Math.max(currentSum, largestInRest);
// Track minimum
minLargestSum = Math.min(minLargestSum, currentLargest);
}
return minLargestSum;
}
⏰ Time: O(k × 2^n) - Exponential (try all splits)
💾 Space: O(n) - Recursion stack
❌ Problem: Way too slow! Need better approach!
🎯 Approach 2: Binary Search on Answer (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Don't try all splits!
Binary search on the answer (largest sum)!
Search space: [max(nums), sum(nums)]
Property: Monotonic (if maxSum works, maxSum+1 works)
Goal: Find MINIMUM maxSum that allows ≤ k splits
The Strategy:
Binary Search on maxSum:
1. left = max(nums), right = sum(nums)
2. While left < right:
a. mid = left + (right - left) / 2
b. If canSplit(nums, k, mid):
mid works, try smaller
right = mid
c. Else:
mid too small, need larger
left = mid + 1
3. Return left
Implementation
public int splitArray(int[] nums, int k) {
// Find search bounds
int left = 0; // Minimum possible largest sum (max element)
int right = 0; // Maximum possible largest sum (total sum)
for (int num : nums) {
left = Math.max(left, num); // Must be at least max element
right += num; // At most entire array sum
}
// Binary search for minimum valid largest sum
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, k, mid)) {
// Can split with maxSum = mid, try smaller
right = mid;
} else {
// Can't split with maxSum = mid, need larger
left = mid + 1;
}
}
return left;
}
// Check if we can split array into ≤ k subarrays with max sum ≤ maxSum
private boolean canSplit(int[] nums, int k, int maxSum) {
int subarrays = 1; // Start with first subarray
int currentSum = 0;
for (int num : nums) {
// Can we add this number to current subarray?
if (currentSum + num > maxSum) {
// No, start new subarray
subarrays++;
currentSum = num;
// Early termination
if (subarrays > k) {
return false;
}
} else {
// Yes, add to current subarray
currentSum += num;
}
}
return subarrays <= k;
}
⏰ Time: O(n × log(sum - max)) - Binary search × checking all elements
💾 Space: O(1) - Only variables
🔍 Dry Run
Example 1: nums = [7,2,5,10,8], k = 2
Goal: Find minimum largest sum
Find bounds:
left = max(nums) = 10
right = sum(nums) = 32
Initial: left = 10, right = 32
Iteration 1:
mid = 10 + (32 - 10) / 2 = 21
Can split with maxSum = 21?
currentSum = 0, subarrays = 1
7: 0+7=7 ≤ 21, currentSum = 7
2: 7+2=9 ≤ 21, currentSum = 9
5: 9+5=14 ≤ 21, currentSum = 14
10: 14+10=24 > 21, split! subarrays = 2, currentSum = 10
8: 10+8=18 ≤ 21, currentSum = 18
Total subarrays: 2 ≤ 2 ✓
Works! Try smaller
right = 21
Range: [10, 21]
Iteration 2:
mid = 10 + (21 - 10) / 2 = 15
Can split with maxSum = 15?
currentSum = 0, subarrays = 1
7: 0+7=7 ≤ 15, currentSum = 7
2: 7+2=9 ≤ 15, currentSum = 9
5: 9+5=14 ≤ 15, currentSum = 14
10: 14+10=24 > 15, split! subarrays = 2, currentSum = 10
8: 10+8=18 > 15, split! subarrays = 3, currentSum = 8
Total subarrays: 3 > 2 ✗
Too small! Need larger
left = 16
Range: [16, 21]
Iteration 3:
mid = 16 + (21 - 16) / 2 = 18
Can split with maxSum = 18?
7: currentSum = 7
2: currentSum = 9
5: currentSum = 14
10: 14+10=24 > 18, split! subarrays = 2, currentSum = 10
8: currentSum = 18
Total subarrays: 2 ≤ 2 ✓
Works! Try smaller
right = 18
Range: [16, 18]
Iteration 4:
mid = 16 + (18 - 16) / 2 = 17
Can split with maxSum = 17?
7: currentSum = 7
2: currentSum = 9
5: currentSum = 14
10: split! subarrays = 2, currentSum = 10
8: 10+8=18 > 17, split! subarrays = 3
Total subarrays: 3 > 2 ✗
Too small!
left = 18
Range: [18, 18]
Loop ends (left == right)
return 18 ✓
Example 2: nums = [1,2,3,4,5], k = 2
Bounds: left = 5, right = 15
Iteration 1:
mid = 10
Can split with maxSum = 10?
1: currentSum = 1
2: currentSum = 3
3: currentSum = 6
4: currentSum = 10
5: 10+5=15 > 10, split! subarrays = 2, currentSum = 5
Total: 2 ≤ 2 ✓
right = 10
Iteration 2:
mid = 7
Can split with maxSum = 7?
1: currentSum = 1
2: currentSum = 3
3: currentSum = 6
4: 6+4=10 > 7, split! subarrays = 2, currentSum = 4
5: 4+5=9 > 7, split! subarrays = 3
Total: 3 > 2 ✗
left = 8
Iteration 3:
mid = 9
Can split with maxSum = 9?
1: currentSum = 1
2: currentSum = 3
3: currentSum = 6
4: 6+4=10 > 9, split! subarrays = 2, currentSum = 4
5: 4+5=9 ≤ 9, currentSum = 9
Total: 2 ≤ 2 ✓
right = 9
Iteration 4:
mid = 8
Can split with maxSum = 8?
Similar analysis... subarrays = 3 > 2 ✗
left = 9
Loop ends
return 9 ✓
🎯 Why This Works - Deep Dive
The Monotonic Property:
═══════════════════════════════════════════════════════════════
Key insight: Larger maxSum = Easier to split
If we can split with maxSum = M into ≤ k subarrays:
→ With maxSum = M+1, we can do same split or better
→ Will use ≤ k subarrays
If we can't split with maxSum = M:
→ With maxSum = M-1, even harder
→ Will need > k subarrays
This creates sorted pattern:
[CAN'T CAN'T ... | CAN CAN CAN ...]
↑
Find boundary
The Greedy Splitting:
═══════════════════════════════════════════════════════════════
Greedy strategy: Pack as much as possible in each subarray
Why greedy works?
We want to MINIMIZE number of subarrays
Packing greedily minimizes subarrays needed
Proof by contradiction:
Suppose greedy uses G subarrays
Suppose optimal uses O < G subarrays
Then optimal must have at least one subarray
that exceeds maxSum (since greedy packed maximally)
Contradiction! ✗
Therefore: Greedy is optimal ✓
The Search Bounds:
═══════════════════════════════════════════════════════════════
Minimum maxSum:
At least max(nums)
Each subarray has at least one element
Some subarray contains the max element
Maximum maxSum:
At most sum(nums)
Put entire array in one subarray
Tighter than [0, infinity]!
The "Find First Valid" Pattern:
═══════════════════════════════════════════════════════════════
Loop: while (left < right)
Converge to minimum valid
When valid: right = mid
mid works, but try smaller
Keep mid in range
When invalid: left = mid + 1
mid doesn't work, exclude it
Return: left (minimum valid maxSum)
Same pattern as other "BS on Answer" problems!
Time Complexity:
═══════════════════════════════════════════════════════════════
Binary search: O(log(sum - max))
≈ O(log(sum(nums)))
Each check: O(n) to process all elements
Total: O(n × log(sum(nums)))
Much better than exponential brute force!
Space: O(1) - only variables
Relationship to Other Problems
This problem is VERY similar to:
┌────────────────────────────────────────────┐
│ Koko Eating Bananas (LC 875): │
│ Find minimum eating speed │
│ Check: Can finish in h hours? │
│ │
│ Ship Packages (LC 1011): │
│ Find minimum ship capacity │
│ Check: Can ship in d days? │
│ │
│ Split Array (This Problem): │
│ Find minimum largest subarray sum │
│ Check: Can split into ≤ k subarrays? │
└────────────────────────────────────────────┘
All use:
- Binary search on answer space
- Greedy checking
- Monotonic property
- Find minimum valid value
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong bounds
// ❌ WRONG
int left = 0; // Should be max(nums)
int right = Integer.MAX_VALUE; // Too large!
// ✓ CORRECT
int left = max(nums); // Minimum possible
int right = sum(nums); // Maximum possible
Mistake 2: Starting with 0 subarrays
// ❌ WRONG
int subarrays = 0; // Should start at 1!
// ✓ CORRECT
int subarrays = 1; // First element starts first subarray
Mistake 3: Not using early termination
// ❌ INEFFICIENT - Check all elements
for (int num : nums) {
if (currentSum + num > maxSum) {
subarrays++;
}
}
return subarrays <= k;
// ✓ BETTER - Early exit
for (int num : nums) {
if (currentSum + num > maxSum) {
subarrays++;
if (subarrays > k) {
return false; // Early exit!
}
}
}
Mistake 4: Wrong loop condition
// ❌ WRONG
while (left <= right) {
if (canSplit(mid)) {
right = mid; // Infinite loop risk!
}
}
// ✓ CORRECT
while (left < right) {
if (canSplit(mid)) {
right = mid;
}
}
Mistake 5: Confusing k splits vs k subarrays
// k = 2 means:
// 2 SUBARRAYS
// 1 SPLIT (the cut)
// Common confusion:
// If we make k splits, we get k+1 subarrays!
// In this problem: k = number of SUBARRAYS
🎯 Pattern Recognition
Problem Type: Binary Search on Answer Space
Core Pattern: Minimize Maximum Value with Constraint
When to Apply:
✓ Need to find OPTIMAL value (not in array)
✓ Can CHECK if value satisfies constraint
✓ Monotonic property exists
✓ "Minimize the maximum" or "Maximize the minimum"
✓ Split/partition with constraint
Recognition Keywords:
- "Minimize the largest"
- "Split into k parts"
- "Non-empty subarrays"
- "Contiguous"
- Optimization problem
Similar Problems:
- Koko Eating Bananas (LC 875)
- Capacity To Ship Packages (LC 1011)
- Painter's Partition (Classic problem)
- Allocate Books (Classic problem)
Key Pattern Elements:
┌────────────────────────────────────────────┐
│ Binary Search on Answer: │
│ 1. Define search space [min, max] │
│ 2. Greedy check: can split in ≤ k parts │
│ 3. Monotonic: larger → easier │
│ 4. Find minimum valid value │
│ │
│ "Minimize Maximum" pattern! │
└────────────────────────────────────────────┘
This is a CLASSIC Hard problem pattern!
🧠 Interview Strategy
Step 1: "Minimize largest sum → Binary search on answer"
Step 2: "Search space: [max(nums), sum(nums)]"
Step 3: "Check: greedy packing into subarrays"
Step 4: "Monotonic: larger maxSum → fewer subarrays"
Step 5: "Find minimum valid maxSum"
Key Points to Mention:
- Binary search on ANSWER (not array)
- Bounds: max(nums) to sum(nums)
- Check: greedy packing
- Greedy: fit as much as possible per subarray
- Monotonic property
- Find minimum valid maxSum
- Loop: while (left < right)
- When valid: right = mid
- When invalid: left = mid + 1
- Time: O(n log(sum))
Why This Approach?
"This is a binary search on answer space problem. I'm searching
for the minimum possible largest subarray sum. The key insight
is the monotonic property: if I can split the array into k
subarrays with largest sum M, I can definitely do it with any
larger sum. For each candidate maxSum, I use greedy packing -
fitting as many elements as possible in each subarray without
exceeding maxSum. If I can fit everything in k or fewer
subarrays, I try a smaller maxSum. Otherwise, I need a larger
maxSum."
Why Greedy Works?
"I want to minimize the number of subarrays used. By packing
greedily - adding as many elements as possible to each subarray
- I'm minimizing the splits needed. Any other packing strategy
would either use more subarrays or achieve the same result."
Why These Bounds?
"The minimum possible largest sum is max(nums) because every
subarray must contain at least one element, and at least one
will contain the maximum element. The maximum possible is
sum(nums) when we put everything in one subarray. Any value
outside this range doesn't make sense."
📝 Quick Revision Notes
🎯 Core Concept:
Split Array Largest Sum: Find minimum largest sum. Binary search on maxSum [max(nums), sum(nums)]. Check: greedy packing - fit as much as possible per subarray. Count subarrays needed. If ≤ k → valid. Monotonic: larger maxSum → fewer subarrays. Find minimum valid!
⚡ Quick Implementation:
class Test {
public int splitArray(int[] a, int k) {
// Find search bounds
int left = 0; // Minimum possible largest sum (max element)
int right = 0; // Maximum possible largest sum (total sum)
for (int num : a) {
left = Math.max(left, num); // Must be at least max element
right += num; // At most entire array sum
}
while (left < right) {
int mid = left + (right - left) / 2;
if(isPossible(a, k , mid)) {
right = mid;
} else {
left = mid + 1 ;
}
}
return left;
}
private boolean isPossible(int[] a, int k, int maxSum) {
int subarrays = 1;
int runningSum = 0;
for(int num : a) {
if(runningSum + num > maxSum) {
runningSum = num;
subarrays++;
if(subarrays > k) {
return false;
}
} else {
runningSum += num;
}
}
return subarrays <= k;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.splitArray(new int[] {7,2,5,10,8}, 2) == 18);
System.out.println(t.splitArray(new int[] {1,2,3,4,5}, 2) == 9);
System.out.println(t.splitArray(new int[] {7,2,5,10,8}, 1) == 32);
System.out.println(t.splitArray(new int[] {7,2,5,10,8}, 5) == 10);
System.out.println(t.splitArray(new int[] {5,5,5,5}, 2) == 10);
System.out.println(t.splitArray(new int[] {1,2,100,4,5}, 2) == 103);
System.out.println(t.splitArray(new int[] {1,2}, 2) == 2);
}
}
🔑 Key Insights:
- Pattern: Binary Search on Answer (Minimize Maximum)
- Bounds: [max(nums), sum(nums)]
- Check: Greedy packing into subarrays
- Greedy: Fit max elements per subarray
- Monotonic: M works → M+1 works
- Find: Minimum valid maxSum
- Loop:
while (left < right) - Valid:
right = mid(try smaller) - Invalid:
left = mid + 1(need larger) - Time: O(n × log(sum)), Space: O(1)
🎪 Memory Aid:
"Binary search on max sum! Greedy pack, count subarrays!"
Think: "Minimize maximum = BS on answer!"
💡 The Key Insight:
Minimize the largest = Find minimum valid
Monotonic property:
maxSum = M works → M+1 works (easier)
maxSum = M fails → M-1 fails (harder)
[FAIL FAIL | PASS PASS PASS]
↑
Find boundary!
⚠️ Critical Details:
1. Bounds: max(nums) to sum(nums)
2. Greedy: Pack as much as possible
3. Start: subarrays = 1 (not 0!)
4. Split: when currentSum + num > maxSum
5. Early exit: if subarrays > k
6. Valid: right = mid (try smaller)
7. Invalid: left = mid + 1
8. Return: left (minimum maxSum)
🔥 The Greedy Packing:
nums = [7,2,5,10,8], maxSum = 18
subarrays = 1, currentSum = 0
7: 0+7=7 ≤ 18, add → currentSum = 7
2: 7+2=9 ≤ 18, add → currentSum = 9
5: 9+5=14 ≤ 18, add → currentSum = 14
10: 14+10=24 > 18, SPLIT!
subarrays = 2
currentSum = 10
8: 10+8=18 ≤ 18, add → currentSum = 18
Result: 2 subarrays
Split: [7,2,5] | [10,8]
💡 Why Start with subarrays = 1:
First element always goes in first subarray!
We count SUBARRAYS, not SPLITS:
1 split → 2 subarrays
2 splits → 3 subarrays
k-1 splits → k subarrays
Start with 1, increment on each split.
🧪 Edge Cases
Case 1: k = 1 (no split)
Input: nums = [7,2,5,10,8], k = 1
Output: 32
(Entire array as one subarray)
Case 2: k = n (max splits)
Input: nums = [7,2,5,10,8], k = 5
Output: 10
(Each element in its own subarray)
Case 3: All same values
Input: nums = [5,5,5,5], k = 2
Output: 10
(Split into [5,5] and [5,5])
Case 4: Single large element
Input: nums = [1,2,100,4,5], k = 2
Output: 103
Case 5: Two elements
Input: nums = [1,2], k = 2
Output: 2
(Each in its own)
All handled correctly! ✓
Related Patterns
- Koko Eating Bananas (LC 875) - Same pattern
- Capacity To Ship Packages (LC 1011) - Same pattern
- Painter's Partition Problem - Classic problem
- Allocate Books - Classic problem
Happy practicing! 🎯
Note: This is a CLASSIC Hard problem! The "minimize maximum" pattern with binary search on answer space appears frequently in interviews. Master this!