Binary-Search Partition

What is this?

Both problems cut an array into k 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 + 1 in one midpoint and not the other is not a stylistic choice — it is what stops an infinite loop. When feasibility means "move lo up", lo and hi eventually sit adjacent, mid rounds down to lo, and lo = mid changes nothing: the loop spins forever. Biasing the midpoint upward with (lo + hi + 1) // 2 fixes it. The rule is simple and worth memorising: the branch that assigns mid to lo needs the + 1; the branch that assigns mid to hi must not have it.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: when the question is "the best possible worst piece", guess the answer and verify it greedily. The verification is linear and obvious; the search around it is five lines.

1. Minimise the largest

def feasible(cap):
    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.

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)
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 friends means the chocolate is divided into k + 1 parts and one of them is yours. And the midpoint carries the + 1.

Leftover pieces at the end are simply discarded in the feasibility check — they can always be attached to the last piece, which only makes it larger and therefore still valid.

3. A 30-second worked example (minimise the largest)

nums = [7, 2, 5, 10, 8], k = 2. Search range is [10, 32].

mid = 21   fill: 7+2+5 = 14, +10 = 24 > 21 → new piece
                 10+8 = 18                        2 pieces ≤ 2  ✓   hi = 21
mid = 15   fill: 7+2+5 = 14, +10 = 24 > 15 → new piece
                 10, +8 = 18 > 15 → new piece     3 pieces > 2  ✗   lo = 16
mid = 18   fill: 7+2+5 = 14, +10 > 18 → new piece
                 10+8 = 18                        2 pieces ≤ 2  ✓   hi = 18
mid = 17   fill: 7+2 = 9, +5 = 14, +10 > 17 → new
                 10, +8 = 18 > 17 → new           3 pieces > 2  ✗   lo = 18

lo == hi == 18       → split as [7,2,5] and [10,8]

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

Cut into k + 1 contiguous pieces maximising the smallest total. Binary-search the minimum, cutting as soon as each piece qualifies.
Pattern: maximise the minimum. Target: O(n log(sum)) time, O(1) space.

▶ Split Array Largest Sum

Split into k contiguous subarrays minimising the largest sum. Binary-search the cap, filling each piece until it would overflow.
Pattern: minimise the maximum. Target: O(n log(sum)) time, O(1) space.

6. Common pitfalls 🚫

• Dropping the + 1 in 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 k pieces in Divide Chocolate. k friends means k + 1 pieces.
• Starting the search at 0 or 1. max(nums) and min(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, it is O(n²k), and it is the slower answer.

7. Key takeaways

1. Guess the answer and verify it — this whole family avoids a table entirely.
2. Monotonic feasibility is the licence to binary-search. Say why it holds.
3. The two directions are mirrors, and the three differences between them are all forced.
4. + 1 belongs to the branch that assigns mid to lo — nowhere else.
5. Bounds are provable, not arbitrary. A single element cannot be split; everything in one piece always works.
6. The greedy check is linear and boring, which is exactly what you want inside a search.
7. Why interviewers like it: the pair tests whether you learned a template or a technique, and the + 1 shows instantly which.

Order: Divide Chocolate → Split Array Largest Sum.