Leetcode–Triangle

The Problem:

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

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.

Notes:

  1. The main idea is traversing the list backwards, which means start from bottom of the triangle. For each level up, store the result of min path to reach this node from lower level.
  2. It is a DP problem, but the previous results for one level can be updated in place.

Java Solution

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1)
            return triangle.get(0).get(0);
        int rows = triangle.size();
        int sum[] = new int[triangle.get(rows-1).size()];
        for(int i = 0; i < triangle.get(rows-1).size(); i++ ){
            sum[i] = triangle.get(rows-1).get(i);
        }
        
        for(int i = rows-2; i>= 0; i--){
            for(int j = 0; j <  triangle.get(i).size(); j++ ){
                sum[j] = triangle.get(i).get(j) + Math.min(sum[j], sum[j +1]);
            }
        }
        return sum[0];
    }
}
Advertisements

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