DSA interview question

Painter's Partition

Medium · Algorithms · Topics: binary search on answer, array

The problem

A theme park repaints a row of fence boards before opening day. It has k painters, each painting at one unit of length per hour, and each painter must take a contiguous stretch of boards so they don't walk past each other. All painters work in parallel, so the job takes as long as the busiest painter's stretch. Minimise that time. It's the "minimise the largest part" pattern again. One difference from book allocation: a painter may be left idle, so having more painters than boards is fine.

Example: boards [5, 10, 30, 20, 15], k = 3 → 35 ([5, 10], [30], [20, 15]).

Function signature

long long minTime(const vector<int>& boards, int k);  // minimum time; painters may be idle

Test cases

Input `(boards, k)`	Output	Explanation
`([5, 10, 30, 20, 15], 3)`	35	[5, 10], [30], [20, 15]
`([10, 20, 30, 40], 2)`	60	[10, 20, 30] and [40]
`([10, 20, 60, 50, 30, 40], 3)`	90	[10, 20, 60], [50, 30], [40]
`([100], 5)`	100	Four painters stay idle
`([1, 1, 1, 1], 4)`	1

(Confirm: each painter takes a contiguous stretch; idle painters are allowed; time equals the largest stretch length.)

How interviewers phrase it

"The painter's partition problem" (GeeksforGeeks).
Structurally identical to split array largest sum and book allocation, and often asked to see whether you recognise that.

Clarifying questions to ask

Must each painter's boards be contiguous?
Can a painter be idle? (Here yes, which differs from book allocation.)
Does painting speed matter? (If all painters are equally fast, it just scales the answer.)

Follow-ups to expect

"What's the answer range?"
"How do you check a time limit T?"
"What changes if painters can't be idle?"
"What if each unit takes t hours?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview