☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Painter's Partition

Medium TUF ID 805 A2Z

Java source ↗ Edit this article ↗

Problem

There are n boards laid out in a row; boards[i] is the length of the i-th board. You have k painters, and every painter paints one unit of length per unit of time. Each painter must paint a contiguous block of boards, and every board is painted by exactly one painter. All painters work at the same time, so the job is finished when the painter with the most work finishes. Choose the blocks so that this finishing time is as small as possible, and return it.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ boards[i] ≤ 10^9, 1 ≤ k ≤ 10^5. The total length can exceed the range of a 32-bit integer, so sums must be computed in long.

Example 1

boards = [10, 20, 30, 40], k = 2
answer = 60          // painter 1 takes [10, 20, 30] = 60, painter 2 takes [40]

Example 2

boards = [5, 5, 5, 5], k = 2
answer = 10          // [5, 5] and [5, 5]; two boards each is the best possible balance

Example 3

boards = [48, 90], k = 1
answer = 138         // a single painter paints everything

If k is larger than n, the extra painters simply have nothing to do; the answer is then the longest single board. Unlike the book allocation version, nothing is impossible here.

The check that both approaches share

Fix a time budget T. Can the boards be handed out so that no painter needs more than T units of time? Walk the boards from left to right and keep giving boards to the current painter while the running total stays within T. When the next board would push the total over T, hand it to a fresh painter. This greedy packing uses the fewest painters possible for the budget T: at every step the current painter has taken as many boards as the budget allows, so the next painter starts as far right as possible, and by induction every painter starts no earlier than in any other valid assignment.

static int paintersNeeded(int[] boards, long maxLength) {
    int painters = 1;
    long load = 0;
    for (int b : boards) {
        if (load + b > maxLength) { painters++; load = 0; }
        load += b;
    }
    return painters;
}

The helper assumes maxLength is at least the longest board, so that a lone board always fits a painter. Both callers guarantee that. If paintersNeeded(boards, T) <= k, the budget T is achievable: unused painters may idle, and splitting a block between two painters never raises anyone’s load.

Approach 1: Brute force over the answer

Intuition. The finishing time is somebody’s total load, so it is at least the longest board (whoever paints that board needs at least that long) and at most the total length (one painter does everything). Try every integer budget in that range from the bottom up; the first budget that needs at most k painters is the minimum finishing time.

Algorithm.

  1. Compute max and sum of the board lengths, as long.
  2. For limit = max, max + 1, ..., sum: if paintersNeeded(boards, limit) <= k, return limit.
static long bruteForce(int[] boards, int k) {
    long max = 0, sum = 0;
    for (int b : boards) { max = Math.max(max, b); sum += b; }
    for (long limit = max; limit <= sum; limit++) {
        if (paintersNeeded(boards, limit) <= k) return limit;
    }
    return sum;
}

Complexity. Time O(n × (sum − max)): one linear check per candidate budget. Space O(1).

With lengths up to 10^9 the range can hold billions of candidates, so this is far too slow, but it tells us exactly what the search space is and gives us a cheap test for any point in it.

Approach 2: Optimal, binary search on the answer

Intuition. As the budget T grows, each painter can take more boards, so the number of painters needed never goes up. The predicate “paintersNeeded(boards, T) <= k” is therefore false for every T below some threshold and true for every T at or above it. Binary search finds that threshold with about log2(sum) checks instead of scanning the whole range.

Algorithm.

  1. Compute max and sum. Set lo = max, hi = sum, ans = sum.
  2. While lo <= hi: let mid be the midpoint.
    • If paintersNeeded(boards, mid) <= k, then mid is achievable: store ans = mid and try smaller budgets with hi = mid − 1.
    • Otherwise mid is too small: lo = mid + 1.
  3. Return ans.
static long optimal(int[] boards, int k) {
    long max = 0, sum = 0;
    for (int b : boards) { max = Math.max(max, b); sum += b; }
    long lo = max, hi = sum, ans = sum;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (paintersNeeded(boards, mid) <= k) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on boards = [10, 20, 30, 40], k = 2. Here max = 40, sum = 100.

lo hi mid greedy blocks within mid painters ≤ 2? action
40 100 70 [10,20,30] [40] 2 yes ans = 70, hi = 69
40 69 54 [10,20] [30] [40] 3 no lo = 55
55 69 62 [10,20,30] [40] 2 yes ans = 62, hi = 61
55 61 58 [10,20] [30] [40] 3 no lo = 59
59 61 60 [10,20,30] [40] 2 yes ans = 60, hi = 59
59 59 59 [10,20] [30] [40] 3 no lo = 60

lo > hi, so the answer is 60.

Complexity. Time O(n log(sum)): roughly log2(sum − max) probes, each a linear pass over the boards. Space O(1).

Why does the smallest achievable budget equal the true optimum? Any real assignment with finishing time F shows that the budget F is achievable, so the smallest achievable budget is at most the optimum. Conversely, the greedy assignment for the smallest achievable budget is a real assignment whose finishing time is at most that budget, so the optimum is at most the smallest achievable budget. The two are equal.

Edge cases and pitfalls