Python O(nk) solution with clear explanation


  • 0
    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.


Log in to reply
 

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