O(n log sum) O(1)
Intuition
The answer (a maximum subarray sum) lies between max(nums) and sum(nums). For a candidate limit, greedily count how many subarrays are needed; binary search the smallest limit that fits within k.
Explanation
Search the answer, not the array
The minimized largest sum is somewhere in [max(nums), sum(nums)]. This value is monotonic: a larger limit needs fewer subarrays. So binary search it — for a candidate limit, greedily pack elements until adding one would exceed limit, starting a new subarray each time, and count how many subarrays result.
If count <= k, the limit is feasible → try smaller (hi = mid); else lo = mid + 1.
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo+hi)//2
if canSplit(mid) <= k: hi = mid
else: lo = mid+1
return lo
Worked example
[7,2,5,10,8], k=2 → answer 18 (splits [7,2,5] and [10,8]).
Complexity
- Time: O(n log(sum)).
- Space: O(1).
Implementation
class Solution {
public int splitArray(int[] nums, int k) {
int lo = 0, hi = 0;
for (int x : nums) {
lo = Math.max(lo, x);
hi += x;
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canSplit(nums, k, mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
private boolean canSplit(int[] nums, int k, int limit) {
int subs = 1, cur = 0;
for (int x : nums) {
if (cur + x > limit) {
subs++;
cur = x;
if (subs > k) return false;
} else {
cur += x;
}
}
return true;
}
}