Split Array Largest Sum
HardPrompt
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] and [4,5], where the largest sum among the two subarrays is only 9.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem by breaking it down into smaller, overlapping subproblems. We build a table dp[i][j] which stores the minimum largest subarray sum for splitting the first j elements of the array into i parts. The final answer is found by computing the value for splitting the entire array into k parts.
Algorithm
- Define a 2D array
dp[i][j]to store the minimum largest subarray sum for splitting the firstjelements ofnumsintoisubarrays. - The goal is to compute
dp[k][n], wherenis the length of the array. - To avoid recomputing sums, pre-calculate a
prefixSumarray whereprefixSum[i]is the sum of elements fromnums[0]tonums[i-1]. - The base case is for
i=1:dp[1][j] = prefixSum[j], as splittingjelements into one subarray results in the sum of thosejelements. - The transition to compute
dp[i][j]involves trying all possible split pointsp(where0 <= p < j). The last subarray would benums[p...j-1], and the firstpelements would have been split intoi-1subarrays. - The recurrence relation is:
dp[i][j] = min(dp[i][j], max(dp[i-1][p], prefixSum[j] - prefixSum[p]))for all validp. - The final answer is
dp[k][n].
Walkthrough
In this dynamic programming approach, we define dp[i][j] as the minimum largest sum required to split the subarray nums[0...j-1] (the first j elements) into i non-empty subarrays. Our objective is to find dp[k][n], where n is the length of nums.
The state transition is formulated by considering all possible split points for the last (i-th) subarray. If we decide the i-th subarray is nums[p...j-1], then the first p elements (nums[0...p-1]) must have been optimally split into i-1 subarrays. The largest sum for this specific split would be the maximum of the sum of the last subarray (sum(nums[p...j-1])) and the result for the prefix (dp[i-1][p]). We want to choose a split point p that minimizes this value.
To make the calculation of subarray sums efficient, we pre-compute a prefix sum array. This allows us to find the sum of any subarray in O(1) time.
class Solution { public int splitArray(int[] nums, int k) { int n = nums.length; long[] prefixSum = new long[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } long[][] dp = new long[k + 1][n + 1]; for (int i = 0; i <= k; i++) { for (int j = 0; j <= n; j++) { dp[i][j] = Long.MAX_VALUE; } } dp[0][0] = 0; for (int i = 1; i <= k; i++) { // Number of subarrays for (int j = 1; j <= n; j++) { // Number of elements for (int p = 0; p < j; p++) { // Split point long lastSum = prefixSum[j] - prefixSum[p]; if (dp[i - 1][p] != Long.MAX_VALUE) { long currentMax = Math.max(dp[i - 1][p], lastSum); dp[i][j] = Math.min(dp[i][j], currentMax); } } } } return (int) dp[k][n]; }}Complexity
Time
O(k * n^2), where `n` is the number of elements and `k` is the number of splits. There are three nested loops to fill the DP table.
Space
O(k * n), for the 2D DP table of size `(k+1) x (n+1)` and the prefix sum array of size `n+1`.
Trade-offs
Pros
It is a systematic approach that guarantees finding the optimal solution.
The logic is relatively straightforward to formulate for those familiar with dynamic programming.
Cons
The time complexity of
O(k * n^2)can be too slow ifnis large.The space complexity of
O(k * n)can be substantial for largekandn.
This highly efficient approach uses binary search on the answer. The key insight is that if we can split the array with a maximum subarray sum of x, we can also do it for any value greater than x. This monotonic property allows us to search for the smallest possible value of this maximum sum within a defined range. The range for the answer is from the largest single element in the array to the total sum of the array.
Algorithm
- The answer must lie in the range
[max(nums), sum(nums)]. - We can binary search for the minimum possible value
xin this range that can be the largest subarray sum. - For a given
x, we need a helper functionisFeasible(x)to check if it's possible to splitnumsintokor fewer subarrays, each with a sum at mostx. - The
isFeasible(x)function can be implemented greedily: iterate throughnums, creating subarrays. Start a new subarray whenever the current one's sum would exceedx. - Count the number of subarrays needed. If this count is
_<= k, thenxis a feasible maximum sum. - In the binary search, if
isFeasible(mid)is true, it meansmidis a possible answer, so we try for a smaller one:high = mid - 1. - If
isFeasible(mid)is false,midis too small, so we need to allow a larger sum:low = mid + 1. - The smallest
midfor whichisFeasible(mid)is true is our answer.
Walkthrough
This approach reframes the problem from finding the value to verifying if a given value is possible. The possible values for the minimized largest sum are bounded. The lower bound is the largest element in the array (as it must belong to some subarray), and the upper bound is the sum of all elements (the case for k=1).
We can binary search within this range [max(nums), sum(nums)]. For each mid value we test, we need to determine if it's possible to split the array into k or fewer subarrays such that no subarray's sum exceeds mid. This check can be done greedily in linear time.
We iterate through the array, accumulating a currentSum. As soon as adding the next element would make currentSum exceed mid, we must start a new subarray. We count the total number of subarrays required. If this count is less than or equal to k, then mid is a feasible largest sum, and we try to find an even smaller one by narrowing our search to the lower half. Otherwise, mid is too small, and we must search in the upper half.
class Solution { public int splitArray(int[] nums, int k) { long low = 0; long high = 0; for (int num : nums) { low = Math.max(low, num); high += num; } long ans = high; while (low <= high) { long mid = low + (high - low) / 2; if (isFeasible(nums, k, mid)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return (int) ans; } // Checks if we can split nums into k or fewer subarrays, // with each subarray's sum not exceeding maxSum. private boolean isFeasible(int[] nums, int k, long maxSum) { int subarraysNeeded = 1; long currentSum = 0; for (int num : nums) { if (currentSum + num > maxSum) { subarraysNeeded++; currentSum = num; } else { currentSum += num; } } return subarraysNeeded <= k; }}Complexity
Time
O(n * log(S)), where `n` is the length of the array and `S` is the sum of its elements. The binary search performs `O(log(S))` iterations, and each involves a linear `O(n)` scan of the array.
Space
O(1), as we only use a few variables to manage the binary search and the feasibility check.
Trade-offs
Pros
Extremely efficient with a time complexity of
O(n * log(S)).Uses constant extra space, making it very memory-efficient.
It's a powerful and common technique for solving 'minimax' or 'maximin' type problems.
Cons
The approach can be less intuitive to discover compared to a direct DP solution.
It relies on correctly identifying the monotonic property of the problem.
Solutions
Solution
class Solution {public int splitArray(int[] nums, int k) { int left = 0, right = 0; for (int x : nums) { left = Math.max(left, x); right += x; } while (left < right) { int mid = (left + right) >> 1; if (check(nums, mid, k)) { right = mid; } else { left = mid + 1; } } return left; }private boolean check(int[] nums, int mx, int k) { int s = 1 << 30, cnt = 0; for (int x : nums) { s += x; if (s > mx) { ++cnt; s = x; } } return cnt <= k; }}/** * @param {number[]} nums * @param {number} k * @return {number} */ var splitArray = function ( nums , k ) { let l = Math . max (... nums ); let r = nums . reduce (( a , b ) => a + b ); const check = mx => { let [ s , cnt ] = [ 0 , 0 ]; for ( const x of nums ) { s += x ; if ( s > mx ) { s = x ; if ( ++ cnt === k ) return false ; } } return true ; }; while ( l < r ) { const mid = ( l + r ) >> 1 ; if ( check ( mid )) { r = mid ; } else { l = mid + 1 ; } } return l ; };class Solution {public: int splitArray(vector<int> &nums, int k) { int left = 0, right = 0; for (int &x : nums) { left = max(left, x); right += x; } auto check = [&](int mx) { int s = 1 << 30, cnt = 0; for (int &x : nums) { s += x; if (s > mx) { s = x; ++cnt; } } return cnt <= k; }; while (left < right) { int mid = (left + right) >> 1; if (check(mid)) { right = mid; } else { left = mid + 1; } } return left; }};class Solution: def splitArray(self, nums: List[int], k: int) -> int: def check(mx): s, cnt = inf, 0 for x in nums: s += x if s > mx: s = x cnt += 1 return cnt <= k left, right = max(nums), sum(nums) return left + bisect_left(range(left, right + 1), True, key=check)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.