Paint House III

Hard
1511.

Paint House III

Paint House III is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

A street has m houses in a row, and each must be painted one of n colours, labelled 1 to n. Some houses were already painted last summer and must not be repainted.

A neighbourhood is a maximal block of consecutive houses with the same colour. For example, the colours [1,2,2,3,3,2,1,1] form 5 neighbourhoods: {1}, {2,2}, {3,3}, {2}, {1,1}.

You are given houses, where houses[i] is the colour of house i or 0 if it is unpainted; an m x n matrix cost, where cost[i][j] is the price of painting house i with colour j + 1; and an integer target. Return the minimum cost of painting every unpainted house so that the street has exactly target neighbourhoods, or -1 if that is impossible.

Example 1

Input
houses = [0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1]], m = 4, n = 2, target = 2
Output
13
Explanation
Colours `[1,2,2,2]` (or `[1,1,1,2]`) make two neighbourhoods for 1 + 1 + 10 + 1 = 13.

Example 2

Input
houses = [0,2,1,0], cost = [[4,2],[3,3],[7,1],[2,6]], m = 4, n = 2, target = 3
Output
6
Explanation
Paint house 0 with colour 1 and house 3 with colour 1: `[1,2,1,1]` has three neighbourhoods.

Example 3

Input
houses = [1,2,1], cost = [[1,1],[1,1],[1,1]], m = 3, n = 2, target = 2
Output
-1
Explanation
Every house is painted already and there are three neighbourhoods.

Constraints

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4
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[]} houses
 * @param {number[][]} cost
 * @param {number} m
 * @param {number} n
 * @param {number} target
 * @return {number}
 */
var minCost = function(houses, cost, m, n, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Paint House III — Solution in Python, Java & C++

Paint House III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Paint House III is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

Problem statement

A street has m houses in a row, and each must be painted one of n colours, labelled 1 to n. Some houses were already painted last summer and must not be repainted.

A neighbourhood is a maximal block of consecutive houses with the same colour. For example, the colours [1,2,2,3,3,2,1,1] form 5 neighbourhoods: {1}, {2,2}, {3,3}, {2}, {1,1}.

You are given houses, where houses[i] is the colour of house i or 0 if it is unpainted; an m x n matrix cost, where cost[i][j] is the price of painting house i with colour j + 1; and an integer target. Return the minimum cost of painting every unpainted house so that the street has exactly target neighbourhoods, or -1 if that is impossible.

Example 1

Input: houses = [0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1]], m = 4, n = 2, target = 2
Output: 13
Explanation: Colours `[1,2,2,2]` (or `[1,1,1,2]`) make two neighbourhoods for 1 + 1 + 10 + 1 = 13.

Example 2

Input: houses = [0,2,1,0], cost = [[4,2],[3,3],[7,1],[2,6]], m = 4, n = 2, target = 3
Output: 6
Explanation: Paint house 0 with colour 1 and house 3 with colour 1: `[1,2,1,1]` has three neighbourhoods.

Example 3

Input: houses = [1,2,1], cost = [[1,1],[1,1],[1,1]], m = 3, n = 2, target = 2
Output: -1
Explanation: Every house is painted already and there are three neighbourhoods.

Constraints

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4

Hints for Paint House III

  1. Hint 1

    Going left to right, a new neighbourhood starts exactly when a house's colour differs from the previous house's colour.

  2. Hint 2

    So the state after house i needs only two numbers: the colour of house i and how many neighbourhoods exist so far.

  3. Hint 3

    dp[c][t] = cheapest cost with the current house coloured c and t neighbourhoods. For the next house and each allowed colour c2 (only its fixed colour if already painted), move from every dp[c][t] to dp[c2][t + (c != c2)], adding the paint cost (0 for a painted house).

How to solve Paint House III

Whether house i starts a new neighbourhood depends only on its colour and the colour of house i - 1. So a DP over houses whose state is (colour of the current house, neighbourhoods so far) captures everything the future needs.

Approach

  1. Let dp[c][t] be the minimum cost to paint houses 0..i with house i coloured c and exactly t neighbourhoods; start from house 0 with t = 1 for each allowed colour.
  2. For each next house i and each allowed colour c2 (every colour if houses[i] == 0, otherwise only houses[i]), with paint cost p (0 if already painted):
  3. for every previous colour c and count t with a finite dp[c][t], set t2 = t if c == c2 else t + 1; if t2 <= target, relax next[c2][t2] with dp[c][t] + p.
  4. After the last house, the answer is the minimum of dp[c][target] over all colours, or -1 if every entry is infinite.

Why it works

Two partial paintings of houses 0..i that agree on the last colour and the neighbourhood count are interchangeable for everything that follows: the future cost and the future neighbourhood changes depend on nothing else. Keeping only the cheapest one per state is therefore safe, and the transitions enumerate every colour choice for the next house.

Complexity

  • Time — O(m · n^2 · target)
  • Space — O(n · target)

Pitfalls

  • Painted houses keep their colour and cost nothing — but they still count towards neighbourhoods.
  • Discard states whose count exceeds target; they can never come back down.
  • Return -1 when no state reaches exactly target, rather than an infinity sentinel.

Reference solution

Python

from typing import List

def minCost(houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
    INF = float('inf')
    dp = [[INF] * (target + 1) for _ in range(n + 1)]
    for c in range(1, n + 1):
        if houses[0] == 0:
            dp[c][1] = cost[0][c - 1]
        elif houses[0] == c:
            dp[c][1] = 0
    for i in range(1, m):
        nd = [[INF] * (target + 1) for _ in range(n + 1)]
        for c in range(1, n + 1):
            if houses[i] != 0 and houses[i] != c:
                continue
            paint = 0 if houses[i] else cost[i][c - 1]
            for pc in range(1, n + 1):
                row = dp[pc]
                for t in range(1, target + 1):
                    if row[t] == INF:
                        continue
                    nt = t if pc == c else t + 1
                    if nt <= target and row[t] + paint < nd[c][nt]:
                        nd[c][nt] = row[t] + paint
        dp = nd
    best = min(dp[c][target] for c in range(1, n + 1))
    return -1 if best == INF else best

Java

public static int minCost(int[] houses, int[][] cost, int m, int n, int target) {
    final int INF = Integer.MAX_VALUE / 2;
    int[][] dp = new int[n + 1][target + 1];
    for (int[] row : dp) Arrays.fill(row, INF);
    for (int c = 1; c <= n; c++) {
        if (houses[0] == 0) dp[c][1] = cost[0][c - 1];
        else if (houses[0] == c) dp[c][1] = 0;
    }
    for (int i = 1; i < m; i++) {
        int[][] nd = new int[n + 1][target + 1];
        for (int[] row : nd) Arrays.fill(row, INF);
        for (int c = 1; c <= n; c++) {
            if (houses[i] != 0 && houses[i] != c) continue;
            int paint = houses[i] != 0 ? 0 : cost[i][c - 1];
            for (int pc = 1; pc <= n; pc++) {
                for (int t = 1; t <= target; t++) {
                    if (dp[pc][t] == INF) continue;
                    int nt = pc == c ? t : t + 1;
                    if (nt <= target && dp[pc][t] + paint < nd[c][nt]) nd[c][nt] = dp[pc][t] + paint;
                }
            }
        }
        dp = nd;
    }
    int best = INF;
    for (int c = 1; c <= n; c++) best = Math.min(best, dp[c][target]);
    return best == INF ? -1 : best;
}

C++

int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
    const int INF = INT_MAX / 2;
    vector<vector<int>> dp(n + 1, vector<int>(target + 1, INF));
    for (int c = 1; c <= n; c++) {
        if (houses[0] == 0) dp[c][1] = cost[0][c - 1];
        else if (houses[0] == c) dp[c][1] = 0;
    }
    for (int i = 1; i < m; i++) {
        vector<vector<int>> nd(n + 1, vector<int>(target + 1, INF));
        for (int c = 1; c <= n; c++) {
            if (houses[i] != 0 && houses[i] != c) continue;
            int paint = houses[i] != 0 ? 0 : cost[i][c - 1];
            for (int pc = 1; pc <= n; pc++) {
                for (int t = 1; t <= target; t++) {
                    if (dp[pc][t] == INF) continue;
                    int nt = pc == c ? t : t + 1;
                    if (nt <= target && dp[pc][t] + paint < nd[c][nt]) nd[c][nt] = dp[pc][t] + paint;
                }
            }
        }
        dp = nd;
    }
    int best = INF;
    for (int c = 1; c <= n; c++) best = min(best, dp[c][target]);
    return best == INF ? -1 : best;
}

JavaScript

var minCost = function(houses, cost, m, n, target) {
    var INF = Infinity;
    var fresh = function() {
        var t = [];
        for (var c = 0; c <= n; c++) t.push(new Array(target + 1).fill(INF));
        return t;
    };
    var dp = fresh();
    for (var c = 1; c <= n; c++) {
        if (houses[0] === 0) dp[c][1] = cost[0][c - 1];
        else if (houses[0] === c) dp[c][1] = 0;
    }
    for (var i = 1; i < m; i++) {
        var nd = fresh();
        for (var c = 1; c <= n; c++) {
            if (houses[i] !== 0 && houses[i] !== c) continue;
            var paint = houses[i] ? 0 : cost[i][c - 1];
            for (var pc = 1; pc <= n; pc++) {
                for (var t = 1; t <= target; t++) {
                    if (dp[pc][t] === INF) continue;
                    var nt = pc === c ? t : t + 1;
                    if (nt <= target && dp[pc][t] + paint < nd[c][nt]) nd[c][nt] = dp[pc][t] + paint;
                }
            }
        }
        dp = nd;
    }
    var best = INF;
    for (var c = 1; c <= n; c++) best = Math.min(best, dp[c][target]);
    return best === INF ? -1 : best;
};

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