Painters Partition Problem
Hard · Binary Search · Array · Binary Search · Greedy · Dynamic Programming
Problem
You have n boards in a row, where boards[i] is the length of board i, and k painters. Every painter paints one unit of length per unit of time, and all painters work at the same time.
Each painter may only paint a contiguous run of boards (possibly none), and every board must be painted by exactly one painter. The job finishes when the busiest painter finishes.
Return the minimum time needed to paint all the boards: the smallest possible value of the largest total length given to one painter.
Examples
Input: boards = [10,20,30,40], k = 2 Output: 60
[10,20,30] and [40] take 60 and 40; no split finishes before 60.
Input: boards = [8,3,5], k = 5 Output: 8
Each board gets its own painter, so the longest board, 8, decides.
Input: boards = [4,4,4], k = 1 Output: 12
A single painter paints everything, taking 12.
Constraints
- 1 <= len(boards) <= 10^5
- 1 <= boards[i] <= 10^5
- 1 <= k <= 10^5
Approaches
- Baseline: DP over painters and prefixes — time O(min(k, n) · n²), space O(min(k, n) · n)
Follow-up
Binary search plus a greedy check is the standard pattern for "minimize the maximum" over contiguous splits. The first use case is the check on its own (fewest painters for a deadline); the second flips the goal to making the smallest piece as large as possible.
Related problems
Start free on Cariara · Coding problems · System design studio
