Python solution O(nk) time and O(1) extra space


  • 0
    class Solution(object):
        def minCostII(self, costs):
            """
            :type costs: List[List[int]]
            :rtype: int
            """
            if not costs:
                return 0
            
            min1, min2 = (-1, 0), (-1, 0)
            nrow, ncol = len(costs), len(costs[0])
            
            for i in range(nrow):
                ti1, tmin1 = min1[0], float('inf')
                ti2, tmin2 = min2[0], float('inf')
                
                for j in range(ncol):
                    t = costs[i][j] + (min1[1] if j != min1[0] or ti1 == -1 else min2[1])
                    if t < tmin1: 
                        tmin2, tmin1 = tmin1, t
                        ti2, ti1 = ti1, j
                    elif t < tmin2:
                        tmin2, ti2 = t, j
    
                min1, min2 = (ti1, tmin1), (ti2, tmin2)
            
            return min1[1]
    

Log in to reply
 

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