Question

Formatted question description: https://leetcode.ca/all/265.html

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 an n x k cost matrix costs.

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...

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[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.

Example 2:

Input: costs = [[1,3],[2,4]]
Output: 5

Constraints:

costs.length == n
costs[i].length == k
1 <= n <= 100
2 <= k <= 20
1 <= costs[i][j] <= 20

Follow up: Could you solve it in O(nk) runtime?

Algorithm

Implementation with Three For Loops

This approach employs dynamic programming. A 2D array dp is created with n rows and k columns, where dp[i][j] denotes the minimum cumulative cost to paint houses from 0 to i, with house i being painted with color j.

For the initial row, corresponding to the first house, dp[0][j] is set to costs[0][j]. To calculate dp[i][j] for i > 0, the algorithm first identifies the minimum value in the previous row dp[i - 1], excluding dp[i - 1][j], due to the constraint that no two adjacent houses can share the same color. This minimum is denoted as min. Then, it sets dp[i][j] to min + costs[i][j].

The final step involves finding and returning the smallest value in the last row dp[n - 1], which represents the lowest cost to paint all houses.

Enhanced Method: Tracking Minimum and Second Minimum Costs

Instead of traversing all colors to find the minimum costs for different colors, this enhanced method utilizes two variables, min1 and min2, to keep track of the smallest and second smallest costs encountered so far.

If the color of the current house matches the color associated with min1, the algorithm uses the cost associated with min2 for calculations.
Conversely, if the color does not match min1, it uses the cost associated with min1.

This technique effectively simplifies the process of identifying the least and next-to-least expensive options, incorporating the strategy for finding the second smallest value directly into the solution.

Code

public class Paint_House_II {

    // O(n * k^2)
    class Solution_N3 {
        public int minCostII(int[][] costs) {
            if (costs.length == 0 || costs[0].length == 0)
                return 0;
            int length = costs.length, colors = costs[0].length;
            int[][] dp = new int[length][colors];
            for (int i = 0; i < colors; i++)
                dp[0][i] = costs[0][i];
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < colors; j++) {
                    int curCost = costs[i][j];
                    int prevMinSum = Integer.MAX_VALUE;
                    for (int k = 0; k < colors; k++) {
                        if (j == k)
                            continue;
                        prevMinSum = Math.min(prevMinSum, dp[i - 1][k]);
                    }
                    dp[i][j] = prevMinSum + curCost;
                }
            }
            int minCost = Integer.MAX_VALUE;
            for (int i = 0; i < colors; i++)
                minCost = Math.min(minCost, dp[length - 1][i]);
            return minCost;
        }
    }

    public class Solution {
        public int minCostII(int[][] costs) {

            if(costs != null && costs.length == 0) {
                return 0;
            }

            int prevMin = 0, prevSecondMin = 0, prevIdx = -1;

            for(int i = 0; i < costs.length; i++){

                int currMin = Integer.MAX_VALUE;
                int currSecondMin = Integer.MAX_VALUE;
                int currIdx = -1;

                for(int j = 0; j < costs[0].length; j++){ // go over all colors

                    costs[i][j] = costs[i][j] + (prevIdx == j ? prevSecondMin : prevMin);

                    if(costs[i][j] < currMin){
                        currSecondMin = currMin;
                        currMin = costs[i][j];
                        currIdx = j;
                    } else if (costs[i][j] < currSecondMin){
                        currSecondMin = costs[i][j];
                    }
                }
                prevMin = currMin;
                prevSecondMin = currSecondMin;
                prevIdx = currIdx;
            }
            return prevMin;
        }
    }

    public class Solution_DP_O_nk {
        public int minCostII(int[][] costs) {

            if(costs != null && costs.length == 0) {
                return 0;
            }

            int[][] dp = costs;
            int min1 = -1, min2 = -1;

            for (int i = 0; i < dp.length; i++) {
                int last1 = min1;
                int last2 = min2;
                min1 = -1; min2 = -1;
                for (int j = 0; j < dp[i].length; j++) {
                    if (j != last1) {
                        dp[i][j] += last1 < 0 ? 0 : dp[i - 1][last1];
                    } else {
                        dp[i][j] += last2 < 0 ? 0 : dp[i - 1][last2];
                    }

                    if (min1 < 0 || dp[i][j] < dp[i][min1]) {
                        min2 = min1;
                        min1 = j;
                    } else if (min2 < 0 || dp[i][j] < dp[i][min2]) {
                        min2 = j;
                    }
                }
            }

            return dp[dp.length - 1][min1];
        }
    }
}

############

class Solution {
    public int minCostII(int[][] costs) {
        int n = costs.length, k = costs[0].length;
        int[] f = costs[0].clone();
        for (int i = 1; i < n; ++i) {
            int[] g = costs[i].clone();
            for (int j = 0; j < k; ++j) {
                int t = Integer.MAX_VALUE;
                for (int h = 0; h < k; ++h) {
                    if (h != j) {
                        t = Math.min(t, f[h]);
                    }
                }
                g[j] += t;
            }
            f = g;
        }
        return Arrays.stream(f).min().getAsInt();
    }
}

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size(), k = costs[0].size();
        vector<int> f = costs[0];
        for (int i = 1; i < n; ++i) {
            vector<int> g = costs[i];
            for (int j = 0; j < k; ++j) {
                int t = INT_MAX;
                for (int h = 0; h < k; ++h) {
                    if (h != j) {
                        t = min(t, f[h]);
                    }
                }
                g[j] += t;
            }
            f = move(g);
        }
        return *min_element(f.begin(), f.end());
    }
};

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n, k = len(costs), len(costs[0])
        f = costs[0][:] # 1st house
        for i in range(1, n):
            g = costs[i][:]
            for j in range(k):
                t = min(f[h] for h in range(k) if h != j)
                g[j] += t
            f = g
        return min(f)

###############

class Solution: # min1, min2
    def minCostII(self, costs):
        if not costs or len(costs) == 0:
            return 0

        prev_min = 0
        prev_second_min = 0
        prev_idx = -1

        for i in range(len(costs)):
            curr_min = float('inf')
            curr_second_min = float('inf')
            curr_idx = -1

            for j in range(len(costs[0])):
                costs[i][j] = costs[i][j] + (prev_idx == j) * prev_second_min + (prev_idx != j) * prev_min

                if costs[i][j] < curr_min:
                    curr_second_min = curr_min
                    curr_min = costs[i][j]
                    curr_idx = j
                elif costs[i][j] < curr_second_min:
                    curr_second_min = costs[i][j]

            prev_min = curr_min
            prev_second_min = curr_second_min
            prev_idx = curr_idx

        return prev_min

############

class Solution(object):
  def minCostII(self, costs):
    """
    :type costs: List[List[int]]
    :rtype: int
    """
    if not costs:
      return 0
    dp = [[0] * len(costs[0]) for _ in range(0, len(costs))]
    dp[0] = costs[0]
    for i in range(1, len(costs)):
      for j in range(0, len(costs[0])):
        dp[i][j] = min(dp[i - 1][:j] + dp[i - 1][j + 1:]) + costs[i][j] # exclude j itself
    return min(dp[-1])

func minCostII(costs [][]int) (ans int) {
	n, k := len(costs), len(costs[0])
	f := cp(costs[0])
	for i := 1; i < n; i++ {
		g := cp(costs[i])
		for j := 0; j < k; j++ {
			t := math.MaxInt32
			for h := 0; h < k; h++ {
				if h != j && t > f[h] {
					t = f[h]
				}
			}
			g[j] += t
		}
		f = g
	}
	ans = f[0]
	for _, v := range f {
		if ans > v {
			ans = v
		}
	}
	return
}

func cp(arr []int) []int {
	t := make([]int, len(arr))
	copy(t, arr)
	return t
}

265 - Paint House II

Question

Algorithm

Implementation with Three For Loops

Enhanced Method: Tracking Minimum and Second Minimum Costs

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Implementation with Three For Loops

Enhanced Method: Tracking Minimum and Second Minimum Costs

Code

All Problems

All Solutions