We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Paint House

Number: 256

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, Citadel

Problem Description

Given n houses and a cost matrix where costs[i][j] represents the cost of painting house i with one of three colors (red, blue, or green), find the minimum cost to paint all houses such that no two adjacent houses have the same color.

Key Insights

  • The choice for painting each house depends on the previous house's color choices.
  • Use dynamic programming to accumulate the cost while ensuring adjacent houses do not have the same color.
  • The state of each house can be represented by the minimum cost when the house is painted a specific color, computed using the minimal costs of the previous house from the other two colors.
  • The problem only requires updating the cost matrix in-place for optimal space usage.

Space and Time Complexity

Time Complexity: O(n), where n is the number of houses. Space Complexity: O(1) extra space if the input matrix is modified in place.

Solution

We use a dynamic programming approach with iterative in-place updating of the cost matrix. For each house starting from the second one, we update the cost for each color by adding the minimal cost of painting the previous house with either of the other two colors. This guarantees we never use the same color for adjacent houses while accumulating the minimal total cost. The final answer is the minimum value for the last house.

Code Solutions

# Python solution for the Paint House problem

def minCost(costs):
    # Get the number of houses
    n = len(costs)
    # Base case: If there are no houses, return 0 cost
    if n == 0:
        return 0
    
    # Iterate from the second house to the last house
    for i in range(1, n):
        # Update the cost for painting the current house red
        costs[i][0] += min(costs[i-1][1], costs[i-1][2])
        # Update the cost for painting the current house blue
        costs[i][1] += min(costs[i-1][0], costs[i-1][2])
        # Update the cost for painting the current house green
        costs[i][2] += min(costs[i-1][0], costs[i-1][1])
    
    # The answer is the minimum cost of painting the last house with any of the colors
    return min(costs[-1])

# Example usage:
example_costs = [[17,2,17],[16,16,5],[14,3,19]]
print(minCost(example_costs))  # Output: 10
← Back to All Questions