Painter's Partition 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.

For example :

In the below figure where array/list elements are {2, 1, 5, 6, 2, 3}.

A painter can paint blocks {5,6} or {1,5,6,2} together but not {2,5,6} or {5,6,3}.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases. The first line of each test case contains two integers ‘N’ and ‘K’ denoting the number of elements in the array/list and number of painters available. The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output format :

For each test case, print the minimum time required to get the job done.

Note :

You do not need to print anything; it has already been taken care of.

Constraints :

1

Question

Painter's Partition 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.

For example :

In the below figure where array/list elements are {2, 1, 5, 6, 2, 3}.

alt text

A painter can paint blocks {5,6} or {1,5,6,2} together but not {2,5,6} or {5,6,3}.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’ denoting the number of elements in the array/list and number of painters available.

The second line contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output format :

For each test case, print the minimum time required to get the job done.

Note :

You do not need to print anything; it has already been taken care of.

Constraints :

1 <= T <= 5
1 <= N <= 10^4
1 <= K <= N
1 <= ARR[i] <= 10^5

Where ‘T’ is the number of test cases.
'N' is the length of the given array/list (boards).
‘K’ is the number of painters available.
And, ARR[i] denotes the i-th element in the array/list.

Time Limit: 1 sec.

Accepted Answer

Dynamic Programming

All we need to do is to Divide the boards into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.

We can put the (k - 1)th divider between the ith and (i + 1)th element where i is between 1 and N.

Now the recursive function will just require two conditions that can lead to the result and that will be out the maximum total cost:

The time is taken in the last partition where the (k - 1)th divider is before element i.
The maximum cost of any partition already formed to the left of the (k - 1)th divider.

Now to avoid the exponential time complexity we can use Dynamic Programming since it already keeps a track of pre-calculated data and will lead to better results if we can take the data from the dp table.

Space Complexity: OtherExplanation:

O(K * N), where ‘N’ is the number of elements in the given array/list and ‘K’ is the number of painters available.

Since we are creating a dp table of size (N + 1) * (K + 1), the overall space complexity will be O(N * K).

Time Complexity: OtherExplanation:

O(K * N ^ 3), where ‘N’ is the number of elements in the given array/list and ‘K’ is the number of painters available.

We are considering K painters and for each painter, it takes N ^ 3 iterations to calculate the minimum time for each number of painters. So the overall time complexity will be O(K * N ^ 3).

Python (3.5)

'''

    Time Complexity = O(K * (N ^ 3))

    Space Complexity = O(N * K)

    

    Where N is the number of elements in the given array/list and K is the number of painters available.

'''





def calculateSum(boards, start, end):

    totalSum = 0



    for i in range(start, end + 1):

        totalSum = totalSum + boards[i]



    return totalSum



def findLargestMinDistance(boards, k):



    n = len(boards)



    #    Initialize DP table.

    dp = [[0] * (n + 1) for _ in range(k + 1)]



    #    Base cases of k=1

    for i in range(1, n + 1):

        dp[1][i] = calculateSum(boards, 0, i - 1)



    #    For n=1.

    for i in range(1, k + 1):

        dp[i][1] = boards[0]



    #    2 to k partitions.

    for i in range(2, k + 1):

        

        #    2 to n boards.

        for j in range(2, n + 1): 

        

            #    Track the minimum value.

            best = 1e9



            #    i-1 th separator before position boards[p=1..j]

            for p in range(1, j + 1):

                best = min(best, max(dp[i - 1][p], calculateSum(boards, p, j - 1)))

            

            dp[i][j] = best

    

    #    Return the answer.

    return dp[k][n]

C++ (g++ 5.4)

/*

    Time Complexity = O(K * (N ^ 3))

    Space Complexity = O(N * K)

    

    Where N is the number of elements in the given array/list and K is the number of painters available.

*/



#include 



int calculateSum(vector &boards, int start, int end)

{

    int totalSum = 0;



    for (int i = start; i <= end; i++)

    {

        totalSum = totalSum + boards[i];

    }



    return totalSum;

}



int findLargestMinDistance(vector &boards, int k)

{



    int n = boards.size();



    //    Initialize DP table.

    vector> dp(k + 1, vector(n + 1, 0));



    //    Base cases of k=1.

    for (int i = 1; i <= n; i++)

    {

        dp[1][i] = calculateSum(boards, 0, i - 1);

    }



    //    For n=1.

    for (int i = 1; i <= k; i++)

    {

        dp[i][1] = boards[0];

    }



    //    2 to k partitions.

    for (int i = 2; i <= k; i++)

    {

    	

        //    2 to n boards.

        for (int j = 2; j <= n; j++)

        {

        	

            //    Track the minimum value.

            int best = INT_MAX;



            //    i-1 th separator before position boards[p=1..j]

            for (int p = 1; p <= j; p++)

            {

                best = min(best, max(dp[i - 1][p], calculateSum(boards, p, j - 1)));

            }



            dp[i][j] = best;

        }

    }



    //    Return the answer.

    return dp[k][n];

}

Java (SE 1.8)

/*

    Time Complexity = O(K * (N ^ 3))

    Space Complexity = O(N * K)



    Where N is the number of elements in the given array/list and K is the number of painters available.

*/



import java.util.ArrayList;



public class Solution 

{



    private static int calculateSum(ArrayList boards, int start, int end) 

    {

        int totalSum = 0;



        for (int i = start; i <= end; i++) 

        {

            totalSum = totalSum + boards.get(i);

        }



        return totalSum;

    }



    public static int findLargestMinDistance(ArrayList boards, int k) 

    {



        int n = boards.size();



        //    Initialize DP table.

        ArrayList> dp = new ArrayList>(k + 1);



        for (int i = 0; i < k + 1; i++) 

        {

            dp.add(new ArrayList(n + 1));

            for (int j = 0; j < n + 1; j++) 

            {

                dp.get(i).add(0);

            }

        }



        //    Base cases of k=1.

        for (int i = 1; i <= n; i++) 

        {

            dp.get(1).set(i, calculateSum(boards, 0, i - 1));

        }



        //    For n=1.

        for (int i = 1; i <= k; i++) 

        {

            dp.get(i).set(1, boards.get(0));

        }



        //    2 to k partitions.

        for (int i = 2; i <= k; i++) 

        {



            //    2 to n boards.

            for (int j = 2; j <= n; j++) 

            {

                

                //    Track the minimum value.

                int best = Integer.MAX_VALUE;



                //    i-1 th separator before position boards[p=1..j]

                for (int p = 1; p <= j; p++) 

                {

                    best = Math.min(best, Math.max(dp.get(i - 1).get(p), calculateSum(boards, p, j - 1)));

                }



                dp.get(i).set(j, best);

            }

        }



        //    Return the answer.

        return dp.get(k).get(n);

    }

}

Accepted Answer

Dynamic Programming Improvised

Consider we have N painters, then painters with index ‘i’ can paint fences only in continuous order. So, this means the first painter will paint some of the fences. Then the second painter paints some of the fences. The same goes for all the painters. This may happen that some painter does not even get a fence to paint.

We will use Dynamic Programming for solving this problem. Here, we will also use a very well-defined dynamic programming technique which is a prefix sum for taking the sum of time in O(1) time complexity.
First, we will solve the problem for a single painter. Then we will solve in a bottom-up manner for the number of painters = 2, 3, 4,… n.
For solving the problem for an ith painter, we will find the time taken by the ith painter to paint fence k to j. Here, we have considered ith painter will paint fence k to j, and fences from 1 to (k - 1) are painted by (i - 1) painters.
The answer for this subproblem should be the maximum time taken by either of (i - 1) painters or the ith painter.
In this manner, we keep on solving smaller subproblems.
Then, combining the result of these smaller subproblems we solve our initial problem.

Space Complexity: OtherExplanation:

O(N * K), where ‘N’ is the number of elements in the given array/list and ‘K’ is the number of painters available.

Since we are creating a dp table of size (N + 1) * (K + 1), the overall space complexity will be O(N * K).

Time Complexity: OtherExplanation:

O(K * (N ^ 2)), where ‘N’ is the number of elements in the given array/list and ‘K’ is the number of painters available.

The first loop runs over a number of painters (K), and nested loops run over the number of fences. If ‘N’ is equal to ‘K’, the time complexity becomes O(N ^ 3).

C++ (g++ 5.4)

/*

    Time Complexity = O(K * (N ^ 2))

    Space Complexity = O(N * K)

    

    Where N is the number of elements in the given array/list and K is the number of painters available.

*/



#include 



int findLargestMinDistance(vector &boards, int k)

{

    int n = boards.size();



    if (n == 0)

    {

        return 0;

    }



    //    stores the prefix sum for faster sum calculation over the range.

    vector prefixSum(n);



    prefixSum[0] = boards[0];



    for (int i = 1; i < n; i++)

    {

        prefixSum[i] = boards[i];

        prefixSum[i] = (prefixSum[i] + prefixSum[i - 1]);

    }



    //    dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order.

    vector> dp(k, vector(n, LONG_MAX));



    //    Filling the values for first painter.

    for (int i = 0; i < n; i++)

    {

        dp[0][i] = prefixSum[i];

    }



    //    Now solving for painters 2, 3, 4......n

    for (int i = 1; i < k; i++)

    {

        for (int j = i; j < n; j++)

        {

            for (int k = i; k <= j; k++)

            {

                long long int timeTakenForithPainter = prefixSum[j] - prefixSum[k - 1];



                dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1], timeTakenForithPainter));

            }

        }

    }



    if (k > n)

    {

        return dp[n - 1][n - 1];

    }



    return dp[k - 1][n - 1];

}

Java (SE 1.8)

/*

    Time Complexity = O(K * (N ^ 2))

    Space Complexity = O(N * K)



    Where N is the number of elements in the given array/list and K is the number of painters available.

*/



import java.util.Arrays;

import java.util.ArrayList;



public class Solution {

    public static int findLargestMinDistance(ArrayList boards, int k) {

        int n = boards.size();



        if (n == 0) {

            return 0;

        }



        //    stores the prefix sum for faster sum calculation over the range.

        ArrayList prefixSum = new ArrayList(n);



        prefixSum.add(boards.get(0));



        for (int i = 1; i < n; i++) {

            prefixSum.add(boards.get(i));

            prefixSum.set(i, prefixSum.get(i) + prefixSum.get(i - 1));

        }



        //    dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order.

        ArrayList> dp = new ArrayList>(k);

        for (int i = 0; i < k; i++) {

            dp.add(new ArrayList(n));

            for (int j = 0; j < n; j++) {

                dp.get(i).add(Integer.MAX_VALUE);

            }

        }



        //    Filling the values for first painter.

        for (int i = 0; i < n; i++) {

            dp.get(0).set(i, prefixSum.get(i));

        }



        //    Now solving for painters 2, 3, 4......n

        for (int i = 1; i < k; i++) {

            for (int j = i; j < n; j++) {

                for (int l = i; l <= j; l++) {

                    int timeTakenForithPainter = prefixSum.get(j) - prefixSum.get(l - 1);



                    dp.get(i).set(j, Math.min(dp.get(i).get(j), Math.max(dp.get(i - 1).get(l - 1), timeTakenForithPainter)));

                }

            }

        }



        if (k > n) {

            return dp.get(n - 1).get(n - 1);

        }



        return dp.get(k - 1).get(n - 1);

    }

}

Python (3.5)

'''

    Time Complexity = O(K * (N ^ 2))

    Space Complexity = O(N * K)

    

    Where N is the number of elements in the given array/list and K is the number of painters available.

'''



def findLargestMinDistance(boards, k):

    

    n = len(boards)



    if (n == 0):

        return 0



    #    stores the prefix sum for faster sum calculation over the range.

    prefixSum = [0] * n



    prefixSum[0] = boards[0]



    for i in range(1, n):

        prefixSum[i] = boards[i]

        prefixSum[i] = (prefixSum[i] + prefixSum[i - 1])





    #    dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order.

    dp = [[1e18] * n for _ in range(k)]



    #    Filling the values for first painter.

    for i in range(n):

        dp[0][i] = prefixSum[i]



    #    Now solving for painters 2, 3, 4......n

    for i in range(1, k):

        for j in range(i, n):

            for l in range(i, j + 1):

                timeTakenForithPainter = prefixSum[j] - prefixSum[l - 1]

                dp[i][j] = min(dp[i][j], max(dp[i - 1][l - 1], timeTakenForithPainter))



    

    return dp[min(n, k) - 1][n - 1]

Accepted Answer

Binary Search

How can we improvise our solution, we can use binary search for that.

We can see that the highest possible value in this range is the sum of all the elements in the array and this happens when we allot 1 painter to all the sections of the board.
The lowest possible value of this range is the maximum value of the array/list maximum, as in this allocation, we can allot maximum to one painter and divide the other sections such that the cost of them is less than or equal to the max and as close as possible to the max.
If we consider we use x painters in the above scenarios, it is obvious that as the value in the range increases, the value of x decreases, and if the value in the range decreases then the value of x increases.
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.

Space Complexity: O(1)Explanation:

O(1)

Since no extra space is required, the overall space complexity will be O(1).

Time Complexity: OtherExplanation:

O(N * log(sum)), where ‘N’ is the number of elements in the given array/list and sum denotes the sum of the whole array.

Since we are taking the sum of all the elements in the array so find out the number of units to be painted and then applying binary search, so the overall total time complexity will be O(N * (log(sum))).

Java (SE 1.8)

/*

    Time Complexity = O(K * (log(arrSum)))

    Space Complexity = O(1)



    Where N is the number of elements in the given array/list and arrSum is the sum of the array elements.

*/



import java.util.ArrayList;



public class Solution 

{

    

    //    Return the maximum element from the array.

    private static int findMax(ArrayList boards, int n) 

    {

        int max = Integer.MIN_VALUE;



        for (int i = 0; i < n; i++) 

        {

            if (boards.get(i) > max) 

            {

                max = boards.get(i);

            }

        }



        return max;

    }



    //    Return the sum of the elements in the array.

    private static int findSum(ArrayList boards, int n) 

    {

        int total = 0;

        for (int i = 0; i < n; i++) 

        {

            total += boards.get(i);

        }

        return total;

    }



    //    Find minimum required painters for given maxlen which is the maximum length a painter can paint.

    private static int countPainters(ArrayList boards, int maxLen) 

    {

        int n = boards.size(), totalSum = 0, painters = 1;



        for (int i = 0; i < n; i++) 

        {

            totalSum += boards.get(i);



            if (totalSum > maxLen) 

            {

                totalSum = boards.get(i);

                painters++;

            }

        }



        return painters;

    }



    public static int findLargestMinDistance(ArrayList boards, int k) 

    {

        int n = boards.size();



        int low = findMax(boards, n);

        int high = findSum(boards, n);



        while (low < high) 

        {

            int mid = low + (high - low) / 2;

            int reqPainters = countPainters(boards, mid);



            //    Find better optimum in lower half here mid is included because we may not get anything better.

            if (reqPainters <= k) 

            {

                high = mid;

            }

            

            //    Find better optimum in upper half here mid is excluded because it gives required Painters > k, which is invalid.

            else 

            {

                low = mid + 1;

            }

        }



        return low;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity = O(K * (log(arrSum)))

    Space Complexity = O(1)



    Where N is the number of elements in the given array/list and arrSum is the sum of the array elements.

*/



#include 



//    Return the maximum element from the array.

int findMax(vector &boards, int n)

{

	int max = INT_MIN;



	for (int i = 0; i < n; i++)

	{

		if (boards[i] > max)

		{

			max = boards[i];

		}

	}



	return max;

}



//    Return the sum of the elements in the array.

int findSum(vector &boards, int n)

{

	int total = 0;

	for (int i = 0; i < n; i++)

	{

		total += boards[i];

	}

	return total;

}



//    Find minimum required painters for given maxlen which is the maximum length a painter can paint.

int countPainters(vector &boards, int maxLen)

{

	int n = boards.size(), totalSum = 0, painters = 1;



	for (int i = 0; i < n; i++)

	{

		totalSum += boards[i];



		if (totalSum > maxLen)

		{

			totalSum = boards[i];

			painters++;

		}

	}



	return painters;

}



int findLargestMinDistance(vector &boards, int k)

{

	int n = boards.size();



	int low = findMax(boards, n);

	int high = findSum(boards, n);



	while (low < high)

	{

		int mid = low + (high - low) / 2;

		int reqPainters = countPainters(boards, mid);



		//    Find better optimum in lower half here mid is included because we may not get anything better.

		if (reqPainters <= k)

		{

			high = mid;

		}

		

		//    Find better optimum in upper half here mid is excluded because it gives required Painters > k, which is invalid.

		else

		{

			low = mid + 1;

		}

	}



	return low;

}

Python (3.5)

'''

    Time Complexity = O(K*(log(arrSum)))

    Space Complexity = O(1)



    Where N is the number of elements in the given array/list and arrSum is the sum of the array elements.

'''





#    Return the maximum element from the array.

def findMax(boards, n):

    max = -1e9



    for i in range(n):

        if (boards[i] > max):

            max = boards[i];



    return max;





#    Return the sum of the elements in the array.

def findSum(boards, n):

    total = 0

    for i in range(n):

        total += boards[i]

    return total



#    Find minimum required painters for given maxlen which is the maximum length a painter can paint.

def countPainters(boards, maxLen):

    n = len(boards)

    totalSum = 0

    painters = 1



    for i in range(n):

        totalSum += boards[i]



        if (totalSum > maxLen):

            totalSum = boards[i]

            painters += 1



    return painters



def findLargestMinDistance(boards, k):

    n = len(boards)



    low = findMax(boards, n)

    high = findSum(boards, n)



    while (low < high):

        mid = low + int((high - low) / 2)

        reqPainters = countPainters(boards, mid)



        #    Find better optimum in lower half here mid is included because we may not get anything better.

        if (reqPainters <= k):

            high = mid

        #    Find better optimum in upper half here mid is excluded because it gives required Painters > k, which is invalid.

        else:

            low = mid + 1

    return low

Top Google Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Google Software Developer