410. Split Array Largest Sum - Explanation
Description
You are 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 = [2,4,10,1,5], k = 2
Output: 16Explanation: The best way is to split into [2,4,10] and [1,5], where the largest sum among the two subarrays is only 16.
Example 2:
Input: nums = [1,0,2,3,5], k = 4
Output: 5Explanation: The best way is to split into [1], [0,2], [3] and [5], where the largest sum among the two subarrays is only 5.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1,000,0001 <= k <= min(50, nums.length)
Topics
Prerequisites
Before attempting this problem, you should be comfortable with:
- Recursion - Exploring all possible split points by recursively solving subproblems
- Dynamic Programming - Using memoization or tabulation to cache overlapping subproblems
- Binary Search on Answer - Searching for the minimum feasible value when the check function is monotonic
- Greedy Algorithms - Validating a candidate answer by greedily forming subarrays
- Prefix Sums - Efficiently computing subarray sums for optimized feasibility checks
1. Recursion
Intuition
We want to split the array into k subarrays and minimize the maximum sum among them. Using recursion, we try every possible way to form the first subarray, then recursively solve for the remaining elements with k-1 subarrays. For each split point, we track the maximum sum between the current subarray and the best result from the recursive call, then take the minimum across all choices.
Algorithm
- Define
dfs(i, m)whereiis the starting index andmis the number of subarrays left to form. - Base cases: if
i == nandm == 0, return0(valid split). If either condition fails alone, return infinity (invalid). - For each possible endpoint
jof the current subarray:- Accumulate the sum from index
itoj. - Recursively solve
dfs(j + 1, m - 1)for the remaining portion. - Track
min(res, max(curSum, recursiveResult)).
- Accumulate the sum from index
- Return the result of
dfs(0, k).
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
n = len(nums)
def dfs(i, m):
if i == n:
return 0 if m == 0 else float("inf")
if m == 0:
return float("inf")
res = float("inf")
curSum = 0
for j in range(i, n - m + 1):
curSum += nums[j]
res = min(res, max(curSum, dfs(j + 1, m - 1)))
return res
return dfs(0, k)Time & Space Complexity
- Time complexity:
- Space complexity: for recursion stack.
2. Dynamic Programming (Top-Down)
Intuition
The recursive solution has overlapping subproblems since we may compute dfs(i, m) multiple times with the same parameters. By caching results in a memoization table, we avoid redundant computation. The state is defined by the current index and remaining subarrays to form.
Algorithm
- Create a 2D memoization table
dp[n][k+1]initialized to-1. - Use the same recursive structure as the brute force approach.
- Before computing, check if
dp[i][m]is already computed. If so, return the cached value. - After computing the result for state
(i, m), store it indp[i][m]. - Return
dfs(0, k).
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [[-1] * (k + 1) for _ in range(n)]
def dfs(i, m):
if i == n:
return 0 if m == 0 else float("inf")
if m == 0:
return float("inf")
if dp[i][m] != -1:
return dp[i][m]
res = float("inf")
curSum = 0
for j in range(i, n - m + 1):
curSum += nums[j]
res = min(res, max(curSum, dfs(j + 1, m - 1)))
dp[i][m] = res
return res
return dfs(0, k)Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the array and is the number of sub-arrays to form.
3. Dynamic Programming (Bottom-Up)
Intuition
We can convert the top-down approach to bottom-up by filling the DP table iteratively. We build solutions for smaller subproblems first (fewer subarrays, starting from the end of the array) and use them to solve larger problems. The table dp[i][m] represents the minimum largest sum when splitting elements from index i to the end into m subarrays.
Algorithm
- Create
dp[n+1][k+1]initialized to infinity, withdp[n][0] = 0as the base case. - For each number of subarrays
mfrom1tok:- For each starting index
ifromn-1down to0:- Try all possible endpoints
jfor the first subarray. - Compute
dp[i][m] = min(dp[i][m], max(curSum, dp[j+1][m-1])).
- Try all possible endpoints
- For each starting index
- Return
dp[0][k].
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [[float("inf")] * (k + 1) for _ in range(n + 1)]
dp[n][0] = 0
for m in range(1, k + 1):
for i in range(n - 1, -1, -1):
curSum = 0
for j in range(i, n - m + 1):
curSum += nums[j]
dp[i][m] = min(dp[i][m], max(curSum, dp[j + 1][m - 1]))
return dp[0][k]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the array and is the number of sub-arrays to form.
4. Dynamic Programming (Space Optimized)
Intuition
In the bottom-up approach, computing dp[i][m] only depends on values from dp[...][m-1]. We can reduce space from O(k * n) to O(n) by using two 1D arrays: one for the previous layer and one for the current layer, swapping them after each iteration.
Algorithm
- Create two 1D arrays
dpandnextDpof sizen+1, initialized to infinity withdp[n] = 0. - For each number of subarrays
mfrom1tok:- Reset
nextDpto infinity. - For each starting index
i, compute the minimum largest sum using the previousdparray. - Swap
dpandnextDp.
- Reset
- Return
dp[0].
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
n = len(nums)
dp = [float("inf")] * (n + 1)
dp[n] = 0
for m in range(1, k + 1):
nextDp = [float("inf")] * (n + 1)
for i in range(n - 1, -1, -1):
curSum = 0
for j in range(i, n - m + 1):
curSum += nums[j]
nextDp[i] = min(nextDp[i], max(curSum, dp[j + 1]))
dp = nextDp
return dp[0]Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the array and is the number of sub-arrays to form.
5. Binary Search
Intuition
Instead of trying all possible splits, we binary search on the answer itself. The minimum possible largest sum is the maximum element (when k equals n), and the maximum is the total sum (when k equals 1). For a given target sum, we greedily check if we can split the array into at most k subarrays where no subarray exceeds the target. If possible, we try a smaller target; otherwise, we need a larger one.
Algorithm
- Set
l = max(nums)andr = sum(nums). - Binary search while
l <= r:- For
mid, check if we can split into at mostksubarrays with max sum<= mid. - The check greedily adds elements until the sum exceeds
mid, then starts a new subarray. - If feasible, record
midas a candidate and search for smaller values. - Otherwise, search for larger values.
- For
- Return the smallest feasible value.
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
def canSplit(largest):
subarray = 1
curSum = 0
for num in nums:
curSum += num
if curSum > largest:
subarray += 1
if subarray > k:
return False
curSum = num
return True
l, r = max(nums), sum(nums)
res = r
while l <= r:
mid = l + (r - l) // 2
if canSplit(mid):
res = mid
r = mid - 1
else:
l = mid + 1
return resTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the array and is the sum of all the elements in the array.
6. Binary Search + Prefix Sum
Intuition
We can optimize the feasibility check using prefix sums and binary search. Instead of linearly scanning to find where each subarray should end, we use binary search on the prefix sum array to find the farthest index where the subarray sum stays within the target. This speeds up the check from O(n) to O(k log n) for each candidate.
Algorithm
- Build a prefix sum array where
prefix[i]is the sum of elements from index0toi-1. - Binary search on the answer as before.
- In the feasibility check:
- For each subarray start, binary search for the rightmost end where
prefix[end] - prefix[start] <= target. - Count subarrays and verify it does not exceed
k.
- For each subarray start, binary search for the rightmost end where
- Return the smallest feasible value.
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
def canSplit(largest):
subarrays = 0
i = 0
while i < n:
l, r = i + 1, n
while l <= r:
mid = l + (r - l) // 2
if prefix[mid] - prefix[i] <= largest:
l = mid + 1
else:
r = mid - 1
subarrays += 1
i = r
if subarrays > k:
return False
return True
l, r = max(nums), sum(nums)
res = r
while l <= r:
mid = l + (r - l) // 2
if canSplit(mid):
res = mid
r = mid - 1
else:
l = mid + 1
return resTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the array , is the sum of all the elements in the array, and is the number of sub-arrays to form.
Common Pitfalls
Setting Incorrect Binary Search Bounds
The lower bound must be max(nums) (not 0 or 1) because no subarray sum can be smaller than the largest single element. The upper bound is sum(nums) representing the case where all elements are in one subarray. Using incorrect bounds leads to invalid answers or infinite loops.
Off-by-One in Subarray Counting
When checking if a target sum is feasible, starting the subarray count at 0 instead of 1 causes the algorithm to allow one extra split. The count should start at 1 since we always have at least one subarray before any splits occur.
Integer Overflow in Sum Calculations
For large arrays with large values, the sum of elements can overflow 32-bit integers. Using long or equivalent 64-bit types for prefix sums and running totals prevents incorrect comparisons and ensures the binary search operates on valid values.
Greedy Check Not Resetting Current Sum
In the feasibility check, when the current sum exceeds the target and a new subarray begins, the current sum must be reset to the current element (not to 0). Resetting to 0 loses the current element and produces incorrect subarray counts.
Confusing Minimizing Maximum with Maximizing Minimum
This problem asks to minimize the largest subarray sum, which means we want the smallest possible value that still allows a valid k-way split. Binary searching in the wrong direction (trying to maximize instead of minimize) yields incorrect results.
Sign in to join the discussion