LeetCode 256: Paint House Solution

Master LeetCode problem 256 (Paint House), 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.

256. Paint House

Medium

Array Dynamic Programming

Problem Explanation

Explanation:

The problem asks us to paint n houses with k different colors. Each house should be painted with a certain color, and no two adjacent houses can have the same color. We are given a list of costs, where costs[i][j] represents the cost of painting house i with color j.

To minimize the total cost, we need to find the minimum cost to paint all houses without having the same color for adjacent houses.

We can solve this problem using dynamic programming. We will maintain a 2D array, dp, where dp[i][j] represents the minimum cost of painting the first i houses with the i-th house painted with color j. At each step, we will consider the minimum cost of painting the current house with each color, based on the previous house's color choices.

Finally, the minimum cost will be the minimum value in the last row of the dp array.

: :

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 256 (Paint House)?

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

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

Can I run code for LeetCode 256 on DevExCode?

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

Back to LeetCode Solutions