2742. Painting the Walls - Explanation

1. Recursion

Intuition

We have a paid painter and a free painter working simultaneously. The paid painter takes time[i] to paint wall i and costs cost[i]. The free painter paints one wall per unit time at no cost, but can only work while the paid painter is busy.

The key insight is that when the paid painter paints wall i, the free painter can paint time[i] walls during that period. So assigning wall i to the paid painter effectively handles 1 + time[i] walls total.

We use recursion to decide for each wall: either pay to paint it (and let the free painter handle time[i] additional walls), or skip it (hoping the free painter will handle it later).

Algorithm

Define dfs(i, remain) where i is the current wall index and remain is the number of walls still needing to be painted.
Base case: If remain <= 0, all walls are covered, return 0. If i == n, we have run out of walls to assign without covering everything, return infinity.
For each wall, we have two choices:
- Paint it with the paid painter: cost is cost[i] + dfs(i + 1, remain - 1 - time[i]).
- Skip it: cost is dfs(i + 1, remain).
Return the minimum of these two choices.
Start with dfs(0, n) since all n walls need to be painted.

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:

        def dfs(i, remain):
            if remain <= 0:
                return 0
            if i == len(cost):
                return float("inf")

            paint = cost[i] + dfs(i + 1, remain - 1 - time[i])
            skip = dfs(i + 1, remain)
            return min(paint, skip)

        return dfs(0, len(cost))

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems. The state (i, remain) can be reached through different paths, and we recompute the same results multiple times.

By caching results in a memoization table, we ensure each unique state is computed only once. The table has dimensions n x (n + 1) since remain ranges from 0 to n.

Algorithm

Create a 2D memoization table dp[i][remain] initialized to -1 (unvisited).
In the recursive function, first check if the result is already cached.
If not, compute the result by considering both choices (paint or skip) and cache it before returning.
The base cases remain the same: return 0 when remain <= 0, return infinity when i == n.

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        dp = {}

        def dfs(i, remain):
            if remain <= 0:
                return 0
            if i == len(cost):
                return float("inf")
            if (i, remain) in dp:
                return dp[(i, remain)]

            paint = cost[i] + dfs(i + 1, remain - 1 - time[i])
            skip = dfs(i + 1, remain)
            dp[(i, remain)] = min(paint, skip)
            return dp[(i, remain)]

        return dfs(0, len(cost))

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down solution to bottom-up by filling the DP table iteratively. Starting from the last wall and working backward, we compute the minimum cost for each state.

The recurrence relation remains the same: for each wall, we either pay to paint it or skip it, taking the minimum cost.

Algorithm

Create a 2D DP table where dp[i][remain] represents the minimum cost to paint remain walls starting from wall i.
Initialize dp[n][remain] = infinity for all remain > 0 (no walls left but still need to paint) and dp[i][0] = 0 for all i (no walls needed).
Fill the table from i = n - 1 down to i = 0 and for each value of remain from 1 to n.
For each cell, compute paint = cost[i] + dp[i + 1][max(remain - 1 - time[i], 0)] and skip = dp[i + 1][remain], then set dp[i][remain] = min(paint, skip).
Return dp[0][n].

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [[0] * (n + 2) for _ in range(n + 1)]
        for remain in range(1, n + 1):
            dp[n][remain] = float("inf")

        for i in range(n - 1, -1, -1):
            for remain in range(1, n + 1):
                paint = cost[i] + dp[i + 1][max(remain - 1 - time[i], 0)]
                skip = dp[i + 1][remain]
                dp[i][remain] = min(paint, skip)

        return dp[0][n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

Intuition

Notice that this problem resembles a 0/1 knapsack. Each wall is an item with a cost and a benefit (how many walls it covers). We need to cover exactly n walls with minimum total cost.

We can optimize space by using a 1D array. The key is to iterate remain in reverse order so that we do not overwrite values we still need in the current iteration.

Algorithm

Create a 1D DP array of size n + 2 initialized to infinity, except dp[0] = 0.
For each wall i, iterate remain from n down to 1.
Update dp[remain] = min(dp[remain], cost[i] + dp[max(remain - 1 - time[i], 0)]). This represents the choice of painting wall i with the paid painter.
The reverse iteration ensures we use the previous iteration's values for the paint choice.
Return dp[n].

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

        for i in range(n):
            for remain in range(n, 0, -1):
                paint = cost[i] + dp[max(remain - 1 - time[i], 0)]
                dp[remain] = min(paint, dp[remain])

        return dp[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

Common Pitfalls

Misunderstanding the Free Painter's Role

A critical insight is that when the paid painter paints wall i taking time[i] units, the free painter can paint time[i] additional walls simultaneously. Many fail to realize that choosing wall i for the paid painter effectively covers 1 + time[i] walls total, not just 1 wall.

Integer Overflow When Adding to Infinity

When using Integer.MAX_VALUE or similar to represent infinity, adding cost[i] to it causes integer overflow, resulting in negative values and incorrect answers. Always check if the value is infinity before performing addition, or use a sufficiently large but safe sentinel value.

Iterating in Wrong Direction for Space Optimization

In the 1D DP optimization, iterating remain from 1 to n (forward) instead of from n to 1 (backward) causes incorrect results. Forward iteration uses values from the current iteration rather than the previous one, violating the DP recurrence. The reverse iteration ensures we use the untouched previous-iteration values.

Not Capping Negative Remain Values

When remain - 1 - time[i] becomes negative, it means all walls are covered. Failing to cap this at 0 leads to accessing negative indices in the DP array. Always use max(remain - 1 - time[i], 0) to handle cases where the free painter's contribution exceeds the remaining walls.

Treating This as a Standard Knapsack Problem

While this problem resembles 0/1 knapsack, the transition is different because time values affect how much work gets done, not just costs. Applying the standard knapsack recurrence without accounting for the free painter's parallel work leads to incorrect solutions.