Split Array Largest Sum solution and explanation
Google
Infosys
Deloitte
9 more videos on this problem
BS 19. Painter's Partition and Split Array - Largest Sumtake U forward · 11:20 · 284K views
Split Array Largest Sum - Leetcode 410 - PythonNeetCode · 16:51 · 133K views
Split Array Largest Sum | Leetcode 410. Daily Challenge | Binary Search Hard Interview ProblemCode with Alisha · 27:25 · 19K views
LeetCode 410. Split Array Largest Sum Explanation and Solutionhappygirlzt · 7:46 · 15K views
410. Split Array Largest Sum | Binary Search Series | Coders CampCoders Camp · 10:53 · 5K views
Split Array Largest Sum | Leetcode 410 | Range Based Binary Search 🔥🔥 | Live coding sessionCoding Decoded · 15:02 · 3K views
Leetcode 410 (HARD) | Split Array Largest SumTech Traversal · 19:11 · 3K views
SPLIT ARRAY LARGEST SUM | LEETCODE # 410 | PYTHON BINARY SEARCHCracking FAANG · 32:12 · 2K views
Split Array Largest Sum | Problem - 410 | Complete Algorithm | LeetCode | CoderJCoderJ · 15:15 · 1K views
410. Split Array Largest Sum (Leetcode Hard)Programming Live with Larry · 10:10 · 1K views
The problem
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.
def splitArray(nums, k):
left, right = max(nums), sum(nums)
while left < right:
mid = (left + right) // 2
current_sum, pieces = 0, 1
for num in nums:
if current_sum + num > mid:
current_sum = num
pieces += 1
else:
current_sum += num
if pieces > k:
left = mid + 1
else:
right = mid
return leftpublic class Solution {
public int splitArray(int[] nums, int k) {
int max = 0;
int sum = 0;
for (int num : nums) {
max = Math.max(max, num);
sum += num;
}
int left = max, right = sum;
while (left < right) {
int mid = left + (right - left) / 2;
int currentSum = 0;
int pieces = 1;
for (int num : nums) {
if (currentSum + num > mid) {
currentSum = num;
pieces++;
} else {
currentSum += num;
}
}
if (pieces > k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int splitArray(vector<int>& nums, int k) {
int maxElem = *max_element(nums.begin(), nums.end());
int sum = accumulate(nums.begin(), nums.end(), 0);
int left = maxElem, right = sum;
while (left < right) {
int mid = left + (right - left) / 2;
int currentSum = 0, pieces = 1;
for (int num : nums) {
if (currentSum + num > mid) {
currentSum = num;
pieces++;
} else {
currentSum += num;
}
}
if (pieces > k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}var splitArray = function(nums, k) {
let left = Math.max(...nums);
let right = nums.reduce((a, b) => a + b, 0);
while (left < right) {
let mid = Math.floor((left + right) / 2);
let currentSum = 0;
let pieces = 1;
for (let num of nums) {
if (currentSum + num > mid) {
currentSum = num;
pieces++;
} else {
currentSum += num;
}
}
if (pieces > k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
};#include <stdio.h>
int splitArray(int* nums, int numsSize, int k) {
int max = 0, sum = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > max) max = nums[i];
sum += nums[i];
}
int left = max, right = sum;
while (left < right) {
int mid = (left + right) / 2;
int currentSum = 0, pieces = 1;
for (int i = 0; i < numsSize; i++) {
if (currentSum + nums[i] > mid) {
currentSum = nums[i];
pieces++;
} else {
currentSum += nums[i];
}
}
if (pieces > k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}public class Solution {
public int SplitArray(int[] nums, int k) {
int left = nums.Max();
int right = nums.Sum();
while (left < right) {
int mid = (left + right) / 2;
int currentSum = 0, pieces = 1;
foreach (int num in nums) {
if (currentSum + num > mid) {
currentSum = num;
pieces++;
} else {
currentSum += num;
}
}
if (pieces > k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}The Python function performs binary search on the possible maximum subarray sum. The function uses a greedy strategy to divide the array, updating the search boundaries according to how many pieces are formed. The minimized largest sum is returned after the search completes.
Time Complexity: O(n log(sum - max)).
Space Complexity: O(1).
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.
def splitArray(nums, k):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
dp = [[float('inf')] * (n + 1) for _ in range(k + 1)]
dp[0][0] = 0
for j in range(1, k + 1):
for i in range(1, n + 1):
for p in range(i):
dp[j][i] = min(dp[j][i], max(dp[j - 1][p], prefix[i] - prefix[p]))
return dp[k][n]import java.util.Arrays;
public class Solution {
public int splitArray(int[] nums, int k) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int[][] dp = new int[k + 1][n + 1];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
}
dp[0][0] = 0;
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= n; i++) {
for (int p = 0; p < i; p++) {
dp[j][i] = Math.min(dp[j][i], Math.max(dp[j - 1][p], prefix[i] - prefix[p]));
}
}
}
return dp[k][n];
}
}#include <vector>
#include <limits.h>
using namespace std;
int splitArray(vector<int>& nums, int k) {
int n = nums.size();
vector<vector<int>> dp(k + 1, vector<int>(n + 1, INT_MAX));
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
dp[0][0] = 0;
for (int j = 1; j <= k; ++j) {
for (int i = 1; i <= n; ++i) {
for (int p = 0; p < i; ++p) {
dp[j][i] = min(dp[j][i], max(dp[j - 1][p], prefix[i] - prefix[p]));
}
}
}
return dp[k][n];
}var splitArray = function(nums, k) {
const n = nums.length;
const prefix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
const dp = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(Infinity));
dp[0][0] = 0;
for (let j = 1; j <= k; j++) {
for (let i = 1; i <= n; i++) {
for (let p = 0; p < i; p++) {
dp[j][i] = Math.min(dp[j][i], Math.max(dp[j - 1][p], prefix[i] - prefix[p]));
}
}
}
return dp[k][n];
};#include <stdio.h>
#include <limits.h>
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int splitArray(int* nums, int numsSize, int k) {
int dp[k + 1][numsSize + 1];
int prefix[numsSize + 1];
prefix[0] = 0;
for (int i = 1; i <= numsSize; ++i){
prefix[i] = prefix[i - 1] + nums[i - 1];
}
for (int i = 0; i <= numsSize; ++i) {
dp[0][i] = INT_MAX;
}
dp[0][0] = 0;
for (int j = 1; j <= k; ++j) {
for (int i = 0; i <= numsSize; ++i) {
dp[j][i] = INT_MAX;
for (int p = 0; p < i; ++p) {
dp[j][i] = min(dp[j][i], max(dp[j - 1][p], prefix[i] - prefix[p]));
}
}
}
return dp[k][numsSize];
}using System;
public class Solution {
public int SplitArray(int[] nums, int k) {
int n = nums.Length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int[,] dp = new int[k + 1, n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i, j] = int.MaxValue;
}
}
dp[0, 0] = 0;
for (int j = 1; j <= k; j++) {
for (int i = 1; i <= n; i++) {
for (int p = 0; p < i; p++) {
dp[j, i] = Math.Min(dp[j, i], Math.Max(dp[j - 1, p], prefix[i] - prefix[p]));
}
}
}
return dp[k, n];
}
}Python's approach uses a dp matrix and a prefix sum array to build up subproblem solutions, using nested iterations to attempt each possible positioning of subarray cuts. This approach efficiently builds upon previous solutions to yield the minimized largest subarray sum possible.
Time Complexity: O(n^2 * k).
Space Complexity: O(n*k).
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.
function splitArray(nums: number[], k: number): number {
let l = Math.max(...nums);
let r = nums.reduce((a, b) => a + b);
const check = (mx: number) => {
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;
}func splitArray(nums []int, k int) int {
left, right := 0, 0
for _, x := range nums {
left = max(left, x)
right += x
}
return left + sort.Search(right-left, func(mx int) bool {
mx += left
s, cnt := 1<<30, 0
for _, x := range nums {
s += x
if s > mx {
s = x
cnt++
}
}
return cnt <= k
})
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search with Greedy Split | Time Complexity: O(n log(sum - max)). |
| Dynamic Programming | Time Complexity: O(n^2 * k). |
| Binary Search | – |
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 |
Frequently asked questions
Is Split Array Largest Sum easy or hard?
Split Array Largest Sum is classified as Hard because it requires recognizing the 'binary search on answer' pattern combined with a greedy feasibility check. Many candidates initially attempt dynamic programming before discovering the optimized approach.
Split Array Largest Sum Python/Java solution
Most implementations follow the binary search + greedy strategy. Define the search range between max(nums) and sum(nums), then repeatedly check if the array can be split into at most k parts while keeping each subarray sum under the candidate value.
How to solve Split Array Largest Sum in O(n)?
A strict O(n) algorithm is not known for the general problem. The best practical approach is O(n log(sum(nums))) using binary search combined with a greedy check that counts how many subarrays are required for a given maximum sum.
What is the best approach for Split Array Largest Sum?
Binary search with a greedy feasibility check is the most efficient approach. Search the answer between max(nums) and sum(nums), and verify each candidate by greedily forming subarrays without exceeding the limit. This runs in O(n log(sum(nums))) time and O(1) space.
Is Split Array Largest Sum asked at Google/Amazon/Meta?
Split Array Largest Sum is a well-known hard interview problem frequently discussed in preparation for companies like Google, Amazon, and Meta. It tests binary search on answer space, greedy validation, and dynamic programming concepts.
What data structure is used in Split Array Largest Sum?
The solution mainly relies on arrays and simple counters. The dynamic programming version uses a 2D DP table and a prefix sum array for fast subarray sum queries, while the optimal solution uses only variables during a linear scan.
What is the time complexity of Split Array Largest Sum?
The optimal solution runs in O(n log(sum(nums))) time because binary search is applied over the range of possible maximum sums and each feasibility check scans the array once. The dynamic programming approach is slower at O(n² * k) time and O(n * k) space.