How do you solve Paint House III on LeetCode?

Paint House III (LeetCode #1473) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n * target) time complexity and O(m * n * target) space complexity. Key insight: Understanding neighborhoods is crucial for solving the problem.

What is the time complexity of Paint House III?

The optimal solution for Paint House III runs in O(m * n * target) time and uses O(m * n * target) space. This complexity arises from the three nested loops iterating through houses, colors, and neighborhoods, storing results in a DP table.

What is the brute force solution for Paint House III?

The brute force approach for Paint House III is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries all possible combinations of painting the houses and counts the neighborhoods formed. This is simple but inefficient, as it explores every possible way to paint the houses. The optimal Optimal Solution approach improves this to O(m * n * target).

What algorithm or data structure is used to solve Paint House III?

Paint House III uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Backtracking.

What are the interview tips for Paint House III?

Clarify the problem statement and constraints. Discuss your thought process and approach before coding. Test your solution with edge cases after implementation.

What are common mistakes when solving Paint House III?

Not considering already painted houses correctly. Failing to handle edge cases like impossible configurations.

#1473

Paint House III

Hard

ArrayDynamic ProgrammingDynamic ProgrammingBacktracking

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(m * n * target)
Space	O(1)	O(m * n * target)

💡

Intuition

Time O(m * n * target)Space O(m * n * target)

The optimal solution uses dynamic programming to efficiently calculate the minimum cost while keeping track of neighborhoods. It avoids redundant calculations by storing results in a DP table.

⚙️

Algorithm

3 steps

1Step 1: Initialize a 3D DP array where dp[i][j][k] represents the minimum cost to paint the first i houses with j neighborhoods and the i-th house painted with color k.
2Step 2: Iterate through each house and each color, updating the DP table based on previous states.
3Step 3: Return the minimum cost from the last house with the target neighborhoods.

solution.py24 lines

1# Full working Python code
2import sys
3
4def minCost(houses, cost, m, n, target):
5    dp = [[[sys.maxsize] * (target + 1) for _ in range(n + 1)] for _ in range(m + 1)]
6    dp[0][0][0] = 0
7
8    for i in range(1, m + 1):
9        for j in range(1, n + 1):
10            for k in range(1, target + 1):
11                if houses[i - 1] != 0:
12                    color = houses[i - 1]
13                    dp[i][color][k] = min(dp[i][color][k], dp[i - 1][color][k])
14                    if color != houses[i - 2]:
15                        dp[i][color][k] = min(dp[i][color][k], dp[i - 1][houses[i - 2]][k - 1])
16                else:
17                    for color in range(1, n + 1):
18                        cost_to_paint = cost[i - 1][color - 1]
19                        dp[i][color][k] = min(dp[i][color][k], dp[i - 1][color][k] + cost_to_paint)
20                        if color != houses[i - 2]:
21                            dp[i][color][k] = min(dp[i][color][k], dp[i - 1][houses[i - 2]][k - 1] + cost_to_paint)
22
23    min_cost = min(dp[m][color][target] for color in range(1, n + 1))
24    return min_cost if min_cost != sys.maxsize else -1

ℹ

Complexity note: This complexity arises from the three nested loops iterating through houses, colors, and neighborhoods, storing results in a DP table.

1Understanding neighborhoods is crucial for solving the problem.
2Dynamic programming helps avoid redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.