Leetcode 120. Triangle Solution

 

Leetcode 120. Triangle Solution

Hi everybody,

Today we can discuss a Leetcode question. Question :

120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

We can start to understand the problem.

First, we need to understand this question is a Dynamic Problem question. How?

1- We have a triangle.

2-) We need to traverse this triangle

3-) We can compute the min path through the Triangle.

Second, we need to use an extra space like a 2 Dimensional array store to compute the adjacency number on the row below.

Third, in the base case traverse and general traverse case. The base case will traverse fill the left side of our 2D Array. The general traverse case will fill the inside of our second 2 D Array table.

After we need to sum the left and right sides of the Triangle and we can pass the left and right sides of our 2D Table.

Like :

Original Triangle :

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

Fill the left and right side of Table :

[
[2, 0, 0, 0],
[5, 6, 0, 0],
[11, 0, 13, 0],
[15, 0, 0, 16]]

for left side :
2+3 = 5
2+4 = 6
2+3 + 6= 11
2+3 + 6 + 4= 15

After we need to fill 2D inside cells. We can use the Pascal Triangle Equation in this part. We can get min upper cells and we can sum the current triangle cell.

f(i,j) = min(col[i-1][j-1], col[i-1][j]) + triangle[i][j]

Fill the inside Table :
[
[2, 0, 0, 0],
[5, 6, 0, 0],
[11, 10, 13, 0],
[15, 11, 18, 16]
]

Some examples :
table[2,1] = min(5,6) + 5 = 10
table[3,1] = min(11,10) + 1 = 11

Our Code:

	def minTotal(triangle):
	row_size = len(triangle)
	# set up table with the same size as the triangular triangle
	table = [[0 for cols in range(row_size)] for _ in range(row_size)]
	# set up base cases
	table[0][0] = triangle[0][0]
	# base case
	# we can summaziation left and right side cells values
	# we have just one way for the first 2 row because the first row has just one value,     # the second row has just 2 values.
	for i in range(1, row_size):
	table[i][0] = table[i - 1][0] + triangle[i][0]
	table[i][i] = table[i - 1][i - 1] + triangle[i][i]
	# General traversal cases
	# Our recurrence equation in pascal triangle appoarch:
	# f(i,j) = min(col[i-1][j-1], col[i-1][j]) + triangle[i][j]
	# start from row 2
	for i in range(2, len(table)):
	for j in range(1, i):
	table[i][j] = min(table[i - 1][j - 1], table[i - 1][j]) \
	+ triangle[i][j]
	return min(table[-1])
	triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
	ans = minTotal(triangle)
	print ans

Complexities

T(N) = O(rowNumbers²)

1. row = 1
second row = 2 cells
3. row = 3 cells

1+2+3….+ r = r(r+1)/2 = O(r²)

S(N) = O(rowNumbers²) = We need to store each number that we update in triangle.