Paint House LeetCode Solution


Frequently asked in Amazon Google LinkedIn Oracle Twitter
Robolox Walmart Global techViews 3917

Problem Statement

Paint House LeetCode Solution – 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*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 the color green, and so on…

Return the minimum cost to paint all houses.

Example 1:

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.

Example 2:

Input:

 costs = [[7,6,2]]

Output:

 2

Approach

Idea:

The idea is that if I want to paint the current house Red, the previous House must be Blue or Green. If I want to paint the current house Blue, the previous house must be Red or Green. You get the idea. Thus, if we want to paint the current house red, we can take the min of (cost if we paint the prev blue, cost if we paint the prev green) + Cost of pain current red.

Or we can talk in terms of state change

  1. Previous House is Red => (Current House is Blue + cost of painting current Blue) OR Current House is Green + cost of painting current Green
  2. Previous House is Blue => Current House is Red + cost of painting current Red OR Current House is Green + cost of painting current Green
  3. Previous House is Green => Current House is Red + cost of painting current Red OR Current House is Blue + cost of painting current Blue

We’ll use an array to state the cost of painting houses[i] to be color r/g/b

Code

Java Program of Paint House:

class Solution {
    public int minCost(int[][] costs) {
        int N = costs.length;
        
        int r = costs[0][0];
        int b = costs[0][1];
        int g = costs[0][2];
        
        for(int i = 1; i < N; i++){
            int prevR = r;
            int prevB = b;
            int prevG = g;

            r = Math.min(prevB, prevG) + costs[i][0];
            b = Math.min(prevR, prevG) + costs[i][1];
            g = Math.min(prevR, prevB) + costs[i][2];
        }
        return Math.min(r, Math.min(b, g));
    }
}

C++ Program of Paint House:

class Solution
{
    public:
    int minCost(std::vector<std::vector<int>> &costs)
    {
        int N = costs.size();
        int r = costs[0][0];
        int b = costs[0][1];
        int g = costs[0][2];
        for (int i = 1; i < N; i++)
        {
            int prevR = r;
            int prevB = b;
            int prevG = g;
            r = min(prevB,prevG) + costs[i][0];
            b = min(prevR,prevG) + costs[i][1];
            g = min(prevR,prevB) + costs[i][2];
        }
        return min(r,min(b,g));
    }
};

Complexity Analysis for Paint House LeetCode Solution

Time Complexity

The time complexity of the above code is O(n) because it depends on the input to determine how many times we loop.

Space Complexity

The space complexity of the above code is O(n) because we are using an array to store the values.

Translate »