Painter's Partition Problem

Problem

Given an array/list of length ‘n’, where the array/list represents the boards and each element of the given array/list represents the length of each board. Some ‘k’ numbers of painters are available to paint these boards. Consider that each unit of a board takes 1 unit of time to paint.

You are supposed to return the area of the minimum time to get this job done of painting all the ‘n’ boards under a constraint that any painter will only paint the continuous sections of boards. (link)

Example :

Input: arr = [2, 1, 5, 6, 2, 3], k = 2
Output: 11

Explanation:
First painter can paint boards 1 to 3 in 8 units of time and 
the second painter can paint boards 4-6 in 11 units of time. 
Thus both painters will paint all the boards in max(8,11) = 11 units of time.
It can be shown that all the boards can't be painted in less than 11 units of time.

Expected Time Complexity: Try to do this in O(n*log(n)).

Constraints :

1 <= n <= 10^5
1 <= k <= n
1 <= arr[i] <= 10^9

Time Limit: 1 sec.

Solution

Brute force Approach

This is exactly similar to Allocate books (link) and Split Array largest Sum (link). We need to allocate the boards in such a way that the maximum value of the distribution of boards should be as minimal as possible.

Here, we approach the problem in the opposite way: we find out from the minimum possible time to the maximum time and check for each time threshold how many painters are required to paint. If the number of painters required is less than or equal to the required number 𝑘k, then we return that particular time as the answer

Why <=k ? Check the split array largest sum problem.

Time - O(sum-max)*O(n)

Space - O(1)

sum = Total sum of array; max = Max element of the array , n=length of array

public class Solution 
{
    private static int getTotalPainters(ArrayList<Integer> boards, int maxTimeForEachPainter){
        int noOfpainters = 1;
        int duration = 0;

        for(int time: boards){
            if(time+duration<=maxTimeForEachPainter){
                duration+=time;
            }
            else{
                noOfpainters+=1;
                duration = time;
            }
        }
        return noOfpainters;
    }

    public static int findLargestMinDistance(ArrayList<Integer> boards, int k)
    {
        //    Write your code here.
        int min = Collections.max(boards);
        int max = boards.stream().reduce(0, (a,b)->a+b);

        for(int time = min; time<=max; time++){
            if(getTotalPainters(boards, time)<=k){
                return time;
            }
        }

        return -1;

    }
}

Optimal Approach - Binary Search

Apply binary search on top of brute force approach.

Time - O(sum-max) * O(logn)

space - O(1)

sum = Total sum of array; max = Max element of the array , n=length of array

public class Solution 
{
    private static int getTotalPainters(ArrayList<Integer> boards, int maxTimeForEachPainter){
        int noOfpainters = 1;
        int duration = 0;

        for(int time: boards){
            if(time+duration<=maxTimeForEachPainter){
                duration+=time;
            }
            else{
                noOfpainters+=1;
                duration = time;
            }
        }
        return noOfpainters;
    }
    public static int findLargestMinDistance(ArrayList<Integer> boards, int k)
    {
        //    Write your code here.
        int min = Collections.max(boards);
        int max = boards.stream().reduce(0, (a,b)->a+b);

        int low = min;
        int high = max;

        while(low<=high){
            int mid = (low+high)/2;

            if(getTotalPainters(boards, mid)>k){
                low = mid +1;
            }
            else{
                high = mid - 1;
            }
        }

        return low;

    }
}