Painting the Walls
Painting the Walls is a hard dynamic programming problem solved with the knapsack pattern.
The best approach, optimal (1d knapsack over covered walls), runs in O(n²) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every set of paid walls) up.
Problem
There are n walls. Wall i can be painted by a paid painter for cost[i] money in time[i] units of time, or by a free painter for no money in exactly 1 unit of time.
The free painter can only work while the paid painter is busy painting. Return the minimum total money needed to paint all n walls.
Examples
Example 1
- Input
cost = [4, 7, 2, 6], time = [1, 3, 1, 2]- Output
6- Why
- Pay for walls 0 and 2 (cost 4 + 2, 2 time units). Meanwhile the free painter does walls 1 and 3.
Example 2
- Input
cost = [5, 5, 5], time = [2, 2, 2]- Output
5- Why
- Paying for any one wall takes 2 units, enough for the free painter to finish the other two.
Example 3
- Input
cost = [10, 1, 1, 1], time = [1, 1, 1, 1]- Output
2- Why
- Pay for two of the cheap walls (2 units); the free painter does the other two, including the expensive one.
Constraints
1 <= cost.length <= 500cost.length == time.length1 <= cost[i] <= 10^61 <= time[i] <= 500
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every set of paid walls) | O(2ⁿ) | O(n) |
| Memoized recursion | O(n²) | O(n²) |
| Optimal (1D knapsack over covered walls) | O(n²) | O(n) |
1Brute force (try every set of paid walls)
O(2ⁿ)Two branches per wall.O(n)The recursion depth is n.Each wall is either paid or left to the free painter. Recurse over the walls with the number of walls still uncovered; paying for wall i reduces it by time[i] + 1. Without caching, every subset is explored.
- f(i, need): if need <= 0 return 0; if i == n return infinity.
- Skip wall i: f(i + 1, need).
- Pay for wall i: cost[i] + f(i + 1, need - time[i] - 1).
- Return the smaller one; the answer is f(0, n).
class Solution {
private static final int INF = Integer.MAX_VALUE / 2;
public int paintWalls(int[] cost, int[] time) {
return solve(cost, time, 0, cost.length);
}
private int solve(int[] cost, int[] time, int i, int need) {
if (need <= 0) return 0;
if (i == cost.length) return INF;
int skip = solve(cost, time, i + 1, need);
int pay = cost[i] + solve(cost, time, i + 1, need - time[i] - 1);
return Math.min(skip, pay);
}
}class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
n = len(cost)
INF = float("inf")
def solve(i, need):
if need <= 0:
return 0
if i == n:
return INF
skip = solve(i + 1, need)
pay = cost[i] + solve(i + 1, need - time[i] - 1)
return min(skip, pay)
return solve(0, n)class Solution {
static const int INF = INT_MAX / 2;
int solve(vector<int>& cost, vector<int>& time, int i, int need) {
if (need <= 0) return 0;
if (i == (int)cost.size()) return INF;
int skip = solve(cost, time, i + 1, need);
int pay = cost[i] + solve(cost, time, i + 1, need - time[i] - 1);
return min(skip, pay);
}
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
return solve(cost, time, 0, cost.size());
}
};function paintWalls(cost, time) {
const n = cost.length;
const solve = (i, need) => {
if (need <= 0) return 0;
if (i === n) return Infinity;
const skip = solve(i + 1, need);
const pay = cost[i] + solve(i + 1, need - time[i] - 1);
return Math.min(skip, pay);
};
return solve(0, n);
}2Memoized recursion
O(n²)n · (n + 1) states, each computed once in O(1).O(n²)The memo table plus the recursion stack.The recursion only depends on (i, need) with 0 <= need <= n, so there are O(n²) distinct states. Cache each result the first time it is computed.
- memo[i][need] starts as unknown (-1).
- Same recurrence as the brute force; clamp need at 0 and look up memo before recursing.
class Solution {
private static final int INF = Integer.MAX_VALUE / 2;
private int[][] memo;
public int paintWalls(int[] cost, int[] time) {
int n = cost.length;
memo = new int[n][n + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return solve(cost, time, 0, n);
}
private int solve(int[] cost, int[] time, int i, int need) {
if (need <= 0) return 0;
if (i == cost.length) return INF;
if (memo[i][need] != -1) return memo[i][need];
int skip = solve(cost, time, i + 1, need);
int pay = cost[i] + solve(cost, time, i + 1, need - time[i] - 1);
return memo[i][need] = Math.min(skip, pay);
}
}class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
n = len(cost)
INF = float("inf")
memo = [[-1] * (n + 1) for _ in range(n)]
def solve(i, need):
if need <= 0:
return 0
if i == n:
return INF
if memo[i][need] != -1:
return memo[i][need]
skip = solve(i + 1, need)
pay = cost[i] + solve(i + 1, need - time[i] - 1)
memo[i][need] = min(skip, pay)
return memo[i][need]
return solve(0, n)class Solution {
static const int INF = INT_MAX / 2;
vector<vector<int>> memo;
int solve(vector<int>& cost, vector<int>& time, int i, int need) {
if (need <= 0) return 0;
if (i == (int)cost.size()) return INF;
if (memo[i][need] != -1) return memo[i][need];
int skip = solve(cost, time, i + 1, need);
int pay = cost[i] + solve(cost, time, i + 1, need - time[i] - 1);
return memo[i][need] = min(skip, pay);
}
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
int n = cost.size();
memo.assign(n, vector<int>(n + 1, -1));
return solve(cost, time, 0, n);
}
};function paintWalls(cost, time) {
const n = cost.length;
const memo = Array.from({ length: n }, () => new Array(n + 1).fill(-1));
const solve = (i, need) => {
if (need <= 0) return 0;
if (i === n) return Infinity;
if (memo[i][need] !== -1) return memo[i][need];
const skip = solve(i + 1, need);
const pay = cost[i] + solve(i + 1, need - time[i] - 1);
memo[i][need] = Math.min(skip, pay);
return memo[i][need];
};
return solve(0, n);
}3Optimal (1D knapsack over covered walls)
O(n²)n walls times n + 1 states.O(n)A single array of n + 1 values.Let dp[j] be the cheapest cost to cover at least j walls using the walls seen so far. Paying for wall i moves any state j - (time[i] + 1) (clamped at 0) to j. Iterate j downward so each wall is used at most once, exactly like 0/1 knapsack.
- dp[0] = 0, dp[1..n] = infinity.
- For each wall i, for j from n down to 1: dp[j] = min(dp[j], dp[max(0, j - time[i] - 1)] + cost[i]).
- Return dp[n].
class Solution {
public int paintWalls(int[] cost, int[] time) {
int n = cost.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE / 2);
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = n; j >= 1; j--) {
int from = Math.max(0, j - time[i] - 1);
dp[j] = Math.min(dp[j], dp[from] + cost[i]);
}
}
return dp[n];
}
}class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
n = len(cost)
INF = float("inf")
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(n):
c, t = cost[i], time[i] + 1
for j in range(n, 0, -1):
cand = dp[max(0, j - t)] + c
if cand < dp[j]:
dp[j] = cand
return dp[n]class Solution {
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
int n = cost.size();
vector<int> dp(n + 1, INT_MAX / 2);
dp[0] = 0;
for (int i = 0; i < n; i++) {
for (int j = n; j >= 1; j--) {
int from = max(0, j - time[i] - 1);
dp[j] = min(dp[j], dp[from] + cost[i]);
}
}
return dp[n];
}
};function paintWalls(cost, time) {
const n = cost.length;
const dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (let i = 0; i < n; i++) {
for (let j = n; j >= 1; j--) {
const from = Math.max(0, j - time[i] - 1);
dp[j] = Math.min(dp[j], dp[from] + cost[i]);
}
}
return dp[n];
}Edge cases to test
- A single wall (you must pay for it)
- One wall with a long time that covers everything
- The most expensive wall should be given to the free painter
- All walls identical
Hints
Hint 1
The free painter only works while the paid painter is busy. If the paid painter spends T units, the free painter can paint up to T walls.
Hint 2
Paying for wall i therefore takes care of time[i] + 1 walls: itself plus time[i] free ones. You need the chosen walls to cover at least n walls.
Hint 3
This is a 0/1 knapsack: minimise cost subject to the covered count reaching n. Cap the covered count at n.
FAQ
What is the best time complexity for Painting the Walls?
Optimal (1D knapsack over covered walls) runs in O(n²) time and O(n) extra space. n walls times n + 1 states.
Which pattern does Painting the Walls use?
It is a dynamic programming problem that uses the knapsack pattern. Other problems with the same pattern: 0 - 1 Knapsack Problem, Fractional Knapsack, Knapsack with Duplicate Items.
Is there a brute force solution for Painting the Walls?
Yes. Brute force (try every set of paid walls) takes O(2ⁿ) time and O(n) space. Each wall is either paid or left to the free painter.
Which edge cases should I test for Painting the Walls?
A single wall (you must pay for it); One wall with a long time that covers everything; The most expensive wall should be given to the free painter; All walls identical.