Paint house ii

Array Dynamic Programming

57.0% acceptance

Mar 31, 2026

1346

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost_ii(costs: Vec<Vec<i32>>) -> i32 {
    let n = costs.len();
    let k = costs[0].len();
    // Track min1 value, min1 index, min2 value
    let mut min1_val = 0;
    let mut min1_idx: i32 = -1;
    let mut min2_val = 0;
    
    for i in 0..n {
      let mut new_min1_val = i32::MAX;
      let mut new_min1_idx: i32 = -1;
      let mut new_min2_val = i32::MAX;
      
      for j in 0..k {
        let cost = costs[i][j] + if j as i32 == min1_idx { min2_val } else { min1_val };
        if cost < new_min1_val {
          new_min2_val = new_min1_val;
          new_min1_val = cost;
          new_min1_idx = j as i32;
        } else if cost < new_min2_val {
          new_min2_val = cost;
        }
      }
      min1_val = new_min1_val;
      min1_idx = new_min1_idx;
      min2_val = new_min2_val;
    }
    min1_val
  }
}