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 II

Number: 265

Difficulty: Hard

Paid? Yes

Companies: LinkedIn, Meta

Problem Description

Given n houses and k colors, where the cost of painting each house a specific color is provided in an n x k matrix, determine the minimum total cost to paint all houses such that no two adjacent houses share the same color.

Key Insights

  • Use dynamic programming to compute the minimum cost to paint up to each house.
  • For each house, instead of trying all colors from the previous house, track the minimum and second minimum cumulative cost from the previous house.
  • If the current color is the same as the color corresponding to the previous minimum, then use the second minimum; otherwise, use the minimum.
  • This trick allows reducing the nested loop over colors, achieving an O(nk) runtime.

Space and Time Complexity

Time Complexity: O(nk) Space Complexity: O(1) additional space (modifying the input matrix or using variables to store current and previous results)

Solution

The solution leverages dynamic programming where each row in the cost matrix is updated with the cumulative cost to reach that house painted with a particular color. Instead of a naïve O(n*k^2) approach, we optimize by keeping track of the smallest and second smallest cumulative costs from the previous house. When updating the cost for the current house:

  • If the current color is the same as the one with the smallest cost from the previous house, add the second smallest cost.
  • Otherwise, add the smallest cost. This ensures that two adjacent houses do not use the same color while still achieving the overall minimum cost.

Code Solutions

# Python solution with line-by-line comments
def minCostII(costs):
    if not costs:
        return 0

    n = len(costs)
    k = len(costs[0])
    
    # Variables to maintain the minimum and second minimum costs, and the index of the minimum cost from the previous row.
    min1, min2, min1_index = 0, 0, -1
    
    for i in range(n):
        curr_min1, curr_min2, curr_min1_index = float('inf'), float('inf'), -1
        # Iterate through colors for current house
        for j in range(k):
            # If current color j is same as previous min1 index, use min2, else use min1
            cost = costs[i][j] + (min2 if j == min1_index else min1)
            # Update current row's min and second min
            if cost < curr_min1:
                curr_min2 = curr_min1
                curr_min1 = cost
                curr_min1_index = j
            elif cost < curr_min2:
                curr_min2 = cost
        # Update variables for next iteration
        min1, min2, min1_index = curr_min1, curr_min2, curr_min1_index
    
    return min1

# Example usage:
print(minCostII([[1,5,3],[2,9,4]]))  # Output: 5
← Back to All Questions