Painting the Walls — Hard Problem & Solution

There are n walls. A paid painter takes time[i] units to paint wall i and charges cost[i].

Difficulty: Hard
Topics: Arrays, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Set dp[0] = 0 and everything else to infinity.
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].
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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue