The Painter’s Partition Problem-II | GeeksforGeeks Solution Explained

The “Painter’s Partition Problem-II” is a classic binary search and partitioning problem often asked in coding interviews.

In this blog, we’ll 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.

Here’s the [Problem Link] to begin with.

Problem Statement

Dilpreet wants to paint his dog’s home that has n boards with different lengths. The length of i^th board is given by arr[i] where arr[] is an array of n integers. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board.

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] or only board [1] or nothing but not boards [2,4,5].

Examples:

Input: arr[] = [5, 10, 30, 20, 15], k = 3
Output: 35
Explanation: 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

Input: arr[] = [10, 20, 30, 40], k = 2
Output: 60
Explanation: The most optimal way to paint: Painter 1 allocation : [10,20,30], Painter 2 allocation : [40], Job will be complete at time = 60

Input: arr[] = [100, 200, 300, 400], k = 1
Output: 1000
Explanation: 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.

Constraints:
1 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i] ≤ 10⁵
1 ≤ k ≤ 10⁵

Brute Force Solution (Try Every Possible Maximum Time)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Possible Maximum Time:
   Try every possible maximum time from the largest single board to the sum of all boards.
2. Check If Allocation Is Possible:
   For each time, check if it is possible to allocate boards to painters so that no painter paints more than that much time.
3. Return the First Valid Maximum:
   The first value for which allocation is possible is our answer.
4. Why does this work?
   We check every possible value, so we’re sure to find the minimum one that works.

This approach is easy to understand but not efficient for large inputs.

Code Implementation

class Solution:
    def canPaint(self, arr, k, max_time):
        total = 0
        painters = 1
        for length in arr:
            if length > max_time:
                return False
            if total + length <= max_time:
                total += length
            else:
                painters += 1
                total = length
                if painters > k:
                    return False
        return True

    def minTime(self, arr, k):
        start = max(arr)
        end = sum(arr)
        min_time = end

        for time in range(start, end + 1):
            if self.canPaint(arr, k, time):
                min_time = time
                break

        return min_time

Code Explanation

• For each possible maximum time from the largest board to the total length, check if you can allocate boards to at most k painters.
• The helper function canPaint simulates the allocation process.
• Return the smallest maximum time for which allocation is possible.

Dry Run

Input:
arr = , k = 2

• Try time = 40: Need 3 painters (not enough)
• Try time = 60: Need 2 painters (just right, return 60)

Final Output:
60

Time and Space Complexity

• Time Complexity: O((sum(arr) – max(arr)) * n)
  For each possible max, we check all boards.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs, but it’s too slow for large values.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search on Maximum Time:
   The answer lies between the largest single board and the total length. Use binary search to find the minimum maximum time.
2. Check If Allocation Is Possible:
   For each mid value (time), check if it’s possible to allocate boards to painters.
3. Adjust Search Window:
   • If allocation is possible, try a smaller maximum.
   • If not, try a larger maximum.
4. Why does this work?
   The allocation function is monotonic: as the maximum time increases, it becomes easier to allocate. Binary search is perfect for this.

Code Implementation

class Solution:
    def canPaint(self, arr, k, max_time):
        painters = 1
        curr_sum = 0
        for length in arr:
            if length > max_time:
                return False
            if curr_sum + length > max_time:
                painters += 1
                curr_sum = length
                if painters > k:
                    return False
            else:
                curr_sum += length
        return True

    def minTime(self, arr, k):
        low = max(arr)
        high = sum(arr)
        result = high

        while low <= high:
            mid = (low + high) // 2
            if self.canPaint(arr, k, mid):
                result = mid
                high = mid - 1
            else:
                low = mid + 1
        return result

Code Explanation

• Use binary search between the largest board and the total length.
• For each mid value, simulate the allocation process.
• If allocation is possible, try a smaller maximum.
• If not, try a larger maximum.
• Return the minimum valid maximum found.

Dry Run

Input:
arr =[10, 20, 30, 40], k = 2

• low = 40, high = 100
• mid = 70: Can allocate with 2 painters (try smaller, high = 69)
• mid = 54: Need 3 painters (try larger, low = 55)
• mid = 62: Can allocate with 2 painters (try smaller, high = 61)
• mid = 58: Need 3 painters (try larger, low = 59)
• mid = 60: Can allocate with 2 painters (try smaller, high = 59)
• mid = 59: Need 3 painters (try larger, low = 60)
• low = 60, high = 59 → loop ends, answer is 60

Final Output:
60

Time and Space Complexity

• Time Complexity: O(n * log(sum(arr) – max(arr)))
  Binary search on maximum, checking all boards for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.

Final Thoughts

The “Painter’s Partition Problem-II” is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.