Binary-Search Partition
What is this?
Both problems cut an array into contiguous pieces and ask about the extreme piece: the largest in one, the smallest in the other. Neither is a DP table. You guess the answer, check it with a linear greedy, and let binary search find the boundary where feasible turns infeasible.
Learning them as a pair is the point: they are the same algorithm reflected, and the two reflections differ in three specific places.
Fun fact: the
+ 1in one midpoint and not the other is not a stylistic choice. It is what stops an infinite loop. When feasibility means "moveloup",loandhieventually sit adjacent,midrounds down tolo, andlo = midchanges nothing: the loop spins forever. Biasing the midpoint upward with(lo + hi + 1) // 2fixes it. The rule is simple and worth memorising: the branch that assignsmidtoloneeds the+ 1; the branch that assignsmidtohimust not have it.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: when the question is "the best possible worst piece", guess the answer and verify it greedily. The verification is one linear pass; the search around it is five lines.
1. Minimise the largest
def feasible(cap): # k = number of pieces allowed
pieces, cur = 1, 0
for x in nums:
if cur + x > cap: pieces += 1; cur = x # start a new piece
else: cur += x
return pieces <= k
lo, hi = max(nums), sum(nums) # the bounds are not arbitrary
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid): hi = mid
else: lo = mid + 1
return lo
The bounds carry an argument each. max(nums) is the floor because a single element can never be split, and sum(nums) is the ceiling because one piece holding everything always works. Between them, feasibility is monotonic: if a cap works, every larger cap works, which is the only condition binary search needs. The check counts "at most k pieces" even though the problem says exactly k. With k <= n and non-negative values the two give the same answer, because any piece can be cut further without raising the maximum.
The search runs O(log(sum - max)) iterations of an O(n) check.
2. Maximise the smallest
def feasible(m):
pieces, cur = 0, 0
for s in sweetness:
cur += s
if cur >= m: pieces += 1; cur = 0 # cut as soon as the piece qualifies
return pieces >= k + 1 # k friends → k+1 pieces
lo, hi = min(sweetness), sum(sweetness) // (k + 1) # the best minimum cannot beat an even split
while lo < hi:
mid = (lo + hi + 1) // 2 # ← the +1
if feasible(mid): lo = mid
else: hi = mid - 1
return lo
Three differences from the first, and all three are forced. The greedy cuts as soon as the piece qualifies rather than as late as possible. The comparison is >= against a count that must be at least k + 1, because k cuts make k + 1 pieces. And the midpoint carries the + 1. Each chunk is positive, so every piece is non-empty. For [1..9] with k = 5 (6 pieces), a target of 6 yields 6 pieces and a target of 7 yields only 5, so the answer is 6.
A leftover tail that never reaches the target is ignored in the check. It can be merged into the last piece, which only makes that piece larger and so still valid.
3. A 30-second worked example (minimise the largest)
nums = [7, 2, 5, 10, 8], k = 2. Search range is [10, 32].
Note that 18 is feasible and 17 is not. That single boundary is the answer, and the greedy never had to be clever. It just fills each piece until adding the next element would overflow, which is optimal for this question precisely because pieces must be contiguous.
4. Where you'll actually meet this
- Capacity planning. Fewest shipments, machines or workers to finish under a deadline is this exact search.
- Load balancing. Partitioning ordered work across servers so the busiest is as idle as possible.
- Pagination and layout. Splitting content into pages whose heaviest page is minimal.
- Resource fairness. Maximising the smallest share is the standard formulation of a fair split.
- Rate and quota design. Finding the smallest limit under which every consumer still fits.
5. Problems in this chapter
Divide Chocolate
Make k cuts, giving k + 1 contiguous pieces, maximising the smallest total. Binary-search the minimum, cutting as soon as each piece qualifies. The brute force over cut placements is C(n-1, k) partitions; for n = 30, k = 15 that is about 78 million.
Pattern: maximise the minimum. Target: O(n log(sum)) time, O(1) space.
Split Array Largest Sum
Split into m contiguous subarrays minimising the largest sum (the lesson calls the piece count m; this page calls it k). Binary-search the cap, filling each piece until it would overflow.
Pattern: minimise the maximum. Target: O(n log(sum - max)) time, O(1) space.
6. Common pitfalls
- Dropping the
+ 1in the midpoint of the maximise-the-minimum search, which loops forever. - Adding it to the other one, which overshoots and returns an infeasible answer.
- Counting
kpieces in Divide Chocolate.kcuts makek + 1pieces. - Starting the search at
0or1.max(nums)andmin(sweetness)are provable floors and save iterations. - Cutting greedily in the wrong direction. Minimising the maximum fills as much as possible; maximising the minimum cuts as soon as it can.
- Not stating why feasibility is monotonic. Without it, binary search is unjustified even when it works.
- Reaching for a DP table. It exists for Split Array Largest Sum. It is
O(n²·m)time (about 2.5e7 steps atn = 1000,m = 50) andO(n·m)space, orO(n)with rolling rows. The binary search is far cheaper.
7. Key takeaways
- Guess the answer and verify it. This whole family avoids a table entirely.
- Monotonic feasibility is the licence to binary-search. Say why it holds.
- The two directions are mirrors, and the three differences between them are all forced.
+ 1belongs to the branch that assignsmidtolo, nowhere else.- Bounds are provable, not arbitrary. A single element cannot be split; everything in one piece always works.
- The greedy check is linear and boring, which is exactly what you want inside a search.
- Why interviewers like it: the pair tests whether you learned a template or a technique, and the
+ 1shows instantly which.
Order: Divide Chocolate → Split Array Largest Sum.
Core idea: You can't search the cuts directly, so search the answer instead. Guess a target sweetness
xfor the worst piece; greedily walk left-to-right, closing off a new piece every time its running sum reachesx, and count how many such pieces you got. If you can carve at least k+1 pieces, each of sum at leastx, thenxis achievable, and so is anything smaller. Binary-search for the largest achievablex.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson