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

Hiring now

Expedia has 109 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Development Engineer III - Platform Productivity Tools
India - Gurgaon
Sr Manager, Software Engineering
Austin Domain 11 - HomeAway
Software Development Engineer II
India - Gurgaon

Or practice this question first

Next question