</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Binary Search on the Partition: minimise the largest vs maximise the smallest (flowchart)

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.


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].

Minimise the largest piece: binary-search trace to 18

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 + 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 cuts make 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 for Split Array Largest Sum. It is O(n²·m) time (about 2.5e7 steps at n = 1000, m = 50) and O(n·m) space, or O(n) with rolling rows. The binary search is far cheaper.

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.

Core idea: You can't search the cuts directly, so search the answer instead. Guess a target sweetness x for the worst piece; greedily walk left-to-right, closing off a new piece every time its running sum reaches x, and count how many such pieces you got. If you can carve at least k+1 pieces, each of sum at least x, then x is achievable, and so is anything smaller. Binary-search for the largest achievable x.

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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.