coderz.py

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)

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)

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)

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)

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

Approach	Time Complexity	Space Complexity
Brute Force	O(K^N)	O(N)
DP Table	O(NK^2)	O(NK)
Optimized DP	O(NK)	O(K)
Fully Optimized	O(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.