Painting the Walls

Hard
1088.

Painting the Walls

Painting the Walls is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

There are n walls. A paid painter takes time[i] units to paint wall i and charges cost[i]. A free painter paints any wall in 1 unit for nothing, but may only work while the paid painter is busy.

Return the minimum amount you must pay to get all n walls painted.

Example 1

Input
cost = [1,2,3,2], time = [1,2,3,2]
Output
3
Explanation
Pay for walls 0 and 1 (2 + 1 = 3 units of time), letting the free painter cover the other two.

Example 2

Input
cost = [2,3,4,2], time = [1,1,1,1]
Output
4
Explanation
Pay for two walls of cost 2 each.

Example 3

Input
cost = [5], time = [1]
Output
5
Explanation
With one wall there is nothing for a free painter to do.

Constraints

  • 1 <= cost.length <= 500
  • cost.length == time.length
  • 1 <= cost[i] <= 10^6
  • 1 <= time[i] <= 500
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cost
 * @param {number[]} time
 * @return {number}
 */
var paintWalls = function(cost, time) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Painting the Walls — Solution in Python, Java & C++

Painting the Walls solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Painting the Walls is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

There are n walls. A paid painter takes time[i] units to paint wall i and charges cost[i]. A free painter paints any wall in 1 unit for nothing, but may only work while the paid painter is busy.

Return the minimum amount you must pay to get all n walls painted.

Example 1

Input: cost = [1,2,3,2], time = [1,2,3,2]
Output: 3
Explanation: Pay for walls 0 and 1 (2 + 1 = 3 units of time), letting the free painter cover the other two.

Example 2

Input: cost = [2,3,4,2], time = [1,1,1,1]
Output: 4
Explanation: Pay for two walls of cost 2 each.

Example 3

Input: cost = [5], time = [1]
Output: 5
Explanation: With one wall there is nothing for a free painter to do.

Constraints

  • 1 <= cost.length <= 500
  • cost.length == time.length
  • 1 <= cost[i] <= 10^6
  • 1 <= time[i] <= 500

Hints for Painting the Walls

  1. Hint 1

    Paying for wall i occupies time[i] units, during which the free painter finishes time[i] other walls.

  2. Hint 2

    So choosing wall i "covers" time[i] + 1 walls in total — itself plus the free ones.

  3. Hint 3

    That is a knapsack: pick a subset whose total coverage reaches n, at minimum cost.

How to solve Painting the Walls

Choosing to pay for wall i accounts for time[i] + 1 walls: the one being painted plus the time[i] the free painter finishes meanwhile. The problem becomes a minimum-cost knapsack — cover at least n walls — with dp[j] the cheapest way to cover j of them.

Approach

  1. Set dp[0] = 0 and everything else to infinity.
  2. For each wall i, sweep j from n down to 1 and relax dp[j] with dp[max(0, j - (time[i] + 1))] + cost[i].
  3. Return dp[n].

Why it works

Clamping the predecessor index at 0 is what turns "at least" into "exactly": over-covering is free, so any surplus collapses into the dp[0] bucket rather than being lost. And the downward sweep is the standard 0/1 knapsack discipline — sweeping upward would let one paid wall be chosen twice, which the painter cannot do.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • The coverage is time[i] + 1, not time[i] — the paid wall counts itself.
  • The j loop must run downward, or a wall is reused.
  • The free painter is idle unless the paid one is working, so at least one wall must always be paid for.

Reference solution

Python

from typing import List

def paintWalls(cost: List[int], time: List[int]) -> int:
    n = len(cost)
    INF = 10**9
    dp = [INF] * (n + 1)
    dp[0] = 0
    for i in range(n):
        reach = time[i] + 1
        for j in range(n, 0, -1):
            prev = max(0, j - reach)
            if dp[prev] == INF:
                continue
            dp[j] = min(dp[j], dp[prev] + cost[i])
    return dp[n]

Java

public static int paintWalls(int[] cost, int[] time) {
    int n = cost.length;
    final int INF = 1000000000;
    int[] dp = new int[n + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int reach = time[i] + 1;
        for (int j = n; j >= 1; j--) {
            int prev = Math.max(0, j - reach);
            if (dp[prev] == INF) continue;
            dp[j] = Math.min(dp[j], dp[prev] + cost[i]);
        }
    }
    return dp[n];
}

C++

int paintWalls(vector<int>& cost, vector<int>& time) {
    int n = (int) cost.size();
    const int INF = 1000000000;
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int reach = time[i] + 1;
        for (int j = n; j >= 1; j--) {
            int prev = max(0, j - reach);
            if (dp[prev] == INF) continue;
            dp[j] = min(dp[j], dp[prev] + cost[i]);
        }
    }
    return dp[n];
}

JavaScript

var paintWalls = function(cost, time) {
    var n = cost.length, INF = 1000000000, j;
    var dp = [];
    for (j = 0; j <= n; j++) dp.push(INF);
    dp[0] = 0;
    for (var i = 0; i < n; i++) {
        var reach = time[i] + 1;
        for (j = n; j >= 1; j--) {
            var prev = j - reach > 0 ? j - reach : 0;
            if (dp[prev] === INF) continue;
            var cand = dp[prev] + cost[i];
            if (cand < dp[j]) dp[j] = cand;
        }
    }
    return dp[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming