11 Line Python, O(NK)


  • 1

    The basic idea is maintaining the top two smallest results from last house of every color , for the convenience of the deciding the best plan for the current house of every color. The reason for maintaining the smallest two is that if the smallest history is pairing exactly with the same color of the current color, I can only take the second smallest.

    class Solution(object):
        def minCostII(self, costs): 
           # O(NK)
            if not costs:
                return 0
            toptwomin, n, k = [(0, -1), (0, -1)], len(costs), len(costs[0])
            for i in xrange(n):
                tmptopmin = [(0xffffffff, -1), (0xffffffff, -1)]
                for j in xrange(k):
                    tmpmin = (costs[i][j] + min(toptwomin)[0], j) if min(toptwomin)[1] != j else (costs[i][j] + max(toptwomin)[0], j )
                    largerOne = max(tmpmin, tmptopmin[0])
                    tmptopmin[0], tmptopmin[1] = min(tmpmin, tmptopmin[0]), min(largerOne, tmptopmin[1])
                toptwomin[:] = tmptopmin[:]
            return min(toptwomin)[0]
    

Log in to reply
 

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