Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Painter's Partition Problem

HARDProblemSolveExternal Links

Description

You are given an array arr[] where each element represents the length of a board, and an integer k representing the number of painters available.

Every painter takes exactly 1 unit of time to paint 1 unit of board length. All painters work simultaneously, and each painter can only paint a contiguous (consecutive) sequence of boards — a painter cannot skip boards or split a single board with another painter.

Your task is to find the minimum possible time required to paint all the boards.

The total time equals the maximum time any single painter spends (since they work in parallel). You need to divide the boards among k painters such that this maximum is minimized.

If there are more painters than boards, some painters simply remain idle.

Examples

Example 1

Input: arr[] = [5, 10, 30, 20, 15], k = 3
Output: 35

Explanation:
We need to split 5 boards among 3 painters so that the painter who takes the longest finishes as early as possible.

One optimal partition:

  • Painter 1 → [5, 10] → time = 15
  • Painter 2 → [30] → time = 30
  • Painter 3 → [20, 15] → time = 35

All painters work simultaneously, so the total time = max(15, 30, 35) = 35.

No other contiguous partition can reduce the maximum below 35.

Example 2

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

Explanation:
With 2 painters and 4 boards, a good partition:

  • Painter 1 → [10, 20, 30] → time = 60
  • Painter 2 → [40] → time = 40

Total time = max(60, 40) = 60.

Alternative partition [10, 20] | [30, 40] gives max(30, 70) = 70 — worse. Another option [10] | [20, 30, 40] gives max(10, 90) = 90 — even worse. The partition above is optimal.

Example 3

Input: arr[] = [100, 200, 300, 400], k = 1
Output: 1000

Explanation:
With only one painter, that painter must paint all boards sequentially. Total time = 100 + 200 + 300 + 400 = 1000.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^4
  • 1 ≤ k ≤ 10^5

Editorial

Brute Force

Intuition

The most natural way to think about this problem is: try every possible way to divide the boards among painters, and pick the division that gives the smallest maximum workload.

Imagine you have k painters standing in a line, and a row of boards in front of them. You need to place k−1 dividers among the n−1 gaps between adjacent boards, creating k contiguous groups. Each painter takes one group.

For every possible placement of those dividers, compute the sum of each group, find the maximum group sum (that's the time this arrangement takes), and track the overall minimum across all arrangements.

This is essentially choosing k−1 positions from n−1 available gaps — a combinatorial problem that tries all valid partitions.

Step-by-Step Explanation

Let's trace through with arr = [5, 10, 30, 20, 15], k = 3:

We need to place 2 dividers in 4 possible gaps (between indices 0-1, 1-2, 2-3, 3-4).

Step 1: Choose divider positions (0-1, 1-2): Groups = [5] | [10] | [30,20,15]. Sums = 5, 10, 65. Max = 65.

Step 2: Choose divider positions (0-1, 2-3): Groups = [5] | [10,30] | [20,15]. Sums = 5, 40, 35. Max = 40.

Step 3: Choose divider positions (0-1, 3-4): Groups = [5] | [10,30,20] | [15]. Sums = 5, 60, 15. Max = 60.

Step 4: Choose divider positions (1-2, 2-3): Groups = [5,10] | [30] | [20,15]. Sums = 15, 30, 35. Max = 35.

Step 5: Choose divider positions (1-2, 3-4): Groups = [5,10] | [30,20] | [15]. Sums = 15, 50, 15. Max = 50.

Step 6: Choose divider positions (2-3, 3-4): Groups = [5,10,30] | [20] | [15]. Sums = 45, 20, 15. Max = 45.

Step 7: We tried all C(4,2) = 6 combinations. The minimum of all maximums is min(65, 40, 60, 35, 50, 45) = 35, achieved at divider positions (1-2, 2-3).

Step 8: Return 35.

Brute Force — Trying All Divider Placements — Watch every possible way to split 5 boards among 3 painters. For each partition, we compute group sums and track the minimum maximum.

Algorithm

  1. Use a recursive function minTime(curr, k) that returns the minimum possible maximum time to paint boards from index curr to the end using k painters.
  2. Base cases: If curr ≥ n, return 0 (no boards left). If k == 0, return infinity (impossible — no painters).
  3. For the current painter, try assigning boards arr[curr..i] for every possible endpoint i from curr to n-1.
  4. For each choice, compute the time for this painter (sum of arr[curr..i]) and recursively solve for the remaining boards with k-1 painters.
  5. Take the maximum of the current painter's time and the recursive result (since painters work in parallel, total time is the max).
  6. Take the minimum over all choices of i — we want the partition that minimizes the maximum.
  7. Return the overall minimum.

Code

#include <bits/stdc++.h>
using namespace std;

int solve(int curr, int n, vector<int>& arr, int k) {
    // No boards left to paint
    if (curr >= n) return 0;
    // No painters available
    if (k == 0) return INT_MAX;

    int currSum = 0;
    int res = INT_MAX;

    // Try assigning boards [curr..i] to the current painter
    for (int i = curr; i < n; i++) {
        currSum += arr[i];
        int remaining = solve(i + 1, n, arr, k - 1);
        int worst = max(currSum, remaining);
        res = min(res, worst);
    }
    return res;
}

int minTime(vector<int>& arr, int k) {
    return solve(0, arr.size(), arr, k);
}
def solve(curr, n, arr, k):
    # No boards left to paint
    if curr >= n:
        return 0
    # No painters available
    if k == 0:
        return float('inf')

    curr_sum = 0
    res = float('inf')

    # Try assigning boards [curr..i] to the current painter
    for i in range(curr, n):
        curr_sum += arr[i]
        remaining = solve(i + 1, n, arr, k - 1)
        worst = max(curr_sum, remaining)
        res = min(res, worst)
    return res

def minTime(arr, k):
    return solve(0, len(arr), arr, k)
class Solution {
    static int solve(int curr, int n, int[] arr, int k) {
        // No boards left to paint
        if (curr >= n) return 0;
        // No painters available
        if (k == 0) return Integer.MAX_VALUE;

        int currSum = 0;
        int res = Integer.MAX_VALUE;

        // Try assigning boards [curr..i] to the current painter
        for (int i = curr; i < n; i++) {
            currSum += arr[i];
            int remaining = solve(i + 1, n, arr, k - 1);
            int worst = Math.max(currSum, remaining);
            res = Math.min(res, worst);
        }
        return res;
    }

    static int minTime(int[] arr, int k) {
        return solve(0, arr.length, arr, k);
    }
}

Complexity Analysis

Time Complexity: O(k^n) in the worst case — exponential.

At each recursive call, we try up to n choices for where the current painter's segment ends, and we make k levels of recursion (one per painter). This creates a tree of decisions that grows exponentially. For n = 10^5, this approach is completely infeasible.

Space Complexity: O(k) — the recursion depth equals the number of painters. Each frame stores only constant-sized local variables.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity because it explores every possible partition. The number of ways to place k−1 dividers grows astronomically with larger arrays.

However, the recursion has overlapping subproblems: the state is defined by (curr, k) — the starting board index and the number of painters remaining. Many different partition choices for earlier painters lead to the same (curr, k) subproblem. This means we're re-solving identical subproblems repeatedly.

We can add memoization to cache results for each (curr, k) pair, reducing the exponential blowup to a polynomial solution.

With memoization or tabulation, the time drops to O(n² × k) — feasible for small inputs but still problematic when n reaches 10^5. This motivates a fundamentally different approach: instead of partitioning the boards directly, we can search on the answer — guess the maximum time limit and check if it's feasible.

Better Approach - Linear Search on Answer

Intuition

Instead of deciding which boards go to which painter, flip the question: what if we fix the maximum time any painter is allowed to spend, and then check whether that time limit is achievable with at most k painters?

Think of it like a budget: you set a spending cap per painter, and greedily assign boards left to right. Each painter takes consecutive boards until adding the next would exceed the cap, then a new painter starts. If you need ≤ k painters, the budget works; otherwise, it's too tight.

The smallest valid budget is max(arr) — even if a painter only gets one board, they still need time equal to that board's length. The largest possible budget is sum(arr) — one painter does everything.

We can test every integer value from max(arr) to sum(arr), and the first value where the greedy check succeeds with ≤ k painters is our answer. This is a linear search on the answer space.

Step-by-Step Explanation

Let's trace with arr = [5, 10, 30, 20, 15], k = 3:

Search space: lo = max(arr) = 30, hi = sum(arr) = 80.

Step 1: Test limit = 30.

  • Painter 1: 5+10 = 15 ≤ 30. Add 30? 45 > 30. Stop. Painter 1 = [5,10].
  • Painter 2: 30 ≤ 30. Add 20? 50 > 30. Stop. Painter 2 = [30].
  • Painter 3: 20 ≤ 30. Add 15? 35 > 30. Stop. Painter 3 = [20].
  • Painter 4 needed for [15]. Painters used = 4 > 3. NOT feasible.

Step 2: Test limit = 31.

  • Painter 1: 5+10 = 15 ≤ 31. Add 30? 45 > 31. Stop. [5,10].
  • Painter 2: 30 ≤ 31. Add 20? 50 > 31. Stop. [30].
  • Painter 3: 20+15 = 35 > 31. So 20 ≤ 31, add 15? 35 > 31. Stop. [20].
  • Painter 4: [15]. Painters = 4 > 3. NOT feasible.

Step 3: Continue testing 32, 33, 34...

  • At limit = 35: Painter 1 = [5,10] (15), Painter 2 = [30] (30), Painter 3 = [20,15] (35). Painters = 3 ≤ 3. FEASIBLE!

Step 4: Return 35 — the first feasible limit.

Linear Search on Answer — Testing Each Time Limit — Watch as we test increasing time limits from max(arr) upward, running a greedy allocation check for each candidate until we find the first feasible one.

Algorithm

  1. Compute lo = max(arr) and hi = sum(arr).
  2. For each candidate limit X from lo to hi:
    a. Run a greedy feasibility check: scan left to right, give the current painter boards until adding the next would exceed X, then start a new painter.
    b. Count how many painters are needed.
  3. If painters needed ≤ k, return X — it's the smallest feasible limit.
  4. If no value works (impossible for valid inputs), return hi.

Code

#include <bits/stdc++.h>
using namespace std;

bool isFeasible(vector<int>& arr, int k, int limit) {
    int painters = 1;
    int currSum = 0;
    for (int i = 0; i < arr.size(); i++) {
        currSum += arr[i];
        if (currSum > limit) {
            painters++;
            currSum = arr[i];
        }
    }
    return painters <= k;
}

int minTime(vector<int>& arr, int k) {
    int lo = *max_element(arr.begin(), arr.end());
    int hi = accumulate(arr.begin(), arr.end(), 0);

    for (int limit = lo; limit <= hi; limit++) {
        if (isFeasible(arr, k, limit))
            return limit;
    }
    return hi;
}
def is_feasible(arr, k, limit):
    painters = 1
    curr_sum = 0
    for length in arr:
        curr_sum += length
        if curr_sum > limit:
            painters += 1
            curr_sum = length
    return painters <= k

def minTime(arr, k):
    lo = max(arr)
    hi = sum(arr)

    for limit in range(lo, hi + 1):
        if is_feasible(arr, k, limit):
            return limit
    return hi
import java.util.*;
import java.util.stream.*;

class Solution {
    static boolean isFeasible(int[] arr, int k, int limit) {
        int painters = 1;
        int currSum = 0;
        for (int length : arr) {
            currSum += length;
            if (currSum > limit) {
                painters++;
                currSum = length;
            }
        }
        return painters <= k;
    }

    static int minTime(int[] arr, int k) {
        int lo = Arrays.stream(arr).max().getAsInt();
        int hi = Arrays.stream(arr).sum();

        for (int limit = lo; limit <= hi; limit++) {
            if (isFeasible(arr, k, limit))
                return limit;
        }
        return hi;
    }
}

Complexity Analysis

Time Complexity: O((sum(arr) − max(arr)) × n)

In the worst case, we test every integer from max(arr) to sum(arr). For each candidate, the greedy check scans all n boards. If board lengths are large (up to 10^4) and there are many boards (up to 10^5), the answer space can be up to ~10^9 wide. That makes this approach far too slow for the given constraints.

Space Complexity: O(1) — only a few variables for the greedy check, no additional data structures.

Why This Approach Is Not Efficient

The linear search tests every integer from max(arr) to sum(arr). When board lengths are large or there are many boards, this range can span billions of values, making it impractical.

However, notice a critical monotonic property: if a time limit X is feasible (we can paint all boards with ≤ k painters), then every limit X+1, X+2, ... is also feasible — a larger budget can only make things easier. Conversely, if X is infeasible, every smaller value is also infeasible.

This monotonicity means the answer space has a clear transition point: all values below it are infeasible, all values at or above it are feasible. This is exactly the pattern binary search excels at — we can find the transition point in O(log(range)) steps instead of O(range), turning an impossibly large linear scan into a fast logarithmic search.

Optimal Approach - Binary Search on Answer

Intuition

We binary search over the answer itself — the maximum time any painter spends.

The answer must lie in the range [max(arr), sum(arr)]. For any candidate midpoint mid:

  • Run the greedy feasibility check: scan boards left to right, assigning to the current painter until adding the next board would exceed mid. When it does, start a new painter.
  • If we need ≤ k painters, mid is feasible → the answer might be even smaller, so search left.
  • If we need > k painters, mid is too small → search right.

The greedy check works because boards must be contiguous: packing as many boards as possible per painter without exceeding the limit uses the fewest painters. If even this greedy-optimal packing needs more than k painters, no valid allocation exists for that limit.

Binary search converges in O(log(sum − max)) iterations, each iteration runs the O(n) feasibility check. This gives O(n × log(sum)) total — efficient enough for n up to 10^5.

Step-by-Step Explanation

Let's trace with arr = [5, 10, 30, 20, 15], k = 3:

Search space: lo = max(arr) = 30, hi = sum(arr) = 80.

Step 1: Initialize lo = 30, hi = 80.

Step 2: mid = (30 + 80) / 2 = 55. Check feasibility:

  • Painter 1: 5+10+30 = 45 ≤ 55. Add 20? 65 > 55. Stop. Painter 1 = [5,10,30].
  • Painter 2: 20+15 = 35 ≤ 55. Done. Painters used = 2 ≤ 3.
  • Feasible! The answer could be 55 or smaller. Set hi = 55.

Step 3: lo = 30, hi = 55, mid = (30 + 55) / 2 = 42. Check feasibility:

  • Painter 1: 5+10+30 = 45 > 42. So: 5+10 = 15 ≤ 42. Add 30? 45 > 42. Stop. Painter 1 = [5,10].
  • Painter 2: 30 ≤ 42. Add 20? 50 > 42. Stop. Painter 2 = [30].
  • Painter 3: 20+15 = 35 ≤ 42. Done. Painters = 3 ≤ 3.
  • Feasible! Set hi = 42.

Step 4: lo = 30, hi = 42, mid = (30 + 42) / 2 = 36. Check feasibility:

  • Painter 1: 5+10 = 15 ≤ 36. Add 30? 45 > 36. Stop. Painter 1 = [5,10].
  • Painter 2: 30 ≤ 36. Add 20? 50 > 36. Stop. Painter 2 = [30].
  • Painter 3: 20+15 = 35 ≤ 36. Done. Painters = 3 ≤ 3.
  • Feasible! Set hi = 36.

Step 5: lo = 30, hi = 36, mid = (30 + 36) / 2 = 33. Check feasibility:

  • Painter 1: 5+10 = 15 ≤ 33. Add 30? 45 > 33. Stop. [5,10].
  • Painter 2: 30 ≤ 33. Add 20? 50 > 33. Stop. [30].
  • Painter 3: 20 ≤ 33. Add 15? 35 > 33. Stop. [20].
  • Board [15] needs Painter 4. Painters = 4 > 3.
  • NOT feasible! Set lo = 34.

Step 6: lo = 34, hi = 36, mid = (34 + 36) / 2 = 35. Check feasibility:

  • Painter 1: 5+10 = 15 ≤ 35. Add 30? 45 > 35. Stop. [5,10].
  • Painter 2: 30 ≤ 35. Add 20? 50 > 35. Stop. [30].
  • Painter 3: 20+15 = 35 ≤ 35. Done. Painters = 3 ≤ 3.
  • Feasible! Set hi = 35.

Step 7: lo = 34, hi = 35, mid = (34 + 35) / 2 = 34. Check feasibility:

  • Painter 1: 5+10 = 15 ≤ 34. Add 30? 45 > 34. Stop. [5,10].
  • Painter 2: 30 ≤ 34. Add 20? 50 > 34. Stop. [30].
  • Painter 3: 20 ≤ 34. Add 15? 35 > 34. Stop. [20].
  • Painter 4: [15]. Painters = 4 > 3. NOT feasible! Set lo = 35.

Step 8: lo = 35, hi = 35. Loop ends. Answer = 35.

Binary Search on Answer — Halving the Time Limit Range — Watch binary search narrow the range [max(arr), sum(arr)] by testing the midpoint's feasibility with a greedy painter allocation check.

Algorithm

  1. Set lo = max(arr) and hi = sum(arr).
  2. While lo < hi:
    a. Compute mid = lo + (hi - lo) / 2.
    b. Run greedy feasibility: scan boards left to right; assign to current painter until adding next board exceeds mid; start new painter.
    c. If painters needed ≤ k: mid is feasible → set hi = mid.
    d. If painters needed > k: mid too small → set lo = mid + 1.
  3. Return lo (equals hi) — the smallest feasible time limit.

Code

#include <bits/stdc++.h>
using namespace std;

bool isFeasible(vector<int>& arr, int k, long long limit) {
    int painters = 1;
    long long currSum = 0;
    for (int i = 0; i < arr.size(); i++) {
        currSum += arr[i];
        if (currSum > limit) {
            painters++;
            currSum = arr[i];
        }
    }
    return painters <= k;
}

long long minTime(vector<int>& arr, int k) {
    long long lo = *max_element(arr.begin(), arr.end());
    long long hi = accumulate(arr.begin(), arr.end(), 0LL);

    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (isFeasible(arr, k, mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}
def is_feasible(arr, k, limit):
    painters = 1
    curr_sum = 0
    for length in arr:
        curr_sum += length
        if curr_sum > limit:
            painters += 1
            curr_sum = length
    return painters <= k

def minTime(arr, k):
    lo = max(arr)
    hi = sum(arr)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(arr, k, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
import java.util.*;

class Solution {
    static boolean isFeasible(int[] arr, int k, long limit) {
        int painters = 1;
        long currSum = 0;
        for (int length : arr) {
            currSum += length;
            if (currSum > limit) {
                painters++;
                currSum = length;
            }
        }
        return painters <= k;
    }

    static long minTime(int[] arr, int k) {
        long lo = Arrays.stream(arr).max().getAsInt();
        long hi = Arrays.stream(arr).asLongStream().sum();

        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (isFeasible(arr, k, mid))
                hi = mid;
            else
                lo = mid + 1;
        }
        return lo;
    }
}

Complexity Analysis

Time Complexity: O(n × log(sum(arr)))

Binary search runs for O(log(sum − max)) iterations, which simplifies to O(log(sum)). Each iteration performs a greedy scan of all n elements. With n up to 10^5 and sum up to ~10^9, we get roughly 10^5 × 30 ≈ 3 × 10^6 operations — comfortably within time limits.

Space Complexity: O(1)

Only a constant number of variables are used: lo, hi, mid, painters, and currSum. No auxiliary data structures needed.