LeetCode 0265. Paint House II Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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?

Solutions

Solution 1

PythonJavaC++Go

class Solution: def minCostII(self, costs: List[List[int]]) -> int: n, k = len(costs), len(costs[0]) f = costs[0][:] 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)(code-box)

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(); } }(code-box)

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()); } };(code-box)

func minCostII(costs [][]int) 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 } return slices.Min(f) } func cp(arr []int) []int { t := make([]int, len(arr)) copy(t, arr) return t }(code-box)