Coding

Paint House

Asked at

Uber

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. 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 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Return the minimum cost to paint all houses.

Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.

Input: costs = [[7,6,2]] Output: 2 Explaination : Painting house 0 into green is minimum cost possibe .

Input: costs = [[13,19,11],[13,16,7],[14,12,19],[17,20,17],[16,16,5],[14,3,19]]

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

cpp

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

java

class Solution {
    public int minCost(int[][] costs) {
        // Your code goes here
    }
}

python

class Solution(object):
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        # Your code goes here

javascript

/**
 * @param {number[][]} costs
 * @return {number}
 */
var minCost = function(costs) {
    // Your code goes here
};

csharp

public class Solution
{
    public int MinCost(int[][] costs)
    {
        // Your code goes here
    }
}

func minCost(costs [][]int) int {
}

Stuck? Show a way to structure it+

01Set DP for the first house to its paint costs.
02For each later house, choose the cheaper different previous color.
03Update all three color states from old values.
04Use temporary values before overwriting.
05Return the minimum final state.

Reference answer

For three colors, maintain the minimum total cost of painting houses through the previous index with each possible ending color: red, blue, and green. For a new house, its red state is cost[i][red] + min(oldBlue, oldGreen), and analogously for the other colors. Store old states first so one update does not contaminate another. Initialization is simply the first house's three costs; the result is the minimum of the final three states. The recurrence captures the only constraint, that adjacent houses cannot share a color, so no wider history is needed. It runs in O(N) time and O(1) extra space. Validate empty input according to the contract, and use a wide total type if costs can accumulate beyond int.

Then expect these follow-ups

How would you reconstruct color choices?
Tests: parents
How does k colors change the complexity?
Tests: minima tracking

Hiring now

Software engineer roles are open 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.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question