256. Paint House
Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 53.9%
Problem Breakdown
We are given a row of houses and an matrix where each element represents the cost to paint that specific house with Red (0), Blue (1), or Green (2). The constraint is strict: no two adjacent houses can share the same color. We need to find the global minimum total cost for painting all houses satisfying this adjacency rule.
Inputs:
costs: A list of lists, where each inner list has exactly 3 integers representing costs [Red, Blue, Green].- : The number of houses (length of outer list).
Outputs:
- An integer representing the minimum total cost to paint all validly.
Constraints & Edge Cases:
- Empty Input: Constraints state
1 <= n, so we don’t need to handle an empty array, but good practice is to check if returns 0 immediately in a production setting. - Overflow: Costs are small () and . The maximum possible sum is roughly , well within standard integer limits for any language, including Python’s arbitrary precision integers.
- Negative Numbers: Constraints say costs , so no negative values to worry about (which would complicate DP logic).
Intuition
If we try a brute-force approach where we iterate through every possible color combination for each house (), the time complexity is exponential, which will fail given . We need something polynomial.
This problem exhibits optimal substructure and overlapping subproblems, hallmarks of Dynamic Programming (DP). The decision to paint House with a specific color depends only on what we chose for House , not the entire history before that. Specifically, if we choose Red for House , we must have chosen either Blue or Green for House .
Therefore, at any house , to find the minimum cost ending with a specific color (say Red), we take:
Cost(i, Red) + min(Cost(i-1, Blue), Cost(i-1, Green)).
We can build this up iteratively from House 0 to House . At each step, we only need the minimum costs accumulated so far for the previous house’s colors. This reduces our state space significantly compared to brute force.
Approach
I will use a bottom-up DP approach with iterative updates:
- State Definition: Let
dp[i][j]be the minimum cost to paint houses through , ending with color at house . Since we only need values from row to compute row , we can optimize space by maintaining just two arrays (or modifying in-place) representing costs for colors 0, 1, and 2. - Initialization: Start with the first house (
costs[0]). The cost is simplycosts[0][j]because there are no previous houses to conflict with. - Iteration: For each subsequent house from to :
- Calculate new costs for Red, Blue, Green based on the minimum of valid colors from the previous step plus current cost.
- Update our state variables (or array) with these new values.
- Result: After processing all houses, the answer is the minimum value in the final row’s DP table.
I will implement this by creating a dp list of size 3 initialized to the first house costs, then updating it for each subsequent house. This keeps space complexity low relative to .
Complexity Analysis
- Time Complexity: , where is the number of houses. We iterate through the row once ( iterations). Inside the loop, we perform a constant amount of work (comparing 2 previous values and adding current cost) for each color (3 colors total). Since 3 is a constant factor, it simplifies to linear time with respect to .
- Space Complexity: auxiliary space. We maintain an array of size 3 (
dp) regardless of how large gets. If we were not allowed to modify the input or create new structures proportional to output size, this is optimal. (Note: Some implementations use by storing a full table, but since , it’s effectively constant).
Solution
class Solution:
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if not costs or len(costs) == 0:
return 0
# Initialize DP state with the first house's costs.
# dp[0] = min cost ending in Red,
# dp[1] = Blue, dp[2] = Green for current row being processed.
prev_costs = list(costs[0])
n = len(costs)
# Iterate through the remaining houses starting from index 1
for i in range(1, n):
curr_red_cost = costs[i][0] + min(prev_costs[1], prev_costs[2])
curr_blue_cost = costs[i][1] + min(prev_costs[0], prev_costs[2])
curr_green_cost = costs[i][2] + min(prev_costs[0], prev_costs[1])
# Update the previous state for the next iteration (current becomes previous)
prev_costs = [curr_red_cost, curr_blue_cost, curr_green_cost]
return min(prev_costs)
# Example usage:
# costs = [[17,2,17],[16,16,5],[14,3,19]]
# print(minCost(costs)) # Output: 10
Edge Cases Handled
- Single House (): The loop
range(1, n)will not execute. We return the minimum of the first house’s costs directly via initialization and final min call. This is correct as there are no adjacency constraints for a single house. - Minimum Cost Constraints: Since all input values , we don’t need to handle negative cost logic or zero-cost scenarios explicitly, though the code handles them naturally if they existed (min would just pick the smallest).
- Input Structure Validation: The solution assumes
costs[i]always has length 3 based on constraints. If this were not guaranteed, an index error could occur; however, per problem statement guarantees, we proceed with fixed indices[0], [1], [2].