Painting the Walls

Hard Dynamic Programming Knapsack Original on LeetCode

Reported atSnowflakeMeesho

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 <= 500
  • cost.length == time.length
  • 1 <= cost[i] <= 10^6
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (try every set of paid walls)O(2ⁿ)O(n)
Memoized recursionO(n²)O(n²)
Optimal (1D knapsack over covered walls)O(n²)O(n)

1Brute force (try every set of paid walls)

TimeO(2ⁿ)Two branches per wall.
SpaceO(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.

  1. f(i, need): if need <= 0 return 0; if i == n return infinity.
  2. Skip wall i: f(i + 1, need).
  3. Pay for wall i: cost[i] + f(i + 1, need - time[i] - 1).
  4. 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);
    }
}

2Memoized recursion

TimeO(n²)n · (n + 1) states, each computed once in O(1).
SpaceO(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.

  1. memo[i][need] starts as unknown (-1).
  2. 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);
    }
}

3Optimal (1D knapsack over covered walls)

TimeO(n²)n walls times n + 1 states.
SpaceO(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.

  1. dp[0] = 0, dp[1..n] = infinity.
  2. 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]).
  3. 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];
    }
}

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.