Painting the Walls

Hard

#2467Time: O(n^2) - The number of states is `n * (n+1)`. Each state `(i, remain)` is computed once due to memoization, and each computation takes constant time.Space: O(n^2) - The space is dominated by the memoization table `memo` of size `n x (n+1)`. The recursion depth also contributes up to `O(n)` to the call stack space.3 companies

Patterns

Dynamic Programming

Data structures

Array

Companies

Snowflake DE Shaw Media.net

Prompt

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 i^th 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.

Example 1:

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:

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.

Constraints:

1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 10⁶
1 <= time[i] <= 500

Approaches

3 approaches with complexity analysis and trade-offs.

This problem can be modeled as a variation of the classic 0/1 knapsack problem. For each wall, we have a choice: either pay to paint it or not. If we pay cost[i] for wall i, we get 1 + time[i] walls painted (one by the paid painter, time[i] by the free painter). Our goal is to select a subset of walls to pay for such that the total number of walls painted is at least n, while the total cost is minimized.

A top-down dynamic programming approach using recursion with memoization is a natural way to solve this. We define a function that explores these choices recursively, and we store the results of subproblems to avoid re-computation.

Algorithm

Define a recursive function, let's call it solve(i, remain), which calculates the minimum cost to paint remain walls using the walls from index i to n-1.
Base Cases:
- If remain <= 0, it means we have successfully painted at least n walls. The cost for this is 0, so we return 0.
- If i == n (we've considered all walls) but remain > 0, it's impossible to paint the remaining walls. We return a very large value (infinity) to indicate that this path is not a valid solution.
Recursive Step: For the wall at index i, we have two choices:
- Paint wall i: We pay cost[i]. This action paints wall i and allows the free painter to work for time[i] units, painting time[i] additional walls. In total, 1 + time[i] walls are covered. The cost for this choice is cost[i] + solve(i + 1, remain - 1 - time[i]).
- Skip wall i: We don't pay for wall i. The cost is determined by the choices for the remaining walls, which is solve(i + 1, remain).
The function solve(i, remain) returns the minimum of the costs from these two choices.
Memoization: To avoid redundant calculations for the same state (i, remain), we use a 2D array memo (e.g., of size n x (n+1)). Before computing, we check if memo[i][remain] has already been calculated. If so, we return the stored value. Otherwise, we compute the result, store it in the memo table, and then return it.
The initial call to start the process is solve(0, n).

Walkthrough

We define a recursive function solve(i, remain) that computes the minimum cost to paint remain more walls, given that we can choose from walls i through n-1. The state of our recursion is defined by the current wall index i and the number of walls remain that still need to be painted.

For each wall i, we explore two possibilities: we either pay for it or we don't.

If we pay for wall i, we incur cost[i], and the number of walls we still need to paint decreases by 1 + time[i]. The total cost for this branch is cost[i] plus the result of the recursive call for the next wall: solve(i + 1, remain - 1 - time[i]).
If we don't pay for wall i, the cost is simply the result of the recursive call for the next wall with the same remaining walls: solve(i + 1, remain).

The minimum of these two outcomes is the answer for the state (i, remain). The base cases for the recursion are when remain <= 0 (we're done, cost is 0) or when we run out of walls (i == n) but still have walls to paint (an invalid path, cost is infinity).

To make this efficient, we store the results for each state (i, remain) in a 2D memoization table. This ensures that each subproblem is solved only once.

1import java.util.Arrays;2 3class Solution {4    private int[][] memo;5    private int[] cost;6    private int[] time;7    private int n;8 9    public int paintWalls(int[] cost, int[] time) {10        this.n = cost.length;11        this.cost = cost;12        this.time = time;13        this.memo = new int[n][n + 1];14        for (int[] row : memo) {15            Arrays.fill(row, -1);16        }17        return solve(0, n);18    }19 20    private int solve(int i, int remain) {21        if (remain <= 0) {22            return 0;23        }24        if (i == n) {25            return 1_000_000_007; // A large value representing infinity26        }27        if (memo[i][remain] != -1) {28            return memo[i][remain];29        }30 31        // Option 1: Paint wall i32        int paintOption = cost[i] + solve(i + 1, remain - 1 - time[i]);33 34        // Option 2: Skip wall i35        int skipOption = solve(i + 1, remain);36 37        return memo[i][remain] = Math.min(paintOption, skipOption);38    }39}

Complexity

Time

O(n^2) - The number of states is `n * (n+1)`. Each state `(i, remain)` is computed once due to memoization, and each computation takes constant time.

Space

O(n^2) - The space is dominated by the memoization table `memo` of size `n x (n+1)`. The recursion depth also contributes up to `O(n)` to the call stack space.

Trade-offs

Pros

The logic directly follows the problem's recursive structure, making it relatively easy to understand and implement.
Guaranteed to find the optimal solution by exploring all valid choices.

Cons

The space complexity is O(n^2), which might be high for very large n.
Recursive solutions can lead to a StackOverflowError for deep recursion chains, although n=500 is generally safe in most environments.
Typically has higher constant factor overhead compared to iterative solutions due to function call stacks.

An alternative to the top-down recursive approach is a bottom-up iterative approach. This method systematically builds up the solution from the smallest subproblems to the final problem. We use a 2D array to store the results of subproblems, effectively turning the recursion into iteration. This avoids recursion overhead and the risk of stack overflow.

Algorithm

Create a 2D DP table, dp, of size (n+1) x (n+1).
dp[i][j] will store the minimum cost to paint at least j walls using the first i walls.
Initialization:
- Set dp[0][0] = 0, as it costs nothing to paint 0 walls with no walls available.
- Initialize all dp[0][j] for j > 0 to a large value (infinity), since it's impossible to paint walls without any to choose from.
- dp[i][0] for all i will be 0, as painting 0 walls always costs 0.
Iteration:
- Loop through each wall i from 1 to n.
- Inside this loop, loop through the number of walls to paint, j, from 1 to n.
- For each dp[i][j], calculate the cost based on two choices for wall i-1:
  - Skip wall i-1: The cost is inherited from the previous state, dp[i-1][j].
  - Paint wall i-1: The cost is cost[i-1] plus the cost to paint the remaining walls. Since painting wall i-1 covers 1 + time[i-1] walls, we look up the cost from dp[i-1][max(0, j - 1 - time[i-1])].
- The state transition is: dp[i][j] = min(dp[i-1][j], cost[i-1] + dp[i-1][max(0, j - 1 - time[i-1])]).
Result: The final answer is dp[n][n], which represents the minimum cost to paint at least n walls using all n available walls.

Walkthrough

We create a 2D DP table, dp, where dp[i][j] represents the minimum cost to paint at least j walls using the first i walls (from index 0 to i-1). The table size will be (n+1) x (n+1).

We initialize dp[0][0] to 0 and the rest of the first row dp[0][j] to infinity. Then, we iterate from i = 1 to n. For each wall i-1, we iterate through the target number of painted walls j from 1 to n. At each cell dp[i][j], we decide whether to include wall i-1 in our set of paid walls.

The cost if we don't pay for wall i-1 is simply dp[i-1][j].
The cost if we do pay for wall i-1 is cost[i-1] plus the cost to cover the remaining walls. Since wall i-1 covers 1 + time[i-1] walls, we need to find the cost of covering j - (1 + time[i-1]) walls using the first i-1 walls. This is given by dp[i-1][max(0, j - 1 - time[i-1])].

We take the minimum of these two options to populate dp[i][j]. After filling the entire table, the value dp[n][n] gives the minimum cost to paint at least n walls using all available walls.

1import java.util.Arrays;2 3class Solution {4    public int paintWalls(int[] cost, int[] time) {5        int n = cost.length;6        long[][] dp = new long[n + 1][n + 1];7        long infinity = Long.MAX_VALUE / 2; // Use a large value that doesn't overflow on addition8 9        for (int j = 1; j <= n; j++) {10            dp[0][j] = infinity;11        }12        // dp[i][0] is 0 for all i, which is the default13 14        for (int i = 1; i <= n; i++) {15            int c = cost[i - 1];16            int t = time[i - 1];17            for (int j = 1; j <= n; j++) {18                long paintOption = c + dp[i - 1][Math.max(0, j - 1 - t)];19                long skipOption = dp[i - 1][j];20                dp[i][j] = Math.min(paintOption, skipOption);21            }22        }23 24        return (int) dp[n][n];25    }26}

Complexity

Time

O(n^2) - We iterate through the `dp` table using two nested loops of size `n`.

Space

O(n^2) - Requires a 2D DP table of size `(n+1) x (n+1)`.

Trade-offs

Pros

Avoids recursion, eliminating the risk of stack overflow and reducing function call overhead.
The logic is systematic and can be easier to debug than a recursive solution.

Cons

The O(n^2) space complexity can be a concern for memory-constrained environments.
It is less space-efficient than the optimized 1D DP approach.

The most efficient approach in terms of memory is a space-optimized version of the bottom-up DP. Observing the recurrence relation dp[i][j] = min(dp[i-1][j], ...), we can see that computing the values for the current row i only requires values from the previous row i-1. This dependency allows us to reduce the space complexity from O(n^2) to O(n) by using only a single 1D array.

Algorithm

Create a 1D DP array, dp, of size n+1.
dp[j] will store the minimum cost to paint at least j walls.
Initialization:
- Set dp[0] = 0.
- Initialize all other elements dp[j] for j > 0 to a large value (infinity).
Iteration:
- Loop through each wall i from 0 to n-1.
- Inside this loop, have a second loop for j that iterates backwards, from n down to 1.
- The update rule is dp[j] = min(dp[j], cost[i] + dp[previous_j]), where previous_j = max(0, j - 1 - time[i]).
- Iterating j backwards is crucial. It ensures that when we calculate the new dp[j] using dp[previous_j], the value dp[previous_j] is from the state before considering wall i (equivalent to dp[i-1] in the 2D version).
Result: After iterating through all the walls, the answer is dp[n].

Walkthrough

This approach refines the 2D DP solution by using a single 1D array, dp, of size n+1. Here, dp[j] stores the minimum cost to paint at least j walls, considering the walls processed so far.

We initialize dp[0] to 0 and the rest of the array to infinity. We then iterate through each wall. For each wall i with cost[i] and time[i], we update the dp array. The key insight is to iterate the inner loop (for j) from n down to 1.

When we calculate the new value for dp[j], we consider two options:

Don't paint wall i: The cost to paint j walls remains dp[j] (its value from before this iteration).
Paint wall i: The cost is cost[i] plus the cost to paint the remaining j - (1 + time[i]) walls. This previous cost is found at dp[max(0, j - 1 - time[i])].

By iterating j backwards, we ensure that when we access dp[k] where k < j, we are accessing the value from the previous outer loop iteration (i.e., without considering wall i). This correctly mimics the behavior of using dp[i-1] from the 2D table. After iterating through all walls, dp[n] will hold the minimum cost to paint at least n walls.

1import java.util.Arrays;2 3class Solution {4    public int paintWalls(int[] cost, int[] time) {5        int n = cost.length;6        int[] dp = new int[n + 1];7        int infinity = 1_000_000_007;8        Arrays.fill(dp, infinity);9        dp[0] = 0;10 11        for (int i = 0; i < n; i++) {12            int c = cost[i];13            int t = time[i];14            for (int j = n; j > 0; j--) {15                int prevIndex = Math.max(0, j - 1 - t);16                if (dp[prevIndex] != infinity) {17                    dp[j] = Math.min(dp[j], dp[prevIndex] + c);18                }19            }20        }21 22        return dp[n];23    }24}

Complexity

Time

O(n^2) - The algorithm uses two nested loops. The outer loop runs `n` times (for each wall), and the inner loop runs `n` times (for each possible number of walls to paint).

Space

O(n) - We only need a 1D array of size `n+1` to store the DP states.

Trade-offs

Pros

Highly space-efficient, with O(n) space complexity.
Maintains the O(n^2) time efficiency of the other DP approaches.
Iterative nature avoids recursion overhead, making it very fast in practice.

Cons

The logic of iterating the inner loop backwards can be less intuitive at first glance compared to the 2D DP approach.

Solutions

Solution

1class Solution {2private3  int n;4private5  int[] cost;6private7  int[] time;8private9  Integer[][] f;10public11  int paintWalls(int[] cost, int[] time) {12    n = cost.length;13    this.cost = cost;14    this.time = time;15    f = new Integer[n][n << 1 | 1];16    return dfs(0, n);17  }18private19  int dfs(int i, int j) {20    if (n - i <= j - n) {21      return 0;22    }23    if (i >= n) {24      return 1 << 30;25    }26    if (f[i][j] == null) {27      f[i][j] = Math.min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));28    }29    return f[i][j];30  }31}

1class Solution {2public:3  int paintWalls(vector<int> &cost, vector<int> &time) {4    int n = cost.size();5    int f[n][n << 1 | 1];6    memset(f, -1, sizeof(f));7    function<int(int, int)> dfs = [&](int i, int j) -> int {8      if (n - i <= j - n) {9        return 0;10      }11      if (i >= n) {12        return 1 << 30;13      }14      if (f[i][j] == -1) {15        f[i][j] = min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));16      }17      return f[i][j];18    };19    return dfs(0, n);20  }21};

1class Solution:2    def paintWalls(self, cost: List[int], time: List[int]) -> int: @ cache def dfs(i: int, j: int) -> int: if n - i <= j: return 0 if i >= n: return inf return min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1)) n = len(cost) return dfs(0, 0)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int n;4private5  int[] cost;6private7  int[] time;8private9  Integer[][] f;10public11  int paintWalls(int[] cost, int[] time) {12    n = cost.length;13    this.cost = cost;14    this.time = time;15    f = new Integer[n][n << 1 | 1];16    return dfs(0, n);17  }18private19  int dfs(int i, int j) {20    if (n - i <= j - n) {21      return 0;22    }23    if (i >= n) {24      return 1 << 30;25    }26    if (f[i][j] == null) {27      f[i][j] = Math.min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));28    }29    return f[i][j];30  }31}

1class Solution {2public:3  int paintWalls(vector<int> &cost, vector<int> &time) {4    int n = cost.size();5    int f[n][n << 1 | 1];6    memset(f, -1, sizeof(f));7    function<int(int, int)> dfs = [&](int i, int j) -> int {8      if (n - i <= j - n) {9        return 0;10      }11      if (i >= n) {12        return 1 << 30;13      }14      if (f[i][j] == -1) {15        f[i][j] = min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));16      }17      return f[i][j];18    };19    return dfs(0, n);20  }21};

1class Solution:2    def paintWalls(self, cost: List[int], time: List[int]) -> int: @ cache def dfs(i: int, j: int) -> int: if n - i <= j: return 0 if i >= n: return inf return min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1)) n = len(cost) return dfs(0, 0)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.