# Python O(nk) solution with clear explanation

• class Solution(object):
def minCostII(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if not costs:
return 0
n,k = len(costs),len(costs[0])
preMin,preSec,preIdx = 0,0,-1
for i in range(n):
# initialize curMin, curSec, curIdx
curMin,curSec,curIdx = sys.maxint,sys.maxint,-1
for j in range(k):
# if the color is same as previous minimum costs, add the preSec, otherwise add the preMin
costs[i][j] += preSec if preIdx == j else preMin
# update curMin and curSec
if costs[i][j] < curMin:
curSec = curMin
curMin = costs[i][j]
curIdx = j
elif costs[i][j] < curSec:
curSec = costs[i][j]
# update preMin, preSec, preIdx
preMin,preSec,preIdx = curMin,curSec,curIdx
return preMin

We can use the similar idea in Paint House I. To save space, we can update costs[][] and maintain three variables:

1. preMin: minimum cost of previous house painted
2. preSec: second minimum cost of previous house painted
3. preIdx: the index of preMin

In the current loop, if the color is the same as the preMin, that means we have to choose the preSec instead, otherwise we will have two adjacent house painted in the same color.

As we keep updating preMin and preSec, the last value of preMin is the answer.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.