Skip to main content

Paint House

Description​

  • 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.

Example:​

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

Constraints:​

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

Solution​

Approach​

To solve the "Paint House" problem efficiently, we can use dynamic programming to keep track of the minimum cost to paint each house while ensuring no two adjacent houses have the same color. Here's the step-by-step approach to implement this solution:

Approach:​

  1. Initialization:

    • Use the given cost matrix to keep track of the costs. Initialize variables to store the costs of painting the previous house red, blue, or green.

  2. Dynamic Programming:

    • Iterate through each house starting from the second one, updating the minimum cost to paint the current house with each color based on the previous house's costs.
    • For each house, calculate the cost to paint it red, blue, or green as the current cost plus the minimum of the other two costs from the previous house.

  3. Result:

    • The answer will be the minimum cost to paint the last house with any of the three colors.
Written by @sivaprasath
function minCost(costs) {
    if (costs.length === 0) return 0;

    let n = costs.length;

    // Initial cost for the first house
    let previousRed = costs[0][0];
    let previousBlue = costs[0][1];
    let previousGreen = costs[0][2];

    for (let i = 1; i < n; i++) {
        let currentRed = costs[i][0] + Math.min(previousBlue, previousGreen);
        let currentBlue = costs[i][1] + Math.min(previousRed, previousGreen);
        let currentGreen = costs[i][2] + Math.min(previousRed, previousBlue);

        // Update previous costs to current costs for the next iteration
        previousRed = currentRed;
        previousBlue = currentBlue;
        previousGreen = currentGreen;
    }

    // The minimum cost of the last house can be any color
    return Math.min(previousRed, previousBlue, previousGreen);
}

// Example usage:
const costs1 = [[17, 2, 17], [16, 16, 5], [14, 3, 19]];
console.log(minCost(costs1)); // Output: 10

const costs2 = [[7, 6, 2]];
console.log(minCost(costs2)); // Output: 2

Explanation:​

  • Initialization: We start by assigning the costs of painting the first house to previousRed, previousBlue, and previousGreen.
  • Dynamic Programming: For each subsequent house, we calculate the cost of painting it each color based on the minimum cost of painting the previous house a different color.
    • currentRed = costs[i][0] + Math.min(previousBlue, previousGreen)
    • currentBlue = costs[i][1] + Math.min(previousRed, previousGreen)
    • currentGreen = costs[i][2] + Math.min(previousRed, previousBlue)
  • Result: After processing all the houses, the minimum cost of painting the last house can be either red, blue, or green. The final result is the minimum of these three values.

Complexity:​

  • Time Complexity: O(n), where n is the number of houses. We only make a single pass through the houses.
  • Space Complexity: O(1), as we use a constant amount of additional space regardless of the number of houses.

References​

Author:

Loading...