Paint House II

This page explains Java solution to problem Paint House II using Dynamic Programming algorithm.

Problem Statement

There are a row of n houses, each house can be painted with one of the k colors. 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 a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation:
Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Solution

package com.vc.hard;

class PaintHouseIi {
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0) return 0;

        int n = costs.length;
        for(int row = 1; row < n; row++) {

            //Find two minimum elements from prevRow
            int minFirstIndex = -1;
            int minSecondIndex = -1;
            for(int col = 0; col < costs[0].length; col++) {
                int cost = costs[row - 1][col];
                if(minFirstIndex == -1 || cost < costs[row - 1][minFirstIndex]) {
                    minSecondIndex = minFirstIndex;
                    minFirstIndex = col;
                }
                else if(minSecondIndex == -1 || cost < costs[row - 1][minSecondIndex]) {
                    minSecondIndex = col;
                }
            }

            //Find minium in current column based on minimum on previous column
            for(int col = 0; col < costs[0].length; col++) {
                if(col == minFirstIndex) {
                    costs[row][col] += costs[row - 1][minSecondIndex];
                }
                else {
                    costs[row][col] += costs[row - 1][minFirstIndex];
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for(int col = 0; col < costs[0].length; col++) {
            res = Math.min(res, costs[n - 1][col]);
        }
        return res;
    }
}

Time Complexity

O(N * K) Where
N is total number of houses in an input array
K is total number of colors in an input array

Space Complexity

O(1)