Coding

Paint House II

Asked at

Expedia

Media.net

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

There are a row of **n **houses, each house can be painted with one of the **k **colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

For example, costs[1][0] is the cost of painting house 1 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on...

Return the **minimum cost **to paint all houses.

Note : Try to solve in O(nk)

Input: costs = [[1,5,3],[2,9,4]] Output: 5 Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Input: costs = [[1,3],[4,4]] Output: 5 Paint house 0 into color 0, paint house 1 into color 1. Minimum cost: 1 + 4 = 5;

**Input: **[[7,5,8],[9,9,1]]

costs.length == n
costs[i].length == k
1 <= n <= 100
2 <= k <= 20
1 <= costs[i][j] <= 20

cpp

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        // your code goes here 
    }
};

java

class Solution {
    public int minCostII(int[][] costs) {
        // your Code Goes here
    }
}

python

class Solution:
    def minCostII(self, costs):
        # your code goes here

javascript

class Solution {
    minCostII(costs) {
        // your Code Goes Here
    }
}

csharp

public class Solution
{
    public int minCostII(int[][] costs)
    {
        // User Code Goes here
    }
}

func minCostII(costs [][]int) int {
    //your code goes here
}

Stuck? Show a way to structure it+

01Keep one cost per previous color.
02Find the smallest and second-smallest values.
03Use the smallest different-color predecessor.
04Build the next color costs.
05Return the final minimum.

Reference answer

For k colors, the direct recurrence chooses the best previous color other than the current one, but checking every other color costs O(N*K^2). On each row, find the smallest previous cost, its color index, and the second-smallest cost. For a new color c, add the smallest cost unless it came from c; then add the second-smallest. This enforces the no-equal-adjacent rule while doing constant work per color. Initialize from the first row and return the minimum in the last row. The optimized complexity is O(N*K) time and O(K) space. Handle k equal to one carefully: multiple houses cannot satisfy the rule unless the specification supplies a special convention.

Then expect these follow-ups

Why is second minimum sufficient?
Tests: proof
How would you reconstruct colors?
Tests: parents

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question