Split Array Largest Sum — Solution in Python, Java & C++
Split Array Largest Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Split Array Largest Sum is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Greedy, Binary Search
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Split nums into k non-empty contiguous subarrays so that the largest subarray sum is as small as possible.
Return that minimised largest sum.
Example 1
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: [7,2,5] and [10,8] give sums 14 and 18.
Example 2
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: [1,2,3] and [4,5].
Example 3
Input: nums = [1,4,4], k = 3
Output: 4
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10000001 <= k <= nums.length
Hints for Split Array Largest Sum
Hint 1
If a cap on the largest sum is achievable with
kparts, any larger cap is too — the feasibility is monotone.Hint 2
For a candidate cap, greedily extend each part until the next element would overflow it.
Hint 3
The search range runs from the largest element to the total sum.
How to solve Split Array Largest Sum
Binary search the answer. For a candidate cap, the greedy that keeps extending a part until it would overflow produces the fewest parts possible, so comparing that count with k decides feasibility exactly.
Approach
- Set
lotomax(nums)— no part can be smaller than its largest element — andhito the total. need(cap): sweep once, starting a new part whenever the next element would push the running sum pastcap.- Binary search the smallest
capwithneed(cap) <= k.
Why it works
The greedy is optimal for a fixed cap: closing a part before it must can never reduce the number of parts, since the deferred element still has to go somewhere later. Raising the cap lets each part hold more, so need is non-increasing. And using fewer than k parts is fine — a part can always be split further without raising the maximum.
Complexity
- Time —
O(n log S) where S is the total sum - Space —
O(1)
Pitfalls
- The classic
O(n² k)dynamic program also solves it but is far slower here. lomust start atmax(nums), or the greedy can loop on an element that fits in no part.need(cap) <= k, not== k— extra splits are always available.
Reference solution
Python
from typing import List
def splitArray(nums: List[int], k: int) -> int:
lo, hi = max(nums), sum(nums)
def need(cap: int) -> int:
cnt, cur = 1, 0
for x in nums:
if cur + x > cap:
cnt += 1
cur = 0
cur += x
return cnt
while lo < hi:
mid = (lo + hi) // 2
if need(mid) <= k:
hi = mid
else:
lo = mid + 1
return loJava
private static int partsNeeded(int[] nums, int cap) {
int cnt = 1, cur = 0;
for (int x : nums) {
if (cur + x > cap) {
cnt++;
cur = 0;
}
cur += x;
}
return cnt;
}
public static int splitArray(int[] nums, int k) {
int lo = 0;
long hi = 0;
for (int x : nums) {
lo = Math.max(lo, x);
hi += x;
}
int right = (int) hi;
while (lo < right) {
int mid = lo + (right - lo) / 2;
if (partsNeeded(nums, mid) <= k) right = mid; else lo = mid + 1;
}
return lo;
}C++
static int partsNeeded(vector<int>& nums, int cap) {
int cnt = 1, cur = 0;
for (int x : nums) {
if (cur + x > cap) {
cnt++;
cur = 0;
}
cur += x;
}
return cnt;
}
int splitArray(vector<int>& nums, int k) {
int lo = 0;
long long total = 0;
for (int x : nums) {
lo = max(lo, x);
total += x;
}
int hi = (int) total;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (partsNeeded(nums, mid) <= k) hi = mid; else lo = mid + 1;
}
return lo;
}JavaScript
var splitArray = function(nums, k) {
var lo = 0, hi = 0, i;
for (i = 0; i < nums.length; i++) {
if (nums[i] > lo) lo = nums[i];
hi += nums[i];
}
var need = function(cap) {
var cnt = 1, cur = 0;
for (var j = 0; j < nums.length; j++) {
if (cur + nums[j] > cap) { cnt++; cur = 0; }
cur += nums[j];
}
return cnt;
};
while (lo < hi) {
var mid = Math.floor((lo + hi) / 2);
if (need(mid) <= k) hi = mid; else lo = mid + 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming