Loading…

mediumBinary SearchFrequently asked

Painter's Partition Problem

Q: How do you solve Painter's Partition Problem using the Linear Scan Over the Answer — Baseline approach?

When to use it: Lead with this to show you've identified the search space (the finishing time) and the painter-count check. Then flag that the scan range is sum(boards), which is too big. Start with the reframing: you're choosing a *number* — the time the slowest painter is allowed to take — and that number lives in `[max(boards), sum(boards)]`. The lower end is `max(boards)` because whoever paints the longest board needs at least that long; the upper end is `sum(boards)` because a single painter could do every board. **The feasibility check counts painters.** Fix a time cap `x`. Sweep the boards left to right with a running block sum. Add the current board; if that would exceed `x`, close the current painter's block and hand this board to a new painter. The painters opened is exactly the minimum needed under cap `x`, because the assignment is contiguous and lengths are non-negative — packing each painter as full as the cap allows minimizes how many painters you use. **Why greedy-fill is exact.** Within a contiguous block the running sum only grows, and pushing a painter to work right up to the cap never forces *more* painters downstream — it can only leave less for later, which helps. So 'fill to the cap, then cut' yields the fewest painters for that cap — a precise yes/no feasibility answer, not an estimate. **Why scanning upward is valid.** The first cap whose painter count is ≤ `k` is the minimum feasible time. Raising the cap only lets each painter absorb more boards, so it never increases the painter count — meaning once a cap works, all larger caps work. That 'larger cap ⇒ never worse' fact is the monotonicity we'll exploit next. **Why we don't ship this.** `sum(boards)` can reach `10⁵ · 10⁴ = 10⁹`. An O(n) check run a billion times is hopeless. Because feasibility is monotone in the cap, binary-search the boundary instead of walking to it. Time complexity: O(n · sum). Space complexity: O(1).

Binary Search · 13 of 16 · 11 min

You are given an array boards of n integers where boards[i] is the length of the i-th board, and an integer k — the number of painters.

Each painter paints a contiguous sequence of boards, painting 1 unit of board length takes 1 unit of time, and all painters work simultaneously.

Assign the boards so that the time to paint all boards is minimized. The total time is the time taken by the painter who finishes last (the largest block of lengths). Return that minimized time.

In plain English

Cut the board array into k contiguous blocks and hand one block to each painter. Since they paint in parallel, the project finishes when the painter with the largest block finishes. You want the cut that minimizes that largest block sum — a single number, which is the binary-search-on-the-answer tell.

Examples

Example 1

Input: boards = [10, 20, 30, 40], k = 2
Output: 60
Note: Cut [10, 20, 30] | [40] → block sums 60 and 40 → the slower painter takes 60. Any other 2-way cut is worse (e.g. [10,20]|[30,40] → 70).

Example 2

Input: boards = [10, 10, 10, 10], k = 2
Output: 20
Note: Cut [10, 10] | [10, 10] → both painters take 20. Balanced split, minimized maximum 20.

Example 3

Input: boards = [5, 10, 30, 20, 15], k = 3
Output: 35
Note: Cut [5, 10] | [30] | [20, 15] → sums 15, 30, 35 → slowest painter takes 35, the best achievable.

Constraints

1 ≤ k ≤ n ≤ 10⁵
1 ≤ boards[i] ≤ 10⁴
Painters work in parallel; a painter's time equals the sum of lengths in its contiguous block
If a per-unit time t is given, multiply the result by t

Clarifying questions4First question: Can a painter skip around to non-adjacent boards?Explore questions

Q1.Can a painter skip around to non-adjacent boards?
No — each painter's boards are contiguous. That's the whole reason a one-pass greedy count works.
Q2.Do painters work in parallel or one after another?
In parallel. The finishing time is the maximum block sum, not the total. If it were sequential, the answer would just be sum(boards).
Q3.Is there a per-unit painting time?
If each unit length takes t time, solve for the min-max block sum first, then multiply by t at the end — it scales the answer linearly without changing the search.
Q4.Why is the smallest possible time max(board)?
Whoever paints the longest single board can't finish before that board is done, so no assignment beats max(board).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each painter paints a contiguous block of boards, so the finishing time is the largest block-length sum across the k painters. Binary-search that answer: for a candidate time limit x, greedily assign boards left to right and count how many painters x forces. 'Can k painters finish if nobody works more than x?' is monotonic in x, so binary search finds the smallest feasible x in O(n log(sum)). Bounds are [max(board), sum(boards)].

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize this as the same min-max-over-contiguous-groups problem as Allocate Pages, pin the answer bounds at [max(board), sum(boards)], and justify the monotone feasibility predicate before coding.

Where candidates slip

Sorting the boards (which destroys contiguity), using lo = 0, or moving the search the wrong way on a feasible mid because the minimize/maximize direction got flipped.

How to stand out

Name it explicitly: 'this is Allocate Pages / Split Array Largest Sum'. State that feasible(time) is monotone increasing, justify lo = max(board), and fold any per-unit time factor in at the very end.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan Over the Answer — Baseline	`O(n · sum)`	`O(1)`	Lead with this to show you've identified the search space (the finishing time) and the painter-count check. Then flag that the scan range is sum(boards), which is too big.	Read
2	Binary Search on the Finishing Time (Optimal)Optimal	`O(n log(sum))`	`O(1)`	The intended answer. Phrase it as 'feasible(time) is monotone, so binary-search the smallest feasible finishing time'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMinimize the time of the SLOWEST painterpainters needed with cap x ≤ k ?FeasibleInfeasibleExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan Over the Answer — Baseline

TimeO(n · sum)SpaceO(1)

Lead with this to show you've identified the search space (the finishing time) and the painter-count check. Then flag that the scan range is sum(boards), which is too big.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some finishing time between max(boards) and sum(boards). What if you tried every time cap upward and returned the first that works?

2Hint 2Explore hint

For a fixed cap x, count painters: walk the boards, keep a running block sum, and start a new painter whenever the next board would push the block past x.

3Hint 3Explore hint

The first cap whose painter-count is ≤ k is the answer — and once a cap works, every larger cap works. But sum(boards) can be ~10⁹, so the scan dominates.

A · Core idea

Start with the reframing: you're choosing a number — the time the slowest painter is allowed to take — and that number lives in [max(boards), sum(boards)]. The lower end is max(boards) because whoever paints the longest board needs at least that long; the upper end is sum(boards) because a single painter could do every board.

The feasibility check counts painters. Fix a time cap x. Sweep the boards left to right with a running block sum. Add the current board; if that would exceed x, close the current painter's block and hand this board to a new painter. The painters opened is exactly the minimum needed under cap x, because the assignment is contiguous and lengths are non-negative — packing each painter as full as the cap allows minimizes how many painters you use.

Why greedy-fill is exact. Within a contiguous block the running sum only grows, and pushing a painter to work right up to the cap never forces more painters downstream — it can only leave less for later, which helps. So 'fill to the cap, then cut' yields the fewest painters for that cap — a precise yes/no feasibility answer, not an estimate.

Why scanning upward is valid. The first cap whose painter count is ≤ k is the minimum feasible time. Raising the cap only lets each painter absorb more boards, so it never increases the painter count — meaning once a cap works, all larger caps work. That 'larger cap ⇒ never worse' fact is the monotonicity we'll exploit next.

Why we don't ship this. sum(boards) can reach 10⁵ · 10⁴ = 10⁹. An O(n) check run a billion times is hopeless. Because feasibility is monotone in the cap, binary-search the boundary instead of walking to it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

boards = [10, 20, 30, 40], k = 2

Array state

painter 1

10 → 30 → 60 (all ≤ 60)

[0]

[1]

fill ↓

[2]

[3]

Current pointerResolved stateNot processed

Final result60

C · Code with teaching comments

Reference implementation previewpublic int paintersPartition(int[] boards, int k) { int lo = 0, hi = 0; for (int b : boards) { lo = Math.max(lo, b); hi += b; } for (int x = lo; x <= hi; x++) { if (paintersNeeded(boards, x) <= k) {Explore the full code

solution.javaJava

Linear Scan Over the Answer — Baseline — reference

3 teaching notes

1
public int paintersPartition(int[] boards, int k) {
2
    int lo = 0, hi = 0;
3
    // Answer bounds: lo = longest single board (a hard floor), hi = total length (one
4
    // painter does all).
5
    for (int b : boards) { lo = Math.max(lo, b); hi += b; }
6
    for (int x = lo; x <= hi; x++) {
7
        // First time cap that fits within k painters is the minimized finishing time.
8
        if (paintersNeeded(boards, x) <= k) {
9
            return x;          // first feasible time is the minimum
10
        }
11
    }
12
    return hi;
13
}
14
 
15
private int paintersNeeded(int[] boards, int timeCap) {
16
    int painters = 1, load = 0;
17
    for (int b : boards) {
18
        // Adding this board overflows the cap → start a new painter's contiguous block.
19
        if (load + b > timeCap) {
20
            painters++;        // hand this board to a new painter
21
            load = b;
22
        } else {
23
            load += b;
24
        }
25
    }
26
    return painters;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n · sum) timeO(1) spaceOpen the invariant and proofExplore the proof

The fact that 'a larger time cap never needs more painters' is precisely the proof that feasible(x) is monotone increasing — the green light to replace the linear scan with a binary search over the same candidate caps.

ComplexityO(n · sum) time, O(1) space — Each candidate time (up to sum(boards)) runs an O(n) greedy painter count → O(n · sum). Fine for tiny totals, far too slow under the real constraints.

E · Edge cases and pitfalls3Starting the scan at 0 instead of max(boards) — wastes time on impossible caps.Explore edge cases

Pitfalls

Starting the scan at 0 instead of max(boards) — wastes time on impossible caps.
Letting x climb to sum(boards) ≈ 10⁹ — the scan times out.
Sorting boards 'to balance' — destroys contiguity and changes the problem.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Finishing Time (Optimal)

TimeO(n log(sum))SpaceO(1)

The intended answer. Phrase it as 'feasible(time) is monotone, so binary-search the smallest feasible finishing time'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You showed feasible(time) is false for small caps and true for large caps, flipping exactly once. What finds that flip in logarithmic time?

2Hint 2Explore hint

Binary-search the time cap in [max(boards), sum(boards)]. At each mid, run the O(n) greedy painter count. ≤ k painters means mid is feasible — record it and try smaller; otherwise try larger.

3Hint 3Explore hint

Because you MINIMIZE, on a feasible mid record ans = mid and move hi = mid - 1; on infeasible move lo = mid + 1. The last feasible mid is the answer.

A · Core idea

This is binary search on the answer, identical in structure to Allocate Pages — only the words 'students/pages' become 'painters/time'.

The monotonic predicate, precisely. Define feasible(x) = true if the boards split into at most k contiguous blocks each summing to ≤ x. Raising x never increases the painters forced (a roomier cap only lets each painter take more boards). So across x from max(boards) to sum(boards), feasible(x) reads [F, F, …, F, T, T, …, T] — false while too tight, true once loose enough, flipping exactly once. The answer is the smallest `x` that is true.

The feasibility check is the same painter count. paintersNeeded(x) sweeps once, accumulating a block load and opening a new painter whenever the next board would push the load past x. Contiguity plus non-negative lengths make filling-to-the-cap the painter-minimizing strategy, so the count is exact — the hard requirement for binary-search-on-the-answer.

Driving toward the smallest true. Set lo = max(boards), hi = sum(boards). Compute mid = lo + (hi − lo) / 2. If paintersNeeded(mid) ≤ k, mid works but a tighter cap might too — record ans = mid and search the lower half with hi = mid − 1. If mid needs more than k painters, it's too tight — search upward with lo = mid + 1. When lo > hi, ans holds the smallest feasible time.

The off-by-one traps, named. (1) lo = 0 instead of max(boards) wastes iterations on caps that can't even hold the longest board. (2) Recording ans on the infeasible branch returns a time that doesn't actually fit k painters. (3) Flipping the direction — this is minimize the maximum, so a feasible mid means 'try smaller', i.e. move hi left. Going right returns a larger-than-necessary time. State the invariant 'ans is always a time that fits within k painters' and the moves follow.

Folding in per-unit time. If each unit length takes t time, the finishing time is t × (min-max block sum). Solve the integer problem above, then multiply the result by t once at the end — the search itself is unchanged.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

boards = [10, 20, 30, 40], k = 2

Array state

lo=40, hi=100

mid=70 feasible(T) → ans=70, hi=69

lo ↓

[0]

...

[1]

[2]

...

[3]

mid ↓

[4]

...

[5]

hi ↓

100

[6]

Current pointerResolved stateNot processed

Final result60

C · Code with teaching comments

solution.javaJava

Binary Search on the Finishing Time (Optimal) — optimal

6 teaching notes

1
public int paintersPartition(int[] boards, int k) {
2
    int lo = 0, hi = 0;
3
    // lo = longest board (hard floor); hi = total length (one painter does all).
4
    for (int b : boards) { lo = Math.max(lo, b); hi += b; }
5
    int ans = hi;
6
    while (lo <= hi) {
7
        // Overflow-safe midpoint — sum can approach int's limit.
8
        int mid = lo + (hi - lo) / 2;
9
        // The monotone feasibility check: do k painters suffice under this time cap?
10
        if (paintersNeeded(boards, mid) <= k) {
11
            ans = mid;        // feasible → remember it, try LESS time
12
            // Feasible → MINIMIZE, so search for an even smaller time on the left.
13
            hi = mid - 1;
14
        } else {
15
            lo = mid + 1;     // infeasible → allow MORE time
16
        }
17
    }
18
    return ans;
19
}
20
 
21
private int paintersNeeded(int[] boards, int timeCap) {
22
    int painters = 1, load = 0;
23
    for (int b : boards) {
24
        if (load + b > timeCap) {
25
            painters++;
26
            load = b;
27
        } else {
28
            load += b;
29
        }
30
    }
31
    return painters;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(n log(sum)) timeO(1) spaceOpen the invariant and proofExplore the proof

Painter's Partition, Allocate Pages, and Split Array Largest Sum are the same algorithm; only the nouns differ. Once you can say 'minimize the maximum over a contiguous k-way split', you should write the [max, sum] binary search from muscle memory. The transferable skill is recognising that disguise, not re-deriving the search each time.

ComplexityO(n log(sum)) time, O(1) space — The time range spans sum(boards), so binary search runs O(log(sum)) iterations, each doing the O(n) greedy count → O(n log(sum)). Computing bounds is O(n); space is O(1).

E · Edge cases and pitfalls7boards = [100], k = 1 — lo = hi = 100; the single painter takes 100 → answer 100.Explore edge cases

Edge cases handled

boards = [100], k = 1lo = hi = 100; the single painter takes 100 → answer 100.
boards = [1, 1, 1, 1, 1], k = 5One board each → slowest painter takes 1. lo = 1 is already feasible → answer 1.
boards = [3, 1, 4, 1, 5], k = 1One painter does everything → answer sum = 14, the upper bound.

Pitfalls

Setting lo = 0 instead of max(boards) — searches times that can't paint the longest board.
Recording ans on the infeasible branch — returns a time that needs more than k painters.
Going right on a feasible mid — that maximizes instead of minimizing.
Using (lo + hi) / 2 — overflows when sum approaches the int limit.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int paintersPartition(int[] boards, int k) { int lo = 0, hi = 0; for (int b : boards) { lo = Math.max(lo, b); hi += b; } int ans = hi; while (lo <= hi) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting the boards

Painters take contiguous boards in the given order. Sorting reorders the line, so the blocks you count no longer correspond to valid assignments.

Explore the code comparison

Don't write this

Arrays.sort(boards);   // WRONG: contiguity is defined by original order
int lo = boards[boards.length - 1], hi = ...;

Write this instead

int lo = 0, hi = 0;
for (int b : boards) { lo = Math.max(lo, b); hi += b; }  // no sort

Wrong lower bound

The painter assigned the longest board can't finish before that board is done. Starting lo at 0 explores times that can never be feasible.

Explore the code comparison

Don't write this

lo, hi = 0, sum(boards)        # lo too low

Write this instead

lo, hi = max(boards), sum(boards)

Wrong direction on a feasible mid

This minimizes the maximum, so a feasible time means 'a smaller time might also work'. Moving lo right returns a finishing time larger than the true minimum.

Explore the code comparison

Don't write this

if (paintersNeeded(boards, mid) <= k) {
    lo = mid + 1;          // WRONG: walks away from smaller feasible times
}

Write this instead

if (paintersNeeded(boards, mid) <= k) {
    ans = mid;
    hi = mid - 1;          // minimize → search for an even smaller time
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer + greedy painter-count feasibility

Code pattern to memorize

lo, hi = max(boards), sum(boards)
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if paintersNeeded(mid) <= k:   # painters required with time cap mid
        ans = mid; hi = mid - 1        # feasible → try a SMALLER time
    else:
        lo = mid + 1                   # infeasible → allow MORE time

Rules to remember

1A painter paints a contiguous run of boards — that contiguity is what lets a single left-to-right sweep count the painters a time cap forces.
2Lower bound is max(board): whoever paints the longest single board needs at least that much time. Upper bound is sum(boards): one painter does everything.
3The predicate is monotone increasing: if a time cap x is enough, every cap > x is enough too. We MINIMIZE, so on a feasible mid go left (hi = mid − 1) and record it.
4If boards have a per-unit time t, the answer is just t × (min-max block sum) — fold t in at the end; it doesn't change the search.
5Feasibility counts painters forced by the cap: open a new painter whenever the next board would push the running block past the cap. Bail early once the count exceeds k.

Use this pattern when

Workers/painters/machines each take a CONTIGUOUS slice of a sequence
You minimize the slowest worker's load — minimize the maximum block sum
A fast O(n) check answers 'how many workers does this load cap force?'
The answer is a number in [max(element), sum(elements)]

Choose another pattern when

Painters can take non-contiguous boards → it's a scheduling/partition problem, not binary search on the answer
You must output the assignment, not just the finishing time → reconstruct after the search
Board lengths can be negative → running sums aren't monotone and the greedy count breaks
k is effectively unbounded → the answer is just max(board)

Interview takeaway

Painter's Partition is Allocate Pages wearing a different hat: minimize the largest contiguous block sum across k groups. Recognise the contiguous-split + min-max signature, bound the answer by [max, sum], binary-search it, and check feasibility with a one-pass greedy worker count. Same algorithm as Split Array Largest Sum.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Binary Search on the Answer (minimize the maximum). Trigger on 'k workers each take a contiguous slice, minimize the slowest worker's load'. Bounds [max(element), sum(elements)]; feasibility is an O(n) greedy worker count. Identical to Allocate Pages and Split Array Largest Sum.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Allocate Minimum Pages
Same algorithm — k students, book pages, minimize the maximum pages per student.
Split Array Largest Sum
Coming soon
LeetCode's version: split into k subarrays minimizing the largest subarray sum.
Aggressive Cows
The mirror image — maximize the minimum gap; feasible monotone the other way.
Capacity to Ship Packages Within D Days
Coming soon
Binary-search the ship capacity; feasible(cap) = all packages ship within D days.

Same pattern

←

Kth Smallest Element in an Array

Continue · Next problem

Floor and Ceil in a Sorted Array

mediumBinary SearchFrequently asked

Painter's Partition Problem

Binary Search · 13 of 16 · 11 min

You are given an array boards of n integers where boards[i] is the length of the i-th board, and an integer k — the number of painters.

Each painter paints a contiguous sequence of boards, painting 1 unit of board length takes 1 unit of time, and all painters work simultaneously.

Assign the boards so that the time to paint all boards is minimized. The total time is the time taken by the painter who finishes last (the largest block of lengths). Return that minimized time.

In plain English

Examples

Example 1

Input: boards = [10, 20, 30, 40], k = 2
Output: 60
Note: Cut [10, 20, 30] | [40] → block sums 60 and 40 → the slower painter takes 60. Any other 2-way cut is worse (e.g. [10,20]|[30,40] → 70).

Example 2

Input: boards = [10, 10, 10, 10], k = 2
Output: 20
Note: Cut [10, 10] | [10, 10] → both painters take 20. Balanced split, minimized maximum 20.

Example 3

Input: boards = [5, 10, 30, 20, 15], k = 3
Output: 35
Note: Cut [5, 10] | [30] | [20, 15] → sums 15, 30, 35 → slowest painter takes 35, the best achievable.

Constraints

1 ≤ k ≤ n ≤ 10⁵
1 ≤ boards[i] ≤ 10⁴
Painters work in parallel; a painter's time equals the sum of lengths in its contiguous block
If a per-unit time t is given, multiply the result by t

Clarifying questions4First question: Can a painter skip around to non-adjacent boards?Explore questions

Q1.Can a painter skip around to non-adjacent boards?
No — each painter's boards are contiguous. That's the whole reason a one-pass greedy count works.
Q2.Do painters work in parallel or one after another?
In parallel. The finishing time is the maximum block sum, not the total. If it were sequential, the answer would just be sum(boards).
Q3.Is there a per-unit painting time?
If each unit length takes t time, solve for the min-max block sum first, then multiply by t at the end — it scales the answer linearly without changing the search.
Q4.Why is the smallest possible time max(board)?
Whoever paints the longest single board can't finish before that board is done, so no assignment beats max(board).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Sorting the boards (which destroys contiguity), using lo = 0, or moving the search the wrong way on a feasible mid because the minimize/maximize direction got flipped.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Linear Scan Over the Answer — Baseline	`O(n · sum)`	`O(1)`	Lead with this to show you've identified the search space (the finishing time) and the painter-count check. Then flag that the scan range is sum(boards), which is too big.	Read
2	Binary Search on the Finishing Time (Optimal)Optimal	`O(n log(sum))`	`O(1)`	The intended answer. Phrase it as 'feasible(time) is monotone, so binary-search the smallest feasible finishing time'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Linear Scan Over the Answer — Baseline

TimeO(n · sum)SpaceO(1)

Lead with this to show you've identified the search space (the finishing time) and the painter-count check. Then flag that the scan range is sum(boards), which is too big.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some finishing time between max(boards) and sum(boards). What if you tried every time cap upward and returned the first that works?

2Hint 2Explore hint

For a fixed cap x, count painters: walk the boards, keep a running block sum, and start a new painter whenever the next board would push the block past x.

3Hint 3Explore hint

The first cap whose painter-count is ≤ k is the answer — and once a cap works, every larger cap works. But sum(boards) can be ~10⁹, so the scan dominates.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

boards = [10, 20, 30, 40], k = 2

Array state

painter 1

10 → 30 → 60 (all ≤ 60)

[0]

[1]

fill ↓

[2]

[3]

Current pointerResolved stateNot processed

Final result60

C · Code with teaching comments

solution.javaJava

Linear Scan Over the Answer — Baseline — reference

3 teaching notes

1
public int paintersPartition(int[] boards, int k) {
2
    int lo = 0, hi = 0;
3
    // Answer bounds: lo = longest single board (a hard floor), hi = total length (one
4
    // painter does all).
5
    for (int b : boards) { lo = Math.max(lo, b); hi += b; }
6
    for (int x = lo; x <= hi; x++) {
7
        // First time cap that fits within k painters is the minimized finishing time.
8
        if (paintersNeeded(boards, x) <= k) {
9
            return x;          // first feasible time is the minimum
10
        }
11
    }
12
    return hi;
13
}
14
 
15
private int paintersNeeded(int[] boards, int timeCap) {
16
    int painters = 1, load = 0;
17
    for (int b : boards) {
18
        // Adding this board overflows the cap → start a new painter's contiguous block.
19
        if (load + b > timeCap) {
20
            painters++;        // hand this board to a new painter
21
            load = b;
22
        } else {
23
            load += b;
24
        }
25
    }
26
    return painters;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n · sum) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Starting the scan at 0 instead of max(boards) — wastes time on impossible caps.Explore edge cases

Pitfalls

Starting the scan at 0 instead of max(boards) — wastes time on impossible caps.
Letting x climb to sum(boards) ≈ 10⁹ — the scan times out.
Sorting boards 'to balance' — destroys contiguity and changes the problem.

03.2

Approach 2 of 2 · Optimal

Binary Search on the Finishing Time (Optimal)

TimeO(n log(sum))SpaceO(1)

The intended answer. Phrase it as 'feasible(time) is monotone, so binary-search the smallest feasible finishing time'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You showed feasible(time) is false for small caps and true for large caps, flipping exactly once. What finds that flip in logarithmic time?

2Hint 2Explore hint

Binary-search the time cap in [max(boards), sum(boards)]. At each mid, run the O(n) greedy painter count. ≤ k painters means mid is feasible — record it and try smaller; otherwise try larger.

3Hint 3Explore hint

Because you MINIMIZE, on a feasible mid record ans = mid and move hi = mid - 1; on infeasible move lo = mid + 1. The last feasible mid is the answer.

A · Core idea

This is binary search on the answer, identical in structure to Allocate Pages — only the words 'students/pages' become 'painters/time'.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

boards = [10, 20, 30, 40], k = 2

Array state

lo=40, hi=100

mid=70 feasible(T) → ans=70, hi=69

lo ↓

[0]

...

[1]

[2]

...

[3]

mid ↓

[4]

...

[5]

hi ↓

100

[6]

Current pointerResolved stateNot processed

Final result60

C · Code with teaching comments

solution.javaJava

Binary Search on the Finishing Time (Optimal) — optimal

6 teaching notes

1
public int paintersPartition(int[] boards, int k) {
2
    int lo = 0, hi = 0;
3
    // lo = longest board (hard floor); hi = total length (one painter does all).
4
    for (int b : boards) { lo = Math.max(lo, b); hi += b; }
5
    int ans = hi;
6
    while (lo <= hi) {
7
        // Overflow-safe midpoint — sum can approach int's limit.
8
        int mid = lo + (hi - lo) / 2;
9
        // The monotone feasibility check: do k painters suffice under this time cap?
10
        if (paintersNeeded(boards, mid) <= k) {
11
            ans = mid;        // feasible → remember it, try LESS time
12
            // Feasible → MINIMIZE, so search for an even smaller time on the left.
13
            hi = mid - 1;
14
        } else {
15
            lo = mid + 1;     // infeasible → allow MORE time
16
        }
17
    }
18
    return ans;
19
}
20
 
21
private int paintersNeeded(int[] boards, int timeCap) {
22
    int painters = 1, load = 0;
23
    for (int b : boards) {
24
        if (load + b > timeCap) {
25
            painters++;
26
            load = b;
27
        } else {
28
            load += b;
29
        }
30
    }
31
    return painters;
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(n log(sum)) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7boards = [100], k = 1 — lo = hi = 100; the single painter takes 100 → answer 100.Explore edge cases

Edge cases handled

boards = [100], k = 1lo = hi = 100; the single painter takes 100 → answer 100.
boards = [1, 1, 1, 1, 1], k = 5One board each → slowest painter takes 1. lo = 1 is already feasible → answer 1.
boards = [3, 1, 4, 1, 5], k = 1One painter does everything → answer sum = 14, the upper bound.

Pitfalls

Setting lo = 0 instead of max(boards) — searches times that can't paint the longest board.
Recording ans on the infeasible branch — returns a time that needs more than k painters.
Going right on a feasible mid — that maximizes instead of minimizing.
Using (lo + hi) / 2 — overflows when sum approaches the int limit.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Sorting the boards

Painters take contiguous boards in the given order. Sorting reorders the line, so the blocks you count no longer correspond to valid assignments.

Explore the code comparison

Don't write this

Arrays.sort(boards);   // WRONG: contiguity is defined by original order
int lo = boards[boards.length - 1], hi = ...;

Write this instead

int lo = 0, hi = 0;
for (int b : boards) { lo = Math.max(lo, b); hi += b; }  // no sort

Wrong lower bound

The painter assigned the longest board can't finish before that board is done. Starting lo at 0 explores times that can never be feasible.

Explore the code comparison

Don't write this

lo, hi = 0, sum(boards)        # lo too low

Write this instead

lo, hi = max(boards), sum(boards)

Wrong direction on a feasible mid

This minimizes the maximum, so a feasible time means 'a smaller time might also work'. Moving lo right returns a finishing time larger than the true minimum.

Explore the code comparison

Don't write this

if (paintersNeeded(boards, mid) <= k) {
    lo = mid + 1;          // WRONG: walks away from smaller feasible times
}

Write this instead

if (paintersNeeded(boards, mid) <= k) {
    ans = mid;
    hi = mid - 1;          // minimize → search for an even smaller time
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Binary search on the answer + greedy painter-count feasibility

Code pattern to memorize

lo, hi = max(boards), sum(boards)
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if paintersNeeded(mid) <= k:   # painters required with time cap mid
        ans = mid; hi = mid - 1        # feasible → try a SMALLER time
    else:
        lo = mid + 1                   # infeasible → allow MORE time

Rules to remember

1A painter paints a contiguous run of boards — that contiguity is what lets a single left-to-right sweep count the painters a time cap forces.
2Lower bound is max(board): whoever paints the longest single board needs at least that much time. Upper bound is sum(boards): one painter does everything.
3The predicate is monotone increasing: if a time cap x is enough, every cap > x is enough too. We MINIMIZE, so on a feasible mid go left (hi = mid − 1) and record it.
4If boards have a per-unit time t, the answer is just t × (min-max block sum) — fold t in at the end; it doesn't change the search.
5Feasibility counts painters forced by the cap: open a new painter whenever the next board would push the running block past the cap. Bail early once the count exceeds k.

Use this pattern when

Workers/painters/machines each take a CONTIGUOUS slice of a sequence
You minimize the slowest worker's load — minimize the maximum block sum
A fast O(n) check answers 'how many workers does this load cap force?'
The answer is a number in [max(element), sum(elements)]

Choose another pattern when

Painters can take non-contiguous boards → it's a scheduling/partition problem, not binary search on the answer
You must output the assignment, not just the finishing time → reconstruct after the search
Board lengths can be negative → running sums aren't monotone and the greedy count breaks
k is effectively unbounded → the answer is just max(board)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Allocate Minimum Pages
Same algorithm — k students, book pages, minimize the maximum pages per student.
Split Array Largest Sum
Coming soon
LeetCode's version: split into k subarrays minimizing the largest subarray sum.
Aggressive Cows
The mirror image — maximize the minimum gap; feasible monotone the other way.
Capacity to Ship Packages Within D Days
Coming soon
Binary-search the ship capacity; feasible(cap) = all packages ship within D days.

Same pattern

←

Kth Smallest Element in an Array

Continue · Next problem

Floor and Ceil in a Sorted Array