Painting the Walls Problem

Problem

You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

  • A paid painter that paints the ith wall in time[i] units of time and takes cost[i] units of money.
  • A free painter that paints any wall in 1 unit of time at a cost of 0. But the free painter can only be used if the paid painter is already occupied.

Return the minimum amount of money required to paint the n walls.

Examples

Example 1:

1
2
3
4
5

Input:
cost = [1,2,3,2], time = [1,2,3,2]
Output:
 3
Explanation: The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.

Example 2:

1
2
3
4
5

Input:
cost = [2,3,4,2], time = [1,1,1,1]
Output:
 4
Explanation: The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.

Solution

Method 1 – Dynamic Programming

Intuition

Use dynamic programming to minimize the cost by choosing which walls to paint with the paid painter, leveraging the free painter optimally.

Approach

  1. Let dp[k] be the minimum cost to paint k walls.
  2. For each wall, for each possible number of walls painted, update dp by considering painting the current wall with the paid painter (which allows the free painter to paint up to time[i] walls for free).
  3. The answer is dp[n], the minimum cost to paint all n walls.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        vector<int> dp(n+1, 1e9);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = n; k >= 0; --k) {
                int nk = min(n, k + time[i] + 1);
                dp[nk] = min(dp[nk], dp[k] + cost[i]);
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func paintWalls(cost []int, time []int) int {
    n := len(cost)
    dp := make([]int, n+1)
    for i := range dp { dp[i] = 1e9 }
    dp[0] = 0
    for i := 0; i < n; i++ {
        for k := n; k >= 0; k-- {
            nk := k + time[i] + 1
            if nk > n { nk = n }
            if dp[k]+cost[i] < dp[nk] {
                dp[nk] = dp[k]+cost[i]
            }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int paintWalls(int[] cost, int[] time) {
        int n = cost.length;
        int[] dp = new int[n+1];
        Arrays.fill(dp, (int)1e9);
        dp[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = n; k >= 0; --k) {
                int nk = Math.min(n, k + time[i] + 1);
                dp[nk] = Math.min(dp[nk], dp[k] + cost[i]);
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun paintWalls(cost: IntArray, time: IntArray): Int {
        val n = cost.size
        val dp = IntArray(n+1) { 1_000_000_000 }
        dp[0] = 0
        for (i in 0 until n) {
            for (k in n downTo 0) {
                val nk = minOf(n, k + time[i] + 1)
                dp[nk] = minOf(dp[nk], dp[k] + cost[i])
            }
        }
        return dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def paintWalls(self, cost: list[int], time: list[int]) -> int:
        n = len(cost)
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(n):
            for k in range(n, -1, -1):
                nk = min(n, k + time[i] + 1)
                dp[nk] = min(dp[nk], dp[k] + cost[i])
        return dp[n]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn paint_walls(cost: Vec<i32>, time: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut dp = vec![i32::MAX; n+1];
        dp[0] = 0;
        for i in 0..n {
            for k in (0..=n).rev() {
                let nk = std::cmp::min(n, k + time[i] as usize + 1);
                dp[nk] = dp[nk].min(dp[k] + cost[i]);
            }
        }
        dp[n]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    paintWalls(cost: number[], time: number[]): number {
        const n = cost.length;
        const dp = Array(n+1).fill(Infinity);
        dp[0] = 0;
        for (let i = 0; i < n; ++i) {
            for (let k = n; k >= 0; --k) {
                const nk = Math.min(n, k + time[i] + 1);
                dp[nk] = Math.min(dp[nk], dp[k] + cost[i]);
            }
        }
        return dp[n];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)