Painter's Partition Problem
Solve a famous interview problem based on Binary Search.
We'll cover the following
Problem statement
We have to paint n
boards of length {${A_1}$, ${A_2}$, …, ${A_n}$}. There are k
painters available and each takes 1 unit of time to paint 1 unit of the board. The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4}
or only board {1}
or nothing but not board {2, 4, 5}
.
Let us look at some examples:

We have input
k = 2
,A = {10, 10, 10, 10}
. The output is20
. Here, we can divide the boards into2
equalsized partitions, so each painter gets20
units of the board and the total time taken is20
. 
We have input
k = 2, A = {10, 20, 30, 40}
. The output is60
. Here, we can divide the first3
boards for one painter and the last board for the second painter.
We can describe the problem as:
Given an array A
of nonnegative integers and a positive integer k
, we have to divide A
into k
of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.
Solution: Divide and conquer approach
We can see that the highest possible value could be the sum of all the elements in the array and this happens when we allot 1
painter all the sections of the board. The lowest possible value of the problem could be the maximum value of the array max
, because in this allocation we can allot max
to one painter and divide the other sections such that the cost of them is less than or equal to max
and as close as possible to max
. Now if we consider using x
painters in the above scenarios, it is obvious that as the value in the range increases, the value of x
decreases and viceversa. From this, we can find the target value when x = k
and use a helper function to find x
, the minimum number of painters required when the maximum length of section a painter can paint is given.
Let us see the implementation to understand the concept better.
Level up your interview prep. Join Educative to access 70+ handson prep courses.