Leetcode

Paint House II

  • Time:O(nk)
  • Space:O(1)

C++

class Solution {
 public:
  int minCostII(vector<vector<int>>& costs) {
    int prevIndex = -1;  // the previous minimum index
    int prevMin1 = 0;    // minimum cost so far
    int prevMin2 = 0;    // 2nd minimum cost so far

    for (const auto& cost : costs) {  // O(n)
      int index = -1;  // the painted index s.t. achieve the minimum cost after
                       // painting current house
      int min1 = INT_MAX;  // the minimum cost after painting current house
      int min2 = INT_MAX;  // the 2nd minimum cost after painting current house
      for (int i = 0; i < cost.size(); ++i) {  // O(k)
        const int theCost = cost[i] + (i == prevIndex ? prevMin2 : prevMin1);
        if (theCost < min1) {
          index = i;
          min2 = min1;
          min1 = theCost;
        } else if (theCost < min2) {  // min1 <= theCost < min2
          min2 = theCost;
        }
      }
      prevIndex = index;
      prevMin1 = min1;
      prevMin2 = min2;
    }

    return prevMin1;
  }
};

JAVA

class Solution {
  public int minCostII(int[][] costs) {
    int prevIndex = -1; // the previous minimum index
    int prevMin1 = 0;   // minimum cost so far
    int prevMin2 = 0;   // 2nd minimum cost so far

    for (int[] cost : costs) { // O(n)
      // the painted index s.t. achieve the minimum cost after painting current house
      int index = -1;
      int min1 = Integer.MAX_VALUE;           // the minimum cost after painting current house
      int min2 = Integer.MAX_VALUE;           // the 2nd minimum cost after painting current house
      for (int i = 0; i < cost.length; ++i) { // O(k)
        final int theCost = cost[i] + (i == prevIndex ? prevMin2 : prevMin1);
        if (theCost < min1) {
          index = i;
          min2 = min1;
          min1 = theCost;
        } else if (theCost < min2) { // min1 <= theCost < min2
          min2 = theCost;
        }
      }
      prevIndex = index;
      prevMin1 = min1;
      prevMin2 = min2;
    }

    return prevMin1;
  }
}

Python

class Solution:
  def minCostII(self, costs: List[List[int]]) -> int:
    prevIndex = -1  # the previous minimum index
    prevMin1 = 0    # minimum cost so far
    prevMin2 = 0    # 2nd minimum cost so far

    for cost in costs:   # O(n)
      index = -1  # the painted index s.t. achieve the minimum cost after painting current house
      min1 = math.inf  # the minimum cost after painting current house
      min2 = math.inf  # the 2nd minimum cost after painting current house
      for i, cst in enumerate(cost):   # O(k)
        theCost = cst + (prevMin2 if i == prevIndex else prevMin1)
        if theCost < min1:
          index = i
          min2 = min1
          min1 = theCost
        elif theCost < min2:   # min1 <= theCost < min2
          min2 = theCost

      prevIndex = index
      prevMin1 = min1
      prevMin2 = min2

    return prevMin1