Painter's Partition Problem

Problem

Given an array boards[] of board lengths and k painters, assign boards to painters such that: (1) each painter paints a contiguous segment of boards, (2) every board is painted by exactly one painter. Minimize the maximum time any single painter takes (time to paint a board equals its length).

Example 1

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

Output: 60

Explanation: Painter 1: [10,20,30] = 60, Painter 2: [40] = 40. Max = 60.

Example 2

Input: boards = [10,10,10,10], k = 2

Output: 20

Explanation: Painter 1: [10,10] = 20, Painter 2: [10,10] = 20. Max = 20.

Example 3

Input: boards = [5,10,30,20,15], k = 3

Output: 35

Explanation: Painter 1: [5,10] = 15, Painter 2: [30] = 30, Painter 3: [20,15] = 35. Max = 35.

Constraints: 1 ≤ k ≤ boards.length ≤ 10⁵ | 1 ≤ boards[i] ≤ 10⁶

Search Range — Max Time per Painter

—

mid

—

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

—

Board Assignment — Greedy Simulation at candidate mid

Waiting…

Variables

—

mid

—

painters

—

feasible?

—

Step Logic

Press ▶ Play or Next Step to begin.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Binary search on answer space: lo = max(boards), hi = sum(boards)

Compute mid = lo + (hi−lo)/2; test if k painters can finish all boards in ≤ mid time

Feasibility check: greedily assign boards to painters, start new painter when limit exceeded

Feasible (painters ≤ k): try smaller mid → hi = mid

Infeasible (painters > k): need more time → lo = mid + 1

Time

O(n log(sum))

Space

O(1)

Why Binary Search on Answer Works

The answer space is monotone: if k painters can finish in time T, they can also finish in time T+1. Binary search finds the smallest T where the answer flips from infeasible to feasible. The feasibility check is a simple greedy linear scan: assign boards to the current painter until adding the next board would exceed the time limit, then start a new painter. O(n log(sum)) total.