coderz.py

Keep Coding Keep Cheering!

Minimum Cost to Paint Houses with K Colors

发布于 March 9, 2025 | 作者 Hassan Raza | 分类: Data Structure, dsa, Facebook
DSA Sheet

Problem Statement (Asked By Facebook)

A builder plans to construct N houses in a row, where each house can be painted in K different colors. The goal is to minimize the total painting cost, ensuring that no two adjacent houses have the same color.

You are given an N × K matrix, where:

  • Each row represents a house (n), and
  • Each column represents a color (k).
  • The value at matrix[n][k] indicates the cost to paint house n with color k.

Return the minimum total cost to paint all N houses while satisfying the constraint that no two consecutive houses have the same color.

Problem link: https://leetcode.com/problems/paint-house-iii/description/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

Brute Force Approach: O(K^N) Time Complexity

Step-by-Step Explanation

  1. Try Every Possible Combination of Colors
    • For each house, try every possible color.
    • Ensure that no two adjacent houses have the same color.
    • Compute the cost for each valid combination.
  2. Inefficiency
    • Exponential Growth: O(K^N) due to recursive branching.
    • Overlapping Subproblems: Redundant calculations for different color choices.

Java Code (Brute Force Recursive)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class PaintHousesBruteForce {
    public static int minCostToPaint(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        return helper(costs, 0, -1);
    }
 
    private static int helper(int[][] costs, int house, int prevColor) {
        if (house == costs.length) return 0; // All houses painted
 
        int minCost = Integer.MAX_VALUE;
        for (int color = 0; color < costs[0].length; color++) {
            if (color != prevColor) { // Ensure adjacent houses have different colors
                int currentCost = costs[house][color] + helper(costs, house + 1, color);
                minCost = Math.min(minCost, currentCost);
            }
        }
        return minCost;
    }
 
    public static void main(String[] args) {
        int[][] costs = {
            {1, 3, 5},
            {2, 9, 4},
            {8, 3, 6},
            {4, 7, 2}
        };
        System.out.println(minCostToPaint(costs)); // Output: 8 (but inefficient)
    }
}

Dynamic Programming Approach (O(NK²) Time Complexity)

Step-by-Step Explanation

  1. Define DP Matrix (dp[i])
    • Represents minimum cost to paint house iii with color ccc.
  2. Transition Formula
    • Compute the cost for house iii by taking the minimum cost of painting previous houses, excluding the current color.
    dp[i]=cost[i]+min⁡(dp[i−1]),c′≠cdp[i] = \text{cost}[i] + \min(dp[i-1]), \quad c’ \neq cdp[i]=cost[i]+min(dp[i−1]),c′=c
  3. Final Result
    • The answer is the minimum value in the last row.

Java Code (O(NK²) DP Solution)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class PaintHousesDP {
    public static int minCostToPaint(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
 
        int N = costs.length, K = costs[0].length;
        int[][] dp = new int[N][K];
 
        // Copy first row (base case)
        System.arraycopy(costs[0], 0, dp[0], 0, K);
 
        for (int i = 1; i < N; i++) {
            for (int c = 0; c < K; c++) {
                int minCost = Integer.MAX_VALUE;
 
                for (int prevC = 0; prevC < K; prevC++) {
                    if (prevC != c) {
                        minCost = Math.min(minCost, dp[i - 1][prevC]);
                    }
                }
                dp[i] = costs[i] + minCost;
            }
        }
 
        // Return the minimum value from the last row
        int minCost = Integer.MAX_VALUE;
        for (int cost : dp[N - 1]) {
            minCost = Math.min(minCost, cost);
        }
        return minCost;
    }
 
    public static void main(String[] args) {
        int[][] costs = {
            {1, 3, 5},
            {2, 9, 4},
            {8, 3, 6},
            {4, 7, 2}
        };
        System.out.println(minCostToPaint(costs)); // Output: 8
    }
}

Optimized DP Approach (O(NK) Time Complexity, O(K) Space)

Step-by-Step Explanation

  1. Track Only the Last Row (prevRow)
    • Instead of keeping a full dp[N][K] table, we store only the last row.
  2. Transition Formula
    • Compute minimum values of the previous row.
    • Update the current row based on previous minimum cost values.
  3. Final Result
    • Return the minimum value from the last computed row.

Java Code (Optimized O(NK) Space Solution)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class PaintHousesOptimizedDP {
    public static int minCostToPaint(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
 
        int N = costs.length, K = costs[0].length;
        int[] prevRow = new int[K];
        System.arraycopy(costs[0], 0, prevRow, 0, K); // Copy first row
 
        for (int i = 1; i < N; i++) {
            int[] currRow = new int[K];
 
            for (int c = 0; c < K; c++) {
                int minCost = Integer.MAX_VALUE;
 
                for (int prevC = 0; prevC < K; prevC++) {
                    if (prevC != c) {
                        minCost = Math.min(minCost, prevRow[prevC]);
                    }
                }
                currRow = costs[i] + minCost;
            }
            prevRow = currRow;
        }
 
        int minCost = Integer.MAX_VALUE;
        for (int cost : prevRow) {
            minCost = Math.min(minCost, cost);
        }
        return minCost;
    }
 
    public static void main(String[] args) {
        int[][] costs = {
            {1, 3, 5},
            {2, 9, 4},
            {8, 3, 6},
            {4, 7, 2}
        };
        System.out.println(minCostToPaint(costs)); // Output: 8
    }
}

Final Optimized Approach (O(NK) Time Complexity, O(1) Space)

Step-by-Step Explanation

  1. Track Only Three Variables
    • min1: Smallest cost in the previous row.
    • min1Idx: Index of min1.
    • min2: Second smallest cost.
  2. Use Efficient Update Rule
    • If the color is not min1Idx, use min1, otherwise use min2.

Java Code (Fully Optimized O(NK) Time, O(1) Space)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class PaintHousesOptimal {
    public static int minCostToPaint(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
 
        int N = costs.length, K = costs[0].length;
        int min1 = 0, min1Idx = -1, min2 = 0;
 
        for (int i = 0; i < N; i++) {
            int newMin1 = Integer.MAX_VALUE, newMin1Idx = -1, newMin2 = Integer.MAX_VALUE;
 
            for (int c = 0; c < K; c++) {
                int cost = costs[i] + (c == min1Idx ? min2 : min1);
 
                if (cost < newMin1) {
                    newMin2 = newMin1;
                    newMin1 = cost;
                    newMin1Idx = c;
                } else if (cost < newMin2) {
                    newMin2 = cost;
                }
            }
            min1 = newMin1;
            min1Idx = newMin1Idx;
            min2 = newMin2;
        }
        return min1;
    }
 
    public static void main(String[] args) {
        int[][] costs = {
            {1, 3, 5},
            {2, 9, 4},
            {8, 3, 6},
            {4, 7, 2}
        };
        System.out.println(minCostToPaint(costs)); // Output: 8
    }
}

Final Complexity Comparison

ApproachTime ComplexitySpace Complexity
Brute ForceO(K^N)O(N)
DP TableO(NK^2)O(NK)
Optimized DPO(NK)O(K)
Fully OptimizedO(NK)O(1)

This final O(NK) time, O(1)space approach is the best possible solution. 🚀

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.

Leave a Comment

Advertisement