LeetCode 265: Paint House II Solution

Master LeetCode problem 265 (Paint House II), a hard 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.

265. Paint House II

Hard

Array Dynamic Programming

Problem Explanation

Explanation

In this problem, we are given a row of n houses, each house can be painted with one of k colors. The cost of painting each house with a certain color is represented by a n x k cost matrix. We need to paint all houses such that no two adjacent houses have the same color, and the total cost is minimized.

To solve this problem, we can use dynamic programming. We will maintain a 2D dp array where dp[i][j] represents the minimum cost of painting the first i houses with the ith house painted with color j. At each step, we update the dp array based on the minimum cost of painting the current house with each color considering the costs of the previous houses.

Algorithm:

Initialize the dp array of size n x k with all values set to infinity except for the first row which is the same as the costs matrix.
Iterate over the houses starting from the second house.
For each house, iterate over the colors and calculate the minimum cost of painting the current house with each color considering the costs of the previous houses with different colors.
Update the dp array with the minimum cost for each house and color combination.
Finally, return the minimum cost from the last row of the dp array.

Time Complexity: O(n * k^2) where n is the number of houses and k is the number of colors. Space Complexity: O(n * k) for the dp array.

Java

Solution Code

class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        
        int[][] dp = new int[n][k];
        
        for (int j = 0; j < k; j++) {
            dp[0][j] = costs[0][j];
        }
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int prev = 0; prev < k; prev++) {
                    if (prev != j) {
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][prev] + costs[i][j]);
                    }
                }
            }
        }
        
        int minCost = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            minCost = Math.min(minCost, dp[n-1][j]);
        }
        
        return minCost;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 265 (Paint House II)?

This page provides optimized solutions for LeetCode problem 265 (Paint House II) 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 265 (Paint House II)?

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

Can I run code for LeetCode 265 on DevExCode?

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

Back to LeetCode Solutions