LeetCode 2742 - Painting the Walls

The problem is asking us to determine the minimum total cost to paint n walls using two painters with different constraints. We are given two arrays: cost and time, both of size n.

leetcodehardarraydynamic-programming

LeetCode Problem 2742

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is asking us to determine the minimum total cost to paint n walls using two painters with different constraints. We are given two arrays: cost and time, both of size n. The cost[i] represents the monetary cost of hiring the paid painter to paint the ith wall, and time[i] represents how long it will take the paid painter to paint that wall. There is also a free painter who can paint any wall in exactly 1 unit of time at zero cost, but the free painter can only paint walls while the paid painter is busy.

The goal is to schedule walls between the paid and free painter to minimize total monetary cost while satisfying the timing constraints.

Key constraints include:

  1. The number of walls n is up to 500, making brute-force approaches with exponential complexity infeasible.
  2. Individual cost[i] can be as high as 10^6, and time[i] can be up to 500.
  3. Each wall must be painted exactly once.

Important edge cases to consider are when all walls have minimal or maximal times, when the cost array has extreme variations, or when the number of walls is very small (like 1).

Approaches

Brute Force

A brute-force approach would try every possible subset of walls to assign to the paid painter, computing the cost for that subset and verifying if the free painter can paint the remaining walls in parallel. This ensures correctness because we examine every assignment of walls, but it is too slow because there are 2^n possible subsets of walls, and n can be up to 500.

Key Insight for Optimization

The problem is essentially a variation of the 0-1 knapsack problem, but with a twist: the free painter introduces a time-based constraint. The paid painter's total time determines how many walls the free painter can complete simultaneously. Let total_time be the sum of the time units assigned to the paid painter. If total_time is at least n, all walls can be painted by the free painter in parallel. We need to select a subset of walls for the paid painter that minimizes total cost while ensuring the free painter's timing is sufficient.

This insight allows us to define a dynamic programming solution. Let dp[j] represent the minimum cost to achieve exactly j units of paid painter time. We iterate over each wall and update dp[j] as the minimum of including the current wall or skipping it. The final solution is the minimum dp[j] where j + free painter units >= n.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries every subset of walls; exponential time infeasible for n=500
Optimal (DP) O(n * sum(time)) O(sum(time)) Uses 1D DP over total paid painter time; efficient for n≤500 and time[i]≤500

Algorithm Walkthrough

  1. Initialize a DP array dp of length sum(time)+1, where each entry is inf except dp[0] = 0. This represents the minimum cost to achieve exactly j units of total paid painter time.
  2. Iterate through each wall i. For each wall, iterate j from sum(time) down to time[i]. Update dp[j] to be the minimum of its current value and dp[j - time[i]] + cost[i]. This ensures we consider using wall i in the subset of paid walls without overwriting previous states prematurely.
  3. After processing all walls, we look for the minimum dp[j] such that j + free_time >= n, where free_time is the number of walls the free painter can paint simultaneously, which equals the total paid painter time because free painter paints 1 wall per unit of paid painter time.
  4. Return the minimum cost found.

This works because dp[j] correctly tracks the minimum cost to accumulate j units of paid painter time, and the constraint j + free_time >= n ensures all walls can be painted.

Python Solution

from typing import List

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        max_time = sum(time)
        dp = [float('inf')] * (max_time + 1)
        dp[0] = 0

        for i in range(n):
            t = time[i]
            c = cost[i]
            for j in range(max_time, t - 1, -1):
                dp[j] = min(dp[j], dp[j - t] + c)

        res = float('inf')
        for j in range(max_time + 1):
            if j + (j) >= n:  # free painter can cover the remaining walls
                res = min(res, dp[j])
        return res

The implementation initializes a DP array to infinity, except dp[0]. For each wall, we consider adding it to the total paid painter time while updating the cost. After processing, we check which total paid painter times allow the free painter to cover remaining walls and pick the minimum cost.

Go Solution

func paintWalls(cost []int, time []int) int {
    n := len(cost)
    maxTime := 0
    for _, t := range time {
        maxTime += t
    }

    dp := make([]int, maxTime+1)
    for i := range dp {
        dp[i] = 1 << 60
    }
    dp[0] = 0

    for i := 0; i < n; i++ {
        t := time[i]
        c := cost[i]
        for j := maxTime; j >= t; j-- {
            if dp[j-t]+c < dp[j] {
                dp[j] = dp[j-t] + c
            }
        }
    }

    res := 1 << 60
    for j := 0; j <= maxTime; j++ {
        if j+j >= n {
            if dp[j] < res {
                res = dp[j]
            }
        }
    }
    return res
}

In Go, we handle large numbers by initializing dp with a very large constant instead of inf. The logic otherwise mirrors Python: iterate backwards to prevent overwriting previous states.

Worked Examples

Example 1: cost = [1,2,3,2], time = [1,2,3,2]

Step Paid Painter Time DP Array Update Comment
0 1 dp[1] = 1 Wall 0 painted by paid painter
1 2 dp[2] = 2, dp[3] = 3 Wall 1 added
2 3 dp[3] = min(3, 1+3=4)=3, dp[4]=min(inf,2+3)=5, dp[5]=5+3=8 Wall 2 considered
3 2 ... Continue updating

Check for j where j+j >= 4 (n=4), minimum cost is 3.

Example 2: cost = [2,3,4,2], time = [1,1,1,1]

DP builds combinations and the minimum cost achieving j+j >= 4 is 4.

Complexity Analysis

Measure Complexity Explanation
Time O(n * sum(time)) Each wall is processed for all possible cumulative times
Space O(sum(time)) DP array stores minimum cost for each possible total time

This is efficient because sum(time) <= 500*500=250000, which is feasible for modern computation.

Test Cases

# Provided examples
assert Solution().paintWalls([1,2,3,2], [1,2,3,2]) == 3  # basic example
assert Solution().paintWalls([2,3,4,2], [1,1,1,1]) == 4  # all same time

# Edge cases
assert Solution().paintWalls([1], [1]) == 1  # single wall
assert Solution().paintWalls([10,1,1], [1,100,100]) == 1  # free painter helps reduce cost
assert Solution().paintWalls([1000000]*5, [500]*5) == 1000000*3  # maximum values
Test Why
[1,2,3,2],[1,2,3,2] Basic scheduling and free painter usage
[2,3,4,2],[1,1,1,1] Same time walls, need careful selection
[1],[1] Minimal input
[10,1,1],[1,100,100] Free painter reduces cost substantially
[1e6]*5,[500]*5 Stress test with large values

Edge Cases

One important edge case is when there is only one wall. The solution correctly assigns it to the paid painter, as the free painter cannot start without the paid painter being busy. Another edge case is when all time[i] are large; this ensures the DP array can handle cumulative times correctly. A