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).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

It is a good practice to approach this problem using dynamic programming technique. However, at first the array looks like a tree from its form, where quickly people think to traverse the numbers using DFS. If we look carefully, every node here always shares a child which is an “overlapping subproblems”. For example from the above example, in the 2nd row: 3 has 6 and 5 as children; 4 has 5 and 7 as children. Here, 5 is both child for 3 and 4. Going down to the bottom we will find more shared children. Clearly this is a dynamic programming problem.

This can be solved using both top-down or bottom-up techniques. I would pick bottom-up as this is pretty straight forward. We will go from the second last row. Path sum of a node will be the minimum value of its two children plus its own value. From the above example, in case of row 3 (2nd last row), path sum of 6 will be ‘min(4,1) + 6’. By generalizing this, we will get the bottom-up approach as below with space complexity O(1) and time complexity O(n^2):

def min_sum(triangle):
  if not triangle:
    return None
  for i in range(len(triangle)-2, -1, -1):
    for j in range(len(triangle[0])):
      triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
  return triangle[0][0]

A slightly different bottom-up approach if we don’t want to change the original input due to thread safe issue or whatever reason. This is going to be O(n) space complexity. Note that when we compute a row, rows after this would be useless for the result, thus we can do this by using 1D array and iteratively update itself.

def min_sum(triangle):
  if not triangle:
    return None
  res = triangle[-1]
  for i in range(len(triangle)-2, -1, -1):
    for j in range(len(triangle[0])):
      res[j] = min(res[j], res[j+1]) + triangle[i][j]
  return res[0]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s