In this guide, you will get 3429. Paint House IV LeetCode Solution with the best time and space complexity. The solution to Paint House IV 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.
You are given an even integer n representing the number of houses arranged in a straight line, and a 2D array cost of size n x 3, where cost[i][j] represents the cost of painting house i with color j + 1.
The houses will look beautiful if they satisfy the following conditions:
No two adjacent houses are painted the same color.
Houses equidistant from the ends of the row are not painted the same color. For example, if n = 6, houses at positions (0, 5), (1, 4), and (2, 3) are considered equidistant.
Return the minimum cost to paint the houses such that they look beautiful.
Example 1:
Input: n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]
Output: 9
Explanation:
The optimal painting sequence is [1, 2, 3, 2] with corresponding costs [3, 2, 1, 3]. This satisfies the following conditions:
No adjacent houses have the same color.
Houses at positions 0 and 3 (equidistant from the ends) are not painted the same color (1 != 2).
Houses at positions 1 and 2 (equidistant from the ends) are not painted the same color (2 != 3).
The minimum cost to paint the houses so that they look beautiful is 3 + 2 + 1 + 3 = 9.
Example 2:
Input: n = 6, cost = [[2,4,6],[5,3,8],[7,1,9],[4,6,2],[3,5,7],[8,2,4]]
Output: 18
Explanation:
The optimal painting sequence is [1, 3, 2, 3, 1, 2] with corresponding costs [2, 8, 1, 2, 3, 2]. This satisfies the following conditions:
No adjacent houses have the same color.
Houses at positions 0 and 5 (equidistant from the ends) are not painted the same color (1 != 2).
Houses at positions 1 and 4 (equidistant from the ends) are not painted the same color (3 != 1).
Houses at positions 2 and 3 (equidistant from the ends) are not painted the same color (2 != 3).
The minimum cost to paint the houses so that they look beautiful is 2 + 8 + 1 + 2 + 3 + 2 = 18.
Constraints:
2 <= n <= 105
n is even.
cost.length == n
cost[i].length == 3
0 <= cost[i][j] <= 105
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3429. Paint House IV LeetCode Solution in C++
class Solution {
public:
long long minCost(int n, vector<vector<int>>& costs) {
constexpr int kInvalidColor = 3;
vector<vector<vector<long>>> mem(
n / 2, vector<vector<long>>(4, vector<long>(4, -1)));
return minCost(costs, 0, kInvalidColor, kInvalidColor, mem);
}
private:
long minCost(const vector<vector<int>>& costs, int i, int prevLeftColor,
int prevRightColor, vector<vector<vector<long>>>& mem) {
if (i == costs.size() / 2)
return 0;
if (mem[i][prevLeftColor][prevRightColor] != -1)
return mem[i][prevLeftColor][prevRightColor];
long res = LONG_MAX;
for (const int leftColor : getValidColors(prevLeftColor))
for (const int rightColor : getValidColors(prevRightColor)) {
if (leftColor == rightColor)
continue;
const long leftCost = costs[i][leftColor];
const long rightCost = costs[costs.size() - 1 - i][rightColor];
res = min(res, leftCost + rightCost +
minCost(costs, i + 1, leftColor, rightColor, mem));
}
return mem[i][prevLeftColor][prevRightColor] = res;
}
vector<int> getValidColors(int prevColor) {
vector<int> validColors;
for (int color = 0; color < 3; ++color)
if (color != prevColor)
validColors.push_back(color);
return validColors;
}
}; /* code provided by PROGIEZ */
3429. Paint House IV LeetCode Solution in Java
class Solution {
public long minCost(int n, int[][] costs) {
final int kInvalidColor = 3;
Long[][][] mem = new Long[n / 2][4][4];
return minCost(costs, 0, kInvalidColor, kInvalidColor, mem);
}
private long minCost(int[][] costs, int i, int prevLeftColor, int prevRightColor,
Long[][][] mem) {
if (i == costs.length / 2)
return 0;
if (mem[i][prevLeftColor][prevRightColor] != null)
return mem[i][prevLeftColor][prevRightColor];
long res = Long.MAX_VALUE;
for (final int leftColor : getValidColors(prevLeftColor))
for (final int rightColor : getValidColors(prevRightColor)) {
if (leftColor == rightColor)
continue;
final long leftCost = costs[i][leftColor];
final long rightCost = costs[costs.length - 1 - i][rightColor];
res =
Math.min(res, leftCost + rightCost + minCost(costs, i + 1, leftColor, rightColor, mem));
}
return mem[i][prevLeftColor][prevRightColor] = res;
}
private List<Integer> getValidColors(int prevColor) {
List<Integer> validColors = new ArrayList<>();
for (int color = 0; color < 3; ++color)
if (color != prevColor)
validColors.add(color);
return validColors;
}
} // code provided by PROGIEZ
3429. Paint House IV LeetCode Solution in Python
class Solution:
def minCost(self, n: int, costs: list[list[int]]) -> int:
kInvalidColor = 3
def getValidColors(prevColor: int) -> list[int]:
return [color for color in range(3) if color != prevColor]
@functools.lru_cache(None)
def minCost(i: int, prevLeftColor: int, prevRightColor: int) -> int:
if i == len(costs) // 2:
return 0
res = math.inf
for leftColor in getValidColors(prevLeftColor):
for rightColor in getValidColors(prevRightColor):
if leftColor == rightColor:
continue
leftCost = costs[i][leftColor]
rightCost = costs[-1 - i][rightColor]
res = min(res, leftCost + rightCost +
minCost(i + 1, leftColor, rightColor))
return res
return minCost(0, kInvalidColor, kInvalidColor) # code by PROGIEZ
