Paint House

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.

For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]

Output: 10

Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.

Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[7,6,2]]

Output: 2

Constraints:

costs.length == n

costs[i].length == 3

1 <= n <= 100

1 <= costs[i][j] <= 20

Approach 2: Brute force with a Recursive Tree

Like the first approach, this approach still isn't good enough.

However, it bridges the gap between approach 1 and approach 3, with approach 3 further building on it.

So make sure you understand it well.

When we have permutations, we can think of them as forming a big tree of all the options.

Drawing out the tree (or part of it) can give useful insights and reveal other possible algorithms.

We'll continue using the sample example that we did above:

    class Solution {
        private int[][] costs;

        public int minCost(int[][] costs) {
            if (costs.length == 0) {
                return 0;    
            }
            this.costs = costs;    
            return Math.min(paintCost(0, 0), Math.min(paintCost(0, 1), paintCost(0, 2)));
        }
    
        private int paintCost(int n, int color) {
            int totalCost = costs[n][color];
            if (n == costs.length - 1) {
            } else if (color == 0) { // Red
                totalCost += Math.min(paintCost(n + 1, 1), paintCost(n + 1, 2));
            } else if (color == 1) { // Green
                totalCost += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 2));
            } else { // Blue
                totalCost += Math.min(paintCost(n + 1, 0), paintCost(n + 1, 1));
            }        
            return totalCost;    
        }    
    }

Complexity Analysis

Time complexity : O(2^n).

While this approach is an improvement on the previous approach, it still requires exponential time.

Think about the number of leaf nodes. Each permutation has its own leaf node.

The number of internal nodes is the same as the number of leaf nodes too.

Remember how there are 2*n different permutations? Each effectively adds 2 nodes to the tree,

so dropping the constant of 2 gives us O(2^n).

This is better than the previous approach, which had an additional factor of n, giving O(n⋅2n).

That extra factor of n has disappeared here because the permutations are now "sharing" their similar parts, unlike before.

The idea of "sharing" similar parts can be taken much further for this particular problem, as we will see with the remaining approaches that knock the time complexity all the way down to O(n).

Space complexity : O(n)

This algorithm might initially appear to be O(1), because we are not allocating any new data structures.

However, we need to take into account space usage on the run-time stack.

The run-time stack was shown in the animation. Whenever we are processing the last house (house number n - 1), there are n stack frames on the stack.

This space usages counts for complexity analysis (it's memory usage, like any other memory usage) and so the space complexity is O(n).