The “Painter’s Partition Problem-II” is a classic binary search and partitioning problem often asked in coding interviews. <\/p>\n\n\n\n
In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Dilpreet wants to paint his dog’s home that has n<\/strong> boards with different lengths. The length of ith <\/sup>board is given by arr[i]<\/strong> where arr[]<\/strong> is an array of n<\/strong> integers. He hired k<\/strong> painters for this work and each painter takes 1 unit time to paint 1 unit of the board. Examples:<\/strong><\/p>\n\n\n\n Constraints:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not efficient for large inputs.<\/p>\n\n\n\n
\n\n\n\nProblem Statement<\/strong><\/h2>\n\n\n\n
<\/strong>
Return the minimum time to get this job done if all painters start together with the constraint that any painter will only paint continuous boards, say boards numbered [2,3,4] <\/strong>or only board [1]<\/strong> or nothing but not boards [2,4,5]<\/strong>.<\/p>\n\n\n\nInput: <\/strong>arr[] = [5, 10, 30, 20, 15], k = 3\nOutput:<\/strong> 35\nExplanation: <\/strong>The most optimal way will be: Painter 1 allocation : [5,10], Painter 2 allocation : [30], Painter 3 allocation : [20,15], Job will be done when all painters finish i.e. at time = max(5+10, 30, 20+15) = 35<\/pre>\n\n\n\n
Input: <\/strong>arr[] = [10, 20, 30, 40], k = 2\nOutput: <\/strong>60\nExplanation: <\/strong>The most optimal way to paint: Painter 1 allocation : [10,20,30], Painter 2 allocation : [40], Job will be complete at time = 60<\/pre>\n\n\n\n
Input: <\/strong>arr[] = [100, 200, 300, 400], k = 1\nOutput: <\/strong>1000\nExplanation: <\/strong>There is only one painter, so the painter must paint all boards sequentially. The total time taken will be the sum of all board lengths, i.e., 100 + 200 + 300 + 400 = 1000.<\/pre>\n\n\n\n
1 \u2264 arr.size() \u2264 105
<\/sup>1 \u2264 arr[i] \u2264 105
<\/sup>1 \u2264 k \u2264 105<\/sup><\/p>\n\n\n
\n\n\n\nBrute Force Solution (Try Every Possible Maximum Time)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Try every possible maximum time from the largest single board to the sum of all boards.<\/li>\n\n\n\n
For each time, check if it is possible to allocate boards to painters so that no painter paints more than that much time.<\/li>\n\n\n\n
The first value for which allocation is possible is our answer.<\/li>\n\n\n\n
We check every possible value, so we\u2019re sure to find the minimum one that works.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n