Painter's Partition Problem Optimal Binary Search Solution

Problem Statement❯

Given an array where each element represents the length of a board, and an integer k representing the number of painters available, your task is to allocate the boards among the painters such that:

Each painter paints only continuous sections of boards.
All painters work simultaneously.
The goal is to minimize the maximum time taken by any painter.

Assume that each unit length takes 1 unit of time to paint. Return the minimum possible time to paint all boards under these constraints.

If the input array is empty or k is zero, return 0.

Examples❯

Boards	K (Painters)	Minimum Time	Description
[10, 20, 30, 40]	2	60	Painter 1 → [10, 20, 30], Painter 2 → [40]. Max = 60
[5, 5, 5, 5]	2	10	Painter 1 → [5, 5], Painter 2 → [5, 5]. Max = 10
[10, 10, 10]	3	10	Each painter gets one board. Max = 10
[10, 20, 30, 40]	1	100	Only one painter paints all boards. Total = 100
[10, 20, 30, 40]	4	40	Each painter paints one board. Max = 40
[]	2	0	Empty board list. Nothing to paint
[5, 10]	0	0	Zero painters. Return 0
[10, 20, 30]	5	30	More painters than boards. Assign each board individually. Max = largest board = 30

Visualization Player

Solution❯

The Painter’s Partition Problem is all about assigning tasks (boards) to workers (painters) in a way that balances the load as efficiently as possible. Each painter must paint a continuous sequence of boards, and our goal is to minimize the time the most-burdened painter spends.

Understanding the Problem

Let’s say we have a list of board lengths like [10, 20, 30, 40] and two painters. One approach is to divide the boards evenly by count—but that won’t always give the best result. The key is to find a way to divide the array so that the painter who ends up with the most work has as little as possible.

This is where Binary Search helps. Instead of checking all ways to split the array (which is too slow), we search for the minimum possible time using a helper function that checks whether a given maximum time is achievable with the available painters.

Different Scenarios Explained

Normal Case: When the number of painters is less than the number of boards, we need to group boards cleverly so that all painters are used and the work is balanced. Binary search helps us test mid-values as the upper limit of work a painter can do, narrowing down to the optimal time.
One Painter: The only painter must paint all the boards. So the answer is just the sum of all board lengths.
Same Number of Painters and Boards: Each painter gets exactly one board. The result is the maximum board length.
More Painters Than Boards: Since we can’t split a board among painters, some painters won’t be used. The result is still the maximum single board length.
Empty Input: If the board list is empty, there’s nothing to paint—so we return 0.
Zero Painters: If no painter is available, the task can’t begin. We return 0 as a safe default.

By combining Binary Search with this understanding of constraints, we can efficiently find the best answer without testing every possible way to split the work.

Efficiency

This binary search method runs in O(N log S), where N is the number of boards and S is the range between the largest board and total sum. This makes it feasible for large arrays.

Algorithm Steps❯

Set low = max(board), high = sum(board).
While low ≤ high:
1. Calculate mid = (low + high) / 2.
2. Check if it's possible to paint all boards within this time limit using ≤ K painters.
3. If possible, store the result and move high = mid - 1.
4. If not, move low = mid + 1.
Return the result found as the minimum time.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def is_possible(boards, k, max_time):
    painters = 1
    curr_time = 0
    for length in boards:
        if length > max_time:
            return False  # Single board exceeds max time
        if curr_time + length > max_time:
            painters += 1
            curr_time = length  # Assign new painter
        else:
            curr_time += length
    return painters <= k

def painters_partition(boards, k):
    low = max(boards)
    high = sum(boards)
    result = high

    while low <= high:
        mid = (low + high) // 2
        if is_possible(boards, k, mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1

    return result

boards = [10, 20, 30, 40]
k = 2
print("Minimum time to paint all boards:", painters_partition(boards, k))

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(N log S)	Where N is the number of boards and S is the sum of board lengths. Binary search runs in log(S) and each feasibility check in O(N).
Average Case	O(N log S)	Feasibility check takes linear time, and binary search runs in logarithmic range space.
Worst Case	O(N log S)	Worst-case is same due to deterministic binary search iterations and linear scan in check.

Space Complexity❯

O(1)

Explanation: Only constant extra space is used for counters and limits, no additional data structures.

⬅ Previous TopicSplit Array - Minimize Largest Sum

Next Topic ⮕Minimize Maximum Distance Between Gas Stations