In this guide, you will get 1473. Paint House III LeetCode Solution with the best time and space complexity. The solution to Paint House III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again.
A neighborhood is a maximal group of continuous houses that are painted with the same color.
Given an array houses, an m x n matrix cost and an integer target where:
houses[i]: is the color of the house i, and 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j + 1.
Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.
Example 1:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}].
Cost of paint the first and last house (10 + 1) = 11.
Example 3:
Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.
Constraints:
m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 104
Complexity Analysis
Time Complexity: O(\texttt{target} \cdot mn^2)
Space Complexity: O(tmn)
1473. Paint House III LeetCode Solution in C++
class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n,
int target) {
vector<vector<vector<int>>> mem(target + 1,
vector<vector<int>>(m, vector<int>(n + 1)));
// Initialize `prevColor` to 0 (the virtual neighbor).
const int c = minCost(houses, cost, m, n, target, 0, 0, mem);
return c == kMax ? -1 : c;
}
private:
static constexpr int kMax = 1'000'001;
// Returns the minimum cost to paint houses[i..m) into k neighborhoods, where
// there are houses[i - 1] colors = prevColor.
int minCost(const vector<int>& houses, const vector<vector<int>>& cost,
const int& m, const int& n, int k, int i, int prevColor,
vector<vector<vector<int>>>& mem) {
if (i == m || k < 0)
return k == 0 ? 0 : kMax;
if (mem[k][i][prevColor] > 0)
return mem[k][i][prevColor];
if (houses[i] > 0) // The house was painted last year.
return minCost(houses, cost, m, n, k - (prevColor != houses[i]), i + 1,
houses[i], mem);
int res = kMax;
// Try to paint the houses[i] with each color in 1..n.
for (int color = 1; color <= n; ++color)
res = min(res, cost[i][color - 1] + minCost(houses, cost, m, n,
k - (prevColor != color),
i + 1, color, mem));
return mem[k][i][prevColor] = res;
}
}; /* code provided by PROGIEZ */
1473. Paint House III LeetCode Solution in Java
class Solution {
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
int[][][] mem = new int[target + 1][m][n + 1];
// Initialize `prevColor` to 0 (the virtual neighbor).
final int c = minCost(houses, cost, m, n, target, 0, 0, mem);
return c == kMax ? -1 : c;
}
private static final int kMax = 1_000_001;
// Returns the minimum cost to paint houses[i..m) into k neighborhoods, where
// there are houses[i - 1] colors = prevColor.
public int minCost(int[] houses, int[][] cost, int m, int n, int k, int i, int prevColor,
int[][][] mem) {
if (i == m || k < 0)
return k == 0 ? 0 : kMax;
if (mem[k][i][prevColor] > 0)
return mem[k][i][prevColor];
if (houses[i] > 0) // The house was painted last year.
return minCost(houses, cost, m, n, k - (prevColor == houses[i] ? 0 : 1), i + 1, houses[i],
mem);
int ans = kMax;
// Try to paint the houses[i] with each color in 1..n.
for (int color = 1; color <= n; ++color)
ans = Math.min(ans, cost[i][color - 1] + minCost(houses, cost, m, n,
k - (prevColor == color ? 0 : 1), i + 1,
color, mem));
return mem[k][i][prevColor] = ans;
}
} // code provided by PROGIEZ
