CODEWITHSUNDEEP
javascriptalgorithmdynamic-programming
Happy Epicurean
Happy Epicurean

Reputation: 101

LeetCode 120: Triangle - Minimum path sum

I'm doing this problem on leetcode:

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

My logic is to find the minimum number in each array and add that to the sum.

This is my code in javascript:

var minimumTotal = function(triangle) {
    let sum = 0;
    for (let i = 0; i < triangle.length; i++) {
        sum += Math.min.apply(null, triangle[i])
    }
    return sum;
};

But it doesn't work for this test case: [[-1],[2,3],[1,-1,-3]].

The expected output is -1. I'm confused how it should equal -1, because -1 + 2 = 1 and none of the numbers in third array equal -1 when summed with 1.

I looked at the discussion answers and they all used some sort of dynamic programming solution.

What am I doing wrong?

Upvotes: 0

Views: 1796

Answers (5)

Priyanka Bhargav
Priyanka Bhargav

Reputation: 1

/*

*/

import java.util.List;

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

Upvotes: -2

Scott Sauyet
Scott Sauyet

Reputation: 50797

As this was brought back up, it's worth pointing out that the dynamic programming technique discussed in answers and comments can be done very simply with a reduceRight:

const minSum = (triangle) => 
  triangle .reduceRight ((ms, ns) => ns .map (
    (n, i) => n + (i > ms.length ? ms[i] : Math .min (ms [i], ms [i + 1])) 
  )) [0]


console .log (minSum ([[-1], [2, 3], [1, -1, -3]]))            //=> -1
console .log (minSum ([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])) //=> 11
console .log (minSum ([[-10]]))                                //=> -10

At each step we calculate the minimum paths through all the elements in a row. ms is the minimum paths through the row below (and on the initial pass will just be the bottom row) and for each n in our row ns, if we're at the rightmost element, we just copy the value from the corresponding row below, otherwise we take the minimum of the element right below and the one to its right.

Since this is called a triangle, I think we can assume that the first row has only one element. But if that's not the case, we could simply take the minimum of the results rather than taking the first element in the final value. That is, we could replace triangle .reduceRight ( ... ) [0] with Math .min (... triangle .reduceRight ( ... )).

Upvotes: 0

Yilmaz
Yilmaz

Reputation: 49321

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.

The above statement is part of the question and it helps to create a graph like this.

enter image description here

Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. We start from the bottom and determine which minimum value we take and then we are going to be using that minimum value above. That is why we use dynamic programming here. Now each row gets 1 size bigger, so you can imagine under the last row, we have 4 0's.

enter image description here

that is why in dynamic programming we always create an array whose size is always 1 greater than the original array. We fill the array with default values. I will be explaining in python but later on I will challenge myself to write in javascript. first, initialize the dp array

     dp=[0]*(len(triangle)+1) #[[0],[0],[0],[0]]

Now, we are starting from the level=[1,-1,3]. For this level, since the bottom is full of 0's, our dp array will be

 dp=[1,-1,-3,0]

now we are moving above level, level=[2,3], but we are using the data from the bottom. (That is why we are using dynamic programming). From 2, its index is 0, so I ask myself what is the minimum between 0'th and 1'st value of the dp array. Whichever is minimum we add it to 2? Obviously, -1 is minimum, 2+(-1)=1 and dp gets updated.

dp=[1, -1, -3, 0]

We do the same for 3. its index is 1, and we ask what is the min(-1,3), because 3 is pointing to -1 and 3 and then we add -1 to 3 which is 2. new dp

dp=[1,0,-3,0]

Now we are at the root level. -1 and its index is 0. We ask what is min value of index 0'th and index 1'st of the dp array. min(1,0)=0 and we add it to -1. dp gets updated

dp=[-1,0,3,0]

and finally, we return dp[0]=0

Here is the code in python:

from typing import List

class Solution:
    def min_total(self,triangle:List[List[int]])->int:
        # dp[] is the bottom row
        dp=[0]*(len(triangle)+1)
        // triangle[::-1] says start from the last element of triangle
        for row in triangle[::-1]:
            for i,n in enumerate(row):
                dp[i]=n+min(dp[i],dp[i+1])
        return dp[0]

Here is javascript code:

function minPath(triangle) {
  let dp = new Array(triangle.length + 1).fill(0);
  for (let row = triangle.length - 1; row >= 0; row--) {
    for (let i = 0; i <= triangle[row].length - 1; i++) {
      dp[i] = triangle[row][i] + Math.min(dp[i], dp[i + 1]);
    }
  }
  console.log(dp);
  return dp[0];
}
const triangle = [[-1], [2, 3], [1, -1, -3]];

console.log(minPath(triangle));

Upvotes: 0

Emma
Emma

Reputation: 27723

What you are doing does not seem to follow the desired data structure of the problem. You are generating an int, while the desired output should be an array.

The correct answers are already posted in the discussion board:

This solution is an accepted one (just tested it):

JavaScript

var minimumTotal = function(triangle) {
    for (let row = triangle.length - 2; row > -1; row--)
        for (let col = 0; col < triangle[row].length; col++)
            triangle[row][col] += Math.min(triangle[-~row][col], triangle[-~row][-~col])
    return triangle[0][0]
}

-~row is the same as row + 1 (bitwise version).

Reference

Explains it here

If you might be interested in Python and Java, these are "accepted" solutions:

Python

class Solution:
    def minimumTotal(self, triangle):
        if not triangle:
            return

        dp = triangle[-1]
        for row in range(len(triangle) - 2, -1, -1):
            for col in range(len(triangle[row])):
                dp[col] = min(dp[col], dp[-~col]) + triangle[row][col]

        return dp[0]

Java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[-~triangle.size()];

        for (int row = triangle.size() - 1; row > -1; row--)
            for (int col = 0; col < triangle.get(row).size(); col++)
                dp[col] = Math.min(dp[col], dp[-~col]) + triangle.get(row).get(col);

        return dp[0];
    }
}

Upvotes: 0

Green-Avocado
Green-Avocado

Reputation: 891

There is a path where the output should be -1.

[
      [ -1 ],
     [ 2, 3 ],
   [ 1, -1, -3 ],
]

-1 + 3 - 3 = -1

The problem is that you only have 2 possible branches at each fork, whereas it appears you're taking the lowest number from the entire row.

Under the rules of the challenge, you shouldn't be able to go from 2 in the second row to -3 in the third row, which would be the most efficient path under your approach.

Upvotes: 0

Related Questions