Paint House

Medium
575.

Paint House

Paint House is a medium coding problem on arrays and dynamic programming, asked in Amazon, Meta and LinkedIn interviews.

A row of n houses must each be painted red, blue or green. costs[i] = [red, blue, green] gives the cost of each colour for house i.

No two adjacent houses may share a colour. Return the minimum total cost.

Example 1

Input
costs = [[17,2,17],[16,16,5],[14,3,19]]
Output
10
Explanation
Blue, green, blue: 2 + 5 + 3 = 10.

Example 2

Input
costs = [[7,6,2]]
Output
2

Example 3

Input
costs = [[1,2,3],[1,2,3]]
Output
3
Explanation
Red then blue: 1 + 2 = 3.

Constraints

  • 1 <= costs.length <= 100
  • costs[i].length == 3
  • 1 <= costs[i][j] <= 20
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[][]} costs
 * @return {number}
 */
var minCost = function(costs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Paint House solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Meta.

Paint House is a medium coding problem on arrays and dynamic programming, asked in Amazon, Meta and LinkedIn interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Meta, LinkedIn
  • 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

A row of n houses must each be painted red, blue or green. costs[i] = [red, blue, green] gives the cost of each colour for house i.

No two adjacent houses may share a colour. Return the minimum total cost.

Example 1

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Blue, green, blue: 2 + 5 + 3 = 10.

Example 2

Input: costs = [[7,6,2]]
Output: 2

Example 3

Input: costs = [[1,2,3],[1,2,3]]
Output: 3
Explanation: Red then blue: 1 + 2 = 3.

Constraints

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

Hints for Paint House

  1. Hint 1

    Track the best total for each possible colour of the current house.

  2. Hint 2

    The cheapest way to end house i in red is costs[i][0] plus the cheaper of ending house i-1 in blue or green.

  3. Hint 3

    Three rolling values are enough — no table needed.

How to solve Paint House

The only thing the future needs to know about the past is the colour of the last house, so three running totals capture the whole state.

Approach

  1. Initialise r, g, b with the first house's three costs.
  2. For each later house, compute the new totals: each colour's cost plus the minimum of the other two previous totals.
  3. Update all three simultaneously — the new values must come from the old ones.
  4. Return the minimum of the three at the end.

Why it works

The adjacency rule only forbids repeating the immediately previous colour, so the optimal cost of ending at house i in a given colour depends solely on the two other colours at i-1. That is exactly the recurrence.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Overwriting r before computing g and b feeds the new value back into the same step.
  • Greedily picking the cheapest colour per house ignores the adjacency constraint and is wrong.
  • Note the column order here is [red, blue, green], matching the problem statement.

Reference solution

Python

from typing import List

def minCost(costs: List[List[int]]) -> int:
    if not costs:
        return 0
    r, g, b = costs[0]
    for i in range(1, len(costs)):
        r, g, b = (
            costs[i][0] + min(g, b),
            costs[i][1] + min(r, b),
            costs[i][2] + min(r, g),
        )
    return min(r, g, b)

Java

public static int minCost(int[][] costs) {
    if (costs.length == 0) return 0;
    int r = costs[0][0], g = costs[0][1], b = costs[0][2];
    for (int i = 1; i < costs.length; i++) {
        int nr = costs[i][0] + Math.min(g, b);
        int ng = costs[i][1] + Math.min(r, b);
        int nb = costs[i][2] + Math.min(r, g);
        r = nr; g = ng; b = nb;
    }
    return Math.min(r, Math.min(g, b));
}

C++

int minCost(vector<vector<int>>& costs) {
    if (costs.empty()) return 0;
    int r = costs[0][0], g = costs[0][1], b = costs[0][2];
    for (int i = 1; i < (int) costs.size(); i++) {
        int nr = costs[i][0] + min(g, b);
        int ng = costs[i][1] + min(r, b);
        int nb = costs[i][2] + min(r, g);
        r = nr; g = ng; b = nb;
    }
    return min(r, min(g, b));
}

JavaScript

var minCost = function(costs) {
    if (costs.length === 0) return 0;
    let r = costs[0][0], g = costs[0][1], b = costs[0][2];
    for (let i = 1; i < costs.length; i++) {
        const nr = costs[i][0] + Math.min(g, b);
        const ng = costs[i][1] + Math.min(r, b);
        const nb = costs[i][2] + Math.min(r, g);
        r = nr; g = ng; b = nb;
    }
    return Math.min(r, Math.min(g, b));
};

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