Skip to content

265. Paint House II 👍

  • Time: $O(nk)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int minCostII(vector<vector<int>>& costs) {
    int prevIndex = -1;  // the previous minimum index
    int prevMin1 = 0;    // the minimum cost so far
    int prevMin2 = 0;    // the second minimum cost so far

    for (const vector<int>& cost : costs) {  // O(n)
      // the painted index that will achieve the minimum cost after painting the
      // current house
      int index = -1;
      // the minimum cost after painting the current house
      int min1 = INT_MAX;
      // the second minimum cost after painting the current house
      int min2 = INT_MAX;
      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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public int minCostII(int[][] costs) {
    int prevIndex = -1; // the previous minimum index
    int prevMin1 = 0;   // the minimum cost so far
    int prevMin2 = 0;   // the second minimum cost so far

    for (int[] cost : costs) { // O(n)
      // the painted index that will achieve the minimum cost after painting the
      // current house
      int index = -1;
      // the minimum cost after painting the current house
      int min1 = Integer.MAX_VALUE;
      // the second minimum cost after painting the current house
      int min2 = Integer.MAX_VALUE;
      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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def minCostII(self, costs: List[List[int]]) -> int:
    prevIndex = -1  # the previous minimum index
    prevMin1 = 0  # the minimum cost so far
    prevMin2 = 0  # the second minimum cost so far

    for cost in costs:  # O(n)
      # the painted index that will achieve the minimum cost after painting the
      # current house
      index = -1
      # the minimum cost after painting the current house
      min1 = math.inf
      # the second minimum cost after painting the current house
      min2 = math.inf
      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