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

• 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])``````

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