Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]] Output: -10
Constraints:
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 10^4
Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
The description was taken from https://leetcode.com/problems/triangle/.
#O(N^2) Time, O(N^2) Space
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
dp = triangle.copy() for row in range(1, n):
for col in range(row+1):
if col == 0:
dp[row][col] += dp[row-1][col]
elif col == row:
dp[row][col] += dp[row-1][col-1]
else:
dp[row][col] += min(dp[row-1][col], dp[row-1][col-1])
return min(dp[-1])This problem falls into the category of finding paths, similar problems include Minimum Path Sum, Paint House, Unique Paths, and Minimum Falling Path Sum.
To solve these types of problems, we'll arrive at point B and bring over the information from each point A that we could have traveled therefrom, based on the overall problem we are trying to solve. If the overall problem is trying to find the minimum contiguous path, for the triangle matrix, then we can break the overall problem into subproblems by trying to find the minimum contiguous path to each cell. Each cell will be each individual subproblem.
Each subproblem will fall into three subcategories:
It is a left cell in which case the only contiguous subpath we could have gotten therefrom would be the cell directly above it
It is a right cell in which case the only contiguous subpath we could have gotten there from would be the cell directly to the upper left, based on the problem description.
It is a cell not on any edge in which case the only contiguous subpath we could have gotten therefrom would be the cell directly above it or to the upper left.
With that intuition, all we need to do is divide each cell into one of these three categories through conditional statements and continuously find, then tabulate each path. Once we have done that, the minimum path would be carried to the last row.
Let's start by getting the length and width of the input matrix and saving it so that we don't have to keep rewriting this later.
n = len(triangle)
We'll also want to make a copy of the matrix to build off of.
Technically we could perform this algorithm in place, but it's generally best practice to not do that for concurrency reasons.
dp = triangle.copy()
For each row in the matrix starting from the second, since there is no path above the first row, we will go through each column and categorize each subproblem based on the aforementioned explanation.
One thing to note here is the number of columns we are iteration within each row will be directly correlated with the row size since this is supposed to be shaped like a pyramid; If we are at the first row then we have one column, if we are at the second then we have two columns. We'll need to add one to this calculation since arrays begin their indices at zero.
for row in range(1, n):
for col in range(row+1):
If the current column is the first, we'll increment the current cell within our dp cache by the top value.
if col == 0:
dp[row][col] += dp[row-1][col]
If the current cell is the last, we'll increment the current cell within our dp cache by the top-left value.
elif col == row:
dp[row][col] += dp[row-1][col-1]
Otherwise, we'll increment the current cell within our dp cache by the minimum value between the top and the top-left cells.
else:
dp[row][col] += min(dp[row-1][col], dp[row-1][col-1])
Once we have tabulated each path, we will find the minimum one in the last row of our dp cache.
return min(dp[-1])
Since we are only utilizing the previous row for each subproblem, each row therebefore will be a waste of space.
We can drop this space complexity down to linear by only having two rows at a time.
To do this, we will initialize the last row as the first row in the matrix. Then, we will initialize an empty row before we begin our traversal of each row. Once we are done building the new row at the end of each row traversal, we will set the new row as the last row. This way, we are only saving the last row in memory for each row traversal while we're building each new row.
#O(N^2) Time, O(N) Space
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
last_row = triangle[0]
for row in range(1, n):
new_row = []
for col in range(row+1):
if col == 0:
new_row.append(last_row[0] + triangle[row][col])
elif col == row:
new_row.append(last_row[-1] + triangle[row][col])
else:
new_row.append(min(last_row[col], last_row[col-1]) + triangle[row][col])
last_row = new_row
return min(last_row)