Split an array to minimise the largest part
Hard · Target 30 minutes · Binary search · Type asked atGoogle
Jane Street
Given an array nums of non-negative integers and an integer k,
split nums into exactly k non-empty contiguous parts so that the largest
part sum is as small as possible. Return that smallest possible largest sum.
Examples
| Input | Output | Why |
|---|---|---|
nums = [7, 2, 5, 10, 8], k = 2 | 18 | [7, 2, 5] and [10, 8]. |
nums = [1, 2, 3, 4, 5], k = 2 | 9 | [1, 2, 3] and [4, 5]. |
nums = [1, 4, 4], k = 3 | 4 | Each element alone. |
Constraints
- 1 ≤ k ≤ n ≤ 1000
- 0 ≤ nums[i] ≤ 10⁶
Hints
Hint 1
Trying every way to place k − 1 cuts is exponential, and a dynamic program over (position, parts) is O(k · n²). There is a faster way to think about it.
Hint 2
Turn the question round: given a limit L, can the array be split into at most k parts with every part summing to at most L? A greedy scan answers that in O(n).
Hint 3
Feasibility is monotone in L: if a limit works, every larger limit works. So binary search L between max(nums) and sum(nums) for the smallest feasible value.
Where people lose marks
- Starting the search at 0 or 1 instead of max(nums). Below the largest element no split is feasible, and the greedy check would loop or miscount.
- Counting parts from 0 rather than 1: the scan always has one part open.
- Searching for "exactly k" parts in the check. The greedy test answers "at most k", which is what makes it monotone.
- Overflow when summing large arrays in languages with 32-bit integers; use 64-bit totals.
Dry run on [7,2,5,10,8],2
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6nums70215210384lo10hi32k2
The answer lies between the largest element (10) and the total (32).
-
Step 2 / 6nums70215210384lo10hi32mid21parts2
Try a limit of 21: the greedy scan needs 2 parts. That is at most 2, so 21 works; look for something smaller.
-
Step 3 / 6nums70215210384lo10hi21mid15parts3
Try a limit of 15: the greedy scan needs 3 parts. More than 2, so 15 is too small.
-
Step 4 / 6nums70215210384lo16hi21mid18parts2
Try a limit of 18: the greedy scan needs 2 parts. That is at most 2, so 18 works; look for something smaller.
-
Step 5 / 6nums70215210384lo16hi18mid17parts3
Try a limit of 17: the greedy scan needs 3 parts. More than 2, so 17 is too small.
-
Step 6 / 6nums70215210384answer18
The range has closed on 18, the smallest limit that allows 2 parts.
How to think about it
Optimisation problems of the form "minimise the maximum" often become easy when the answer is
guessed and checked. Fix a limit L and ask whether nums can be cut into at
most k parts, each with sum at most L.
- Check greedily. Scan from the left, adding elements to the current part until the next
one would push it over
L; then start a new part. Making each part as long as possible can only reduce the number of parts needed, so the greedy count is the minimum. - Search the limit. Feasibility is monotone in
L, the smallest possible answer ismax(nums)(some part contains the largest element) and the largest issum(nums)(one part). Binary search finds the smallest feasible limit inO(log sum)checks.
"At most k parts" and "exactly k parts" give the same answer here: a split into fewer parts can be
refined by cutting any part with two or more elements, which never increases the largest sum, and
k ≤ n guarantees enough elements.
Shipping packages within d days, painting boards with k painters, Koko eating bananas, allocating pages to students: all the same problem. When a question asks for the smallest capacity that makes something possible, look for a monotone feasibility check.
Complexity. Time O(n log(sum)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def split_largest_sum(nums, k):
def parts_needed(limit): # greedy: make every part as long as the limit allows
parts, cur = 1, 0
for x in nums:
if cur + x > limit:
parts += 1
cur = x
else:
cur += x
return parts
lo, hi = max(nums), sum(nums) # some part holds the largest element; one part holds all
while lo < hi:
mid = (lo + hi) // 2
if parts_needed(mid) <= k:
hi = mid # feasible: try smaller
else:
lo = mid + 1
return lo#include <vector>
#include <algorithm>
#include <numeric>
long long solve(const std::vector<int>& nums, int k) {
auto partsNeeded = [&](long long limit) { // greedy: longest parts within the limit
int parts = 1;
long long cur = 0;
for (int x : nums) {
if (cur + x > limit) { ++parts; cur = x; } else cur += x;
}
return parts;
};
long long lo = *std::max_element(nums.begin(), nums.end());
long long hi = std::accumulate(nums.begin(), nums.end(), 0LL);
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (partsNeeded(mid) <= k) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
public long splitLargestSum(int[] nums, int k) {
long lo = 0, hi = 0;
for (int x : nums) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (partsNeeded(nums, mid) <= k) hi = mid; else lo = mid + 1;
}
return lo;
}
private int partsNeeded(int[] nums, long limit) { // greedy: longest parts within the limit
int parts = 1;
long cur = 0;
for (int x : nums) {
if (cur + x > limit) { parts++; cur = x; } else cur += x;
}
return parts;
}
}function splitLargestSum(nums, k) {
const partsNeeded = limit => { // greedy: make every part as long as the limit allows
let parts = 1, cur = 0;
for (const x of nums) {
if (cur + x > limit) { parts++; cur = x; } else cur += x;
}
return parts;
};
let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (partsNeeded(mid) <= k) hi = mid; else lo = mid + 1;
}
return lo;
}fn solve(nums: &[i64], k: i64) -> i64 {
let parts_needed = |limit: i64| { // greedy: longest parts within the limit
let (mut parts, mut cur) = (1i64, 0i64);
for &x in nums {
if cur + x > limit {
parts += 1;
cur = x;
} else {
cur += x;
}
}
parts
};
let (mut lo, mut hi) = (*nums.iter().max().unwrap(), nums.iter().sum::<i64>());
while lo < hi {
let mid = lo + (hi - lo) / 2;
if parts_needed(mid) <= k {
hi = mid;
} else {
lo = mid + 1;
}
}
lo
}solve :: [Int] -> Int -> Int
solve nums k = search (maximum nums) (sum nums)
where
-- greedy: make every part as long as the limit allows; returns the number of parts
partsNeeded limit = fst (foldl step (1, 0) nums)
where
step (parts, cur) x
| cur + x > limit = (parts + 1, x)
| otherwise = (parts, cur + x)
search lo hi
| lo >= hi = lo
| partsNeeded mid <= k = search lo mid
| otherwise = search (mid + 1) hi
where mid = (lo + hi) `div` 2Variants to try
- Return the cuts as well: rerun the greedy scan at the final limit and record where parts start.
- Minimise the largest part when the parts need not be contiguous: that is multiprocessor scheduling, NP-hard in general, usually answered with a heap-based heuristic.
- Maximise the smallest part instead: the same search with the inequality reversed.
- k very large and n small: a dynamic program over prefix sums may be clearer, O(k · n²).
Next problems
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem →Write a solution and run it against the real test table.
Keep going
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.