LeetCode 3429: Paint House IV Solution

Master LeetCode problem 3429 (Paint House IV), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3429. Paint House IV

Medium

Array Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can define a 3D dp array where dp[i][j][k] represents the minimum cost to paint the houses from 0 to i (inclusive) with the color j and the color k used for houses at positions 0 and i. We can then iterate over the houses and colors to fill in this dp array and find the minimum cost.

Algorithm

Initialize a 3D dp array of size n x 3 x 3 with all values set to infinity except for dp[0][j][k] where j and k are colors used for the first house.
Iterate over the houses from 1 to n.
For each house, iterate over the current color and the previous color used for the previous house.
Update dp[i][j][k] with the minimum of dp[i][j][k] and dp[i-1][p][q] + cost[i][j] where p and q are colors for the previous house and i-th house respectively, and p != j and q != k.
Iterate over the last row of the dp array to find the minimum cost to paint all houses.

Time Complexity: O(n * 3 * 3) = O(n) where n is the number of houses. Space Complexity: O(n * 3 * 3) = O(n) for the dp array.

Solutions

Solution Code

class Solution {
    public int minCost(int n, int[][] cost) {
        int[][][] dp = new int[n][3][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (j != k) {
                    dp[0][j][k] = cost[0][j];
                }
            }
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j != k) {
                        for (int p = 0; p < 3; p++) {
                            for (int q = 0; q < 3; q++) {
                                if (p != j && q != k) {
                                    dp[i][j][k] = Math.min(dp[i][j][k], dp[i-1][p][q] + cost[i][j]);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        int minCost = Integer.MAX_VALUE;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (j != k) {
                    minCost = Math.min(minCost, dp[n-1][j][k]);
                }
            }
        }
        
        return minCost;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3429 (Paint House IV)?

This page provides optimized solutions for LeetCode problem 3429 (Paint House IV) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3429 (Paint House IV)?

The time complexity for LeetCode 3429 (Paint House IV) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3429 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3429 in Java, C++, or Python.

Back to LeetCode Solutions