• 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
``````