LeetCode Solutions

			

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 vector<int>& 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;
  }
};

			

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;
  }
}

			

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