DP with a trick to quickly turn space complexity from O(n^2) to O(n)


  • 0

    This can be solved using DP as others have posted. But I'll share a trick that I learned from somewhere else to quickly turn a O(n^2) space complexity to O(n). Might be helpful in an interview.

    First, the O(n^2) solution:

    class Solution(object):
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
        
            n = len(triangle)
        
            if n == 0:
                return 0
    
            #### use O(n) space ####
            min_sum = [[0] * n for i in range(n)]        
            min_sum[0][0] = triangle[0][0]
        
            for i in range(1, n):
                min_sum[i][0] = min_sum[(i-1)][0] + triangle[i][0]
                min_sum[i ][i] = min_sum[(i-1)][i-1] + triangle[i][i]
                for j in range(1, i):
                    min_sum[i][j] = min(min_sum[i-1][j], min_sum[i-1][j-1]) + triangle[i][j]
        
            return min(min_sum[n-1])
    

    Now to turn it into O(n) space complexity. We use a two row min_sum matrix, since we only need two rows. Then at every place you access a row of min_sum, simply modulo 2 using the row index. This will take the minimal amount of time in an interview:

    class Solution(object):
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
        
            n = len(triangle)
        
            if n == 0:
                return 0
    
            #### use O(n) space ####
            min_sum = [[0] * n for i in range(2)]        
            min_sum[0][0] = triangle[0][0]
        
            for i in range(1, n):
                min_sum[i % 2][0] = min_sum[(i-1) % 2][0] + triangle[i][0]
                min_sum[i % 2][i] = min_sum[(i-1) % 2][i-1] + triangle[i][i]
                for j in range(1, i):
                    min_sum[i % 2][j] = min(min_sum[(i-1) % 2][j], min_sum[(i-1) % 2][j-1]) + triangle[i][j]
        
            return min(min_sum[(n-1) % 2])

Log in to reply
 

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