Paint House

Medium Dynamic Programming 1D DP Original on LeetCode

Reported atLinkedInShopify

Paint House is a medium dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (dp with three running totals), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every coloring) up.

Problem

A row of n houses must each be painted in one of three colors (numbered 0, 1 and 2). Painting house i in color j costs costs[i][j].

No two adjacent houses may share a color. Return the minimum total cost to paint every house.

Examples

Example 1

Input
costs = [[4, 9, 3], [8, 2, 7], [5, 6, 1]]
Output
6
Why
Paint house 0 with color 2 (3), house 1 with color 1 (2), house 2 with color 2 (1): 3 + 2 + 1 = 6, and no neighbours share a color.

Example 2

Input
costs = [[5, 1, 9], [6, 1, 8]]
Output
6
Why
Both houses want color 1, but they are neighbours. Giving it to the second house costs 5 + 1 = 6, which beats 1 + 6 = 7.

Example 3

Input
costs = [[12, 4, 7]]
Output
4
Why
A single house simply takes its cheapest color.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every coloring)O(3 · 2^n)O(n)
Optimal (DP with three running totals)O(n)O(1)

1Brute force (try every coloring)

TimeO(3 · 2^n)The first house has 3 choices and every later house has 2, and each valid coloring is visited.
SpaceO(n)The recursion goes n levels deep.

Recursively choose a color for each house, skipping the color used by the previous house, and keep the cheapest total. This explores every valid coloring.

  1. paint(i, prev): if i == n, return 0.
  2. For each color c != prev, compute costs[i][c] + paint(i + 1, c).
  3. Return the minimum of those values.
  4. The answer is paint(0, -1).
class Solution {
    public int minCost(int[][] costs) {
        return paint(costs, 0, -1);
    }

    private int paint(int[][] costs, int i, int prev) {
        if (i == costs.length) return 0;
        int best = Integer.MAX_VALUE;
        for (int c = 0; c < 3; c++) {
            if (c == prev) continue;
            best = Math.min(best, costs[i][c] + paint(costs, i + 1, c));
        }
        return best;
    }
}

2Optimal (DP with three running totals)

TimeO(n)Constant work per house.
SpaceO(1)Three running totals, updated in place.

Keep, for the houses processed so far, the cheapest total that ends in each of the three colors. The next house in color c adds its cost to the cheaper of the two totals that end in a different color. Only the previous row is needed, so three numbers carry the whole state.

  1. a, b, c = costs[0][0], costs[0][1], costs[0][2].
  2. For each next house i: na = costs[i][0] + min(b, c), nb = costs[i][1] + min(a, c), nc = costs[i][2] + min(a, b).
  3. Replace a, b, c with na, nb, nc.
  4. Return min(a, b, c).
class Solution {
    public int minCost(int[][] costs) {
        int a = costs[0][0], b = costs[0][1], c = costs[0][2];
        for (int i = 1; i < costs.length; i++) {
            int na = costs[i][0] + Math.min(b, c);
            int nb = costs[i][1] + Math.min(a, c);
            int nc = costs[i][2] + Math.min(a, b);
            a = na;
            b = nb;
            c = nc;
        }
        return Math.min(a, Math.min(b, c));
    }
}

Edge cases to test

  • A single house: the minimum of its three costs
  • Neighbours that both prefer the same color, so one of them has to settle for its second choice
  • Greedy (cheapest color per house, avoiding only the previous house's color) can lose, because an early cheap pick may force an expensive later one
  • All costs equal

Hints

Hint 1

Greedily picking the cheapest allowed color house by house can fail. Try a case where house 1 strongly needs the color house 0 would grab.

Hint 2

Only the color of the previous house matters for the next decision. Define best[i][c] = cheapest way to paint houses 0..i with house i in color c.

Hint 3

best[i][c] = costs[i][c] + min of best[i - 1] over the two other colors. You only need the previous row, so three variables are enough.

FAQ

What is the best time complexity for Paint House?

Optimal (DP with three running totals) runs in O(n) time and O(1) extra space. Constant work per house.

Which pattern does Paint House use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Paint House?

Yes. Brute force (try every coloring) takes O(3 · 2^n) time and O(n) space. Recursively choose a color for each house, skipping the color used by the previous house, and keep the cheapest total.

Which edge cases should I test for Paint House?

A single house: the minimum of its three costs; Neighbours that both prefer the same color, so one of them has to settle for its second choice; Greedy (cheapest color per house, avoiding only the previous house's color) can lose, because an early cheap pick may force an expensive later one; All costs equal.