Split Array Largest Sum - Solution & Explanation
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] 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)
Approach Overview
Problem Overview: Given an integer array nums and an integer k, split the array into k non-empty contiguous subarrays. The goal is to minimize the largest sum among these subarrays. You must decide where to split so that the maximum subarray sum is as small as possible.
Approach 1: Dynamic Programming with Prefix Sum (O(nĀ² * k) time, O(n * k) space)
This method builds the solution by considering every possible split position. Use a prefix sum array to compute subarray sums in O(1). Let dp[i][j] represent the minimum possible largest subarray sum when splitting the first i elements into j parts. For each state, iterate over all previous split points p and minimize max(dp[p][j-1], sum(p+1..i)). The prefix sum array avoids recomputing sums repeatedly. This approach guarantees the optimal answer but becomes expensive for large n because every state checks multiple partitions.
Approach 2: Binary Search with Greedy Split (O(n log(sum(nums))) time, O(1) space)
The key observation: the answer lies between max(nums) and sum(nums). Instead of testing every partition, perform binary search on this range. For a candidate maximum sum mid, scan the array and greedily form subarrays while the running sum stays ā¤ mid. When the sum exceeds mid, start a new subarray. This greedy check runs in O(n) and tells you how many subarrays are required. If more than k subarrays are needed, the limit is too small; increase the search range. Otherwise, try a smaller maximum. This technique combines greedy validation with binary search to efficiently converge on the optimal value.
Recommended for interviews: The binary search + greedy solution is what most interviewers expect. It reduces the search space dramatically and runs in O(n log(sum)). The dynamic programming approach shows strong understanding of partition DP and is useful for reasoning about the problem, but the optimized binary search approach demonstrates algorithmic insight and scalability.
Approach 1: Binary Search with Greedy Split
This approach uses binary search to efficiently find the minimized largest sum. The range for binary search is between the maximum single element in the array (lower bound) and the sum of the array (upper bound). For each candidate middle value in the binary search, we check if it's possible to partition the array into k or fewer subarrays such that none has a sum greater than this candidate. This check is done through a greedy approach: we iterate over the array, adding elements to a running sum until adding another element would exceed the candidate sum, at which point we start a new subarray.
The C implementation first calculates the sum and maximum value of the given array. These provide the binary search boundaries. The implementation then uses a while loop for the binary search, updating the boundaries based on whether the current guess can divide the array into ā¤ k subarrays. The function finally returns the minimized largest sum.
Complexity
Time Complexity: O(n log(sum - max)), where sum is the total sum of array and max is the maximum element.
Space Complexity: O(1), as no additional space proportional to input size is used.
Approach 2: Dynamic Programming
We can also use dynamic programming to solve this problem by maintaining a DP table where dp[i][j] means the minimum largest sum for splitting the first i elements into j subarrays. The recurrence is based on considering different potential previous cut positions and calculating the maximum sum for the last subarray in each case, iterating across feasible positions.
This C solution implements dynamic programming by using a dp table initialized with INT_MAX, with the exception of dp[0][0] set to 0 allowing split calculations. The recurrence is used to iterate over each possible partition configuration, minimizing the result stored at dp[k][numsSize].
Complexity
Time Complexity: O(n^2 * k), as each subproblem depends on earlier solutions.
Space Complexity: O(n*k), for the dp table.
Approach 3: Binary Search
We notice that the larger the maximum sum of the subarrays, the fewer the number of subarrays. When there is a maximum sum of the subarrays that meets the condition, then a larger maximum sum of the subarrays will definitely meet the condition. This means that we can perform a binary search for the maximum sum of the subarrays to find the smallest value that meets the condition.
We define the left boundary of the binary search as left = max(nums), and the right boundary as right = sum(nums). Then for each step of the binary search, we take the middle value mid = \lfloor \frac{left + right}{2} \rfloor, and then determine whether there is a way to split the array so that the maximum sum of the subarrays does not exceed mid. If there is, it means that mid might be the smallest value that meets the condition, so we adjust the right boundary to mid. Otherwise, we adjust the left boundary to mid + 1.
How do we determine whether there is a way to split the array so that the maximum sum of the subarrays does not exceed mid? We can use a greedy method, traverse the array from left to right, and add the elements of the array to the subarray one by one. If the current sum of the subarray is greater than mid, then we add the current element to the next subarray. If we can split the array into no more than k subarrays, and the maximum sum of each subarray does not exceed mid, then mid is the smallest value that meets the condition. Otherwise, mid does not meet the condition.
The time complexity is O(n times log m), and the space complexity is O(1). Here, n and m are the length of the array and the sum of all elements in the array, respectively.
Code
Python
Java
C++
Go
JavaScript
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search with Greedy Split | Time Complexity: O(n log(sum - max)), where sum is the total sum of array and max is the maximum element. |
| Dynamic Programming | Time Complexity: O(n^2 * k), as each subproblem depends on earlier solutions. |
| Binary Search | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Sum | O(nĀ² * k) | O(n * k) | Useful for understanding partition DP or when constraints are small |
| Binary Search with Greedy Split | O(n log(sum(nums))) | O(1) | Optimal solution for large arrays and the expected interview approach |
Video Solution
BS 19. Painter's Partition and Split Array - Largest Sum ā¢ take U forward ā¢ 284,055 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Split Array Largest Sum easy or hard?
Split Array Largest Sum Python/Java solution
How to solve Split Array Largest Sum in O(n)?
What is the best approach for Split Array Largest Sum?
Is Split Array Largest Sum asked at Google/Amazon/Meta?
What data structure is used in Split Array Largest Sum?
What is the time complexity of Split Array Largest Sum?
Ready to solve this problem?
Practice Split Array Largest Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor