Minimum Sum Path in a Triangle

22 August 2024

0

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

Examples :

Input : 
   2
  3 7
 8 5 6
6 1 9 3
Output : 11
Explanation : 2 + 3 + 5 + 1 = 11

Input :
   3
  6 4
 5 2 7
9 1 8 6
Output : 10
Explanation : 3 + 4 + 2 + 1 = 10

Naive Approach : Going through the Naive approach by traversing every possible path. But, this is costly. So, use Dynamic Programming here in order to reduce the time complexity.

C++

// C++ program for 
// Recursion implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
 
// Util function to find minimum sum for a path
int helper(vector<vector<int>>& A, int i, int j){
    // Base Case  
    if(i == A.size() ){
      return 0 ;
    }
   
    int mn ;
    // Add current to the minimum  of the next paths 
    mn = A[i][j] + min(helper(A, i+1,j), helper(A,i+1, j+1)) ;
    //return minimum
    return mn ;
}
 
 
int minSumPath(vector<vector<int>>& A) { 
    return helper(A, 0, 0) ;
}
 
/* Driver program to test above functions */
int main()
{
    vector<vector<int> > A{ { 2 },
                            { 3, 9 },
                            { 1, 6, 7 } };
    cout << minSumPath(A);
    return 0;
}

Java

// Java program for
// Recursive implementation of
// Min sum path in a triangle
import java.io.*;
class GFG {
 
  // Util function to find minimum sum for a path
  static int helper(int A[][], int i, int j)
  {
 
    // Base Case  
    if(i == A.length){
      return 0 ;
    }
 
    int mn ;
 
    // Add current to the minimum  of the next paths 
    mn = A[i][j] + Math.min(helper(A, i+1,j), helper(A,i+1, j+1)) ;
 
    //return minimum
    return mn ;
  }
  static int minSumPath(int A[][]) { 
    return helper(A, 0, 0) ;
  }
 
  /* Driver program to test above functions */
  public static void main(String[] args)
  {
    int triangle [][] = { { 2 },
                         { 3, 9 },
                         { 1, 6, 7 }  };
    System.out.print(minSumPath(triangle));
  }
}
 
// This code is contributed by Rohini Chandra

Python3

# Python3 program for
# Recursion implementation of
# Min Sum Path in a Triangle
 
# Util function to find minimum sum for a path
def helper(A, i, j):
    # Base Case
   if(i == len(A)):
      return 0
 
    # Add current to the minimum of the next paths
   mn = A[i][j] + min(helper(A, i + 1, j), helper(A, i + 1, j + 1))
   
    # return minimum
   return mn 
 
def minSumPath(A):
    return helper(A, 0, 0) 
 
# Driver program to test above functions 
A = [ [ 2 ], [ 3, 9 ], [ 1, 6, 7 ] ]
print(minSumPath(A))
 
# This code is contributed by shinjanpatra.

C#

// C# program for Recursion implementation of Min Sum Path in a Triangle
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
 
  // Util function to find minimum sum for a path
  static int helper(ref List<List<int>> A, int i, int j)
  {
     
    // Base Case
    if (i == A.Count ) {
      return 0 ;
    }
 
    int mn ;
     
    // Add current to the minimum  of the next paths
    mn = A[i][j] + Math.Min(helper(ref A, i + 1, j), 
                            helper(ref A, i + 1, j + 1)) ;
     
    //return minimum
    return mn ;
  }
 
  static int minSumPath(ref List<List<int>> A) {
    return helper(ref A, 0, 0) ;
  }
 
  // Driver Code
  public static void Main() {
    List<List<int>> A = new List<List<int>>();
    A.Add(new List<int> {2});
    A.Add(new List<int> {3, 9});
    A.Add(new List<int> {1, 6, 7});
    Console.WriteLine(minSumPath(ref A));
  }
}
 
// This code is contributed by ajaymakvana

Javascript

<script>
 
// JavaScript program for
// Recursion implementation of
// Min Sum Path in a Triangle
 
// Util function to find minimum sum for a path
function helper(A, i, j)
{
 
    // Base Case
    if(i == A.length )
    {
       return 0 ;
    }
 
    let mn ;
     
    // Add current to the minimum of the next paths
    mn = A[i][j] + Math.min(helper(A, i + 1,j), helper(A, i + 1, j + 1)) ;
     
    // return minimum
    return mn ;
}
 
function minSumPath(A) 
{
    return helper(A, 0, 0) ;
}
 
/* Driver program to test above functions */
let A = [ [ 2 ], [ 3, 9 ], [ 1, 6, 7 ] ];
document.write(minSumPath(A));
 
// This code is contributed by shinjanpatra.
</script>

Output

Time Complexity: O(2^N*N) where N = number of rows and M = number of columns

Auxiliary Space: O(N)

There are two ways to reach the solution :

1. Memoization – Starting from the top node, traverse recursively with each node, till the pathsum of that node is calculated. And then store the result in an array. But this will take O(N^2) space to maintain the array.

Implementation of Above Approach:

C++

// C++ program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
 
// Util function to find minimum sum for a path
int helper(vector<vector<int>>& A, int i, int j, vector<vector<int>>& dp){
    // Base Case  
    if(i == A.size() ){
      return 0 ;
    }
   
   // To avoid solving overlapping subproblem
   if(dp[i][j] != -1){
     return dp[i][j] ;
   }
   
 
    // Add current to the minimum  of the next paths 
    // and store it in dp matrix
    return dp[i][j] = A[i][j] + min(helper(A, i+1,j, dp), helper(A,i+1, j+1, dp)) ;
     
     
}
 
 
int minSumPath(vector<vector<int>>& A) { 
    int n = A.size() ;
    // Initializating of dp matrix
    vector<vector<int>> dp(n, vector<int>(n, -1) ) ;
    // calling helper function
    return helper(A, 0, 0, dp) ;
}
 
/* Driver program to test above functions */
int main()
{
    vector<vector<int> > A{ { 2 },
                            { 3, 9 },
                            { 1, 6, 7 } };
    cout << minSumPath(A);
    return 0;
}

Java

// Java program for
// Recursive implementation of
// Min sum path in a triangle
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
  // Function for finding miximum sum
  public static int helper(int A[][], int i, int j, int dp[][])
  {
    if (i == A.length) {
      return 0;
    }
    if (dp[i][j] != -1) return dp[i][j];    
    return dp[i][j] = A[i][j] + Math.min(helper(A, i+1, j, dp), helper(A, i+1, j + 1, dp));
  }
 
  public static int minSumPath(int A[][]) {
    int n = A.length;
 
    // Initializating of dp matrix
    int dp[][] = new int[n][n];
    for(int[] row : dp)
      Arrays.fill(row,-1);
 
    // calling helper function
    return helper(A, 0, 0, dp) ;
  } 
 
  /* Driver program to test above functions */
  public static void main(String[] args)
  {
    int A [][] = { { 2 },
                  { 3, 9 },
                  { 1, 6, 7 } };
    System.out.print(minSumPath(A));
  }
}
 
// This code is contributed by Rohini Chandra

Python3

# Python program for Dynamic
# Programming implementation of
# Min Sum Path in a Triangle
 
# Util function to find minimum sum for a path
def helper(A, i, j, dp):
   
    # Base Case  
    if(i == len(A)):
        return 0
   
    # To avoid solving overlapping subproblem
    if(dp[i][j] != -1):
        return dp[i][j]
   
    # Add current to the minimum  of the next paths 
    # and store it in dp matrix
    dp[i][j] = A[i][j] + min(helper(A, i+1,j, dp), helper(A,i+1, j+1, dp))
    return dp[i][j]
 
def minSumPath(A):
    n = len(A)
     
    # Initializating of dp matrix
    dp = [[-1]*n]*n
 
    # calling helper function
    return helper(A, 0, 0, dp)
 
# Driver program to test above functions 
A = [ [ 2 ],[ 3, 9 ],[ 1, 6, 7 ] ]
print(minSumPath(A))
 
# This code is contributed by shinjanpatra

C#

// C# program for Recursion implementation of Min Sum Path in a Triangle
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
 
  // Util function to find minimum sum for a path
  static int helper(ref List<List<int>> A, int i, int j, int[,] dp)
  {
    //   Base Case
    if (i == A.Count) {
      return 0;
    }
    // To avoid solving overlapping subproblem
    if (dp[i, j] != -1) return dp[i, j];
    // Add current to the minimum  of the next paths and store it in dp matrix
    return dp[i, j] = A[i][j] + Math.Min(helper(ref A, i + 1, j, dp), helper(ref A, i + 1, j + 1, dp));
  }
 
  static int minSumPath(ref List<List<int>> A) {
    int n = A.Count;
 
    // Initializating of dp matrix
    int[ , ] dp = new int [n, n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dp[i, j] = -1;
      }
    }
 
    // calling helper function
    return helper(ref A, 0, 0, dp) ;
  }
 
  // Driver Code
  public static void Main() {
    List<List<int>> A = new List<List<int>>();
    A.Add(new List<int> {2});
    A.Add(new List<int> {3, 9});
    A.Add(new List<int> {1, 6, 7});
    Console.WriteLine(minSumPath(ref A));
  }
}
 
// This code is contributed by ajaymakvana.

Javascript

<script>
 
// JavaScript program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
 
// Util function to find minimum sum for a path
function helper(A, i, j, dp)
{
 
    // Base Case  
    if(i == A.length){
      return 0 ;
    }
   
   // To avoid solving overlapping subproblem
   if(dp[i][j] != -1)
   {
     return dp[i][j] ;
   }
   
    // Add current to the minimum  of the next paths 
    // and store it in dp matrix
    return dp[i][j] = A[i][j] + Math.min(helper(A, i+1,j, dp), helper(A,i+1, j+1, dp)) ;
     
     
}
 
 
function minSumPath(A) { 
    let n = A.length ;
     
    // Initializating of dp matrix
    let dp = new Array(n);
    for(let i=0;i<n;i++){
        dp[i] = new Array(n).fill(-1);
    }
    // calling helper function
    return helper(A, 0, 0, dp) ;
}
 
/* Driver program to test above functions */
 
let A = [ [ 2 ],[ 3, 9 ],[ 1, 6, 7 ] ];
document.write(minSumPath(A));
 
// This code is contributed by shinjanpatra
 
</script>

Output

Time Complexity: O(N*M) where N = number of rows and M = number of columns

Auxiliary Space: O(N²)

2. Bottom up – Start from the nodes on the bottom row; the min pathsum for these nodes are the values of the nodes themselves. And after that, minimum pathsum at the ith node of kth row would be the minimum of the pathsum of its two children + the node’s value, i.e.:

memo[k][i] = min( memo[k+1][i], memo[k+1][i+1]) + A[k][i];

OR
Simply set memo as a 1D array, and update it
this will be space efficient also :

For the row k :

memo[i] = min( memo[i], memo[i+1]) + A[k][i];

Below is the implementation of above dynamic programming approach :

C++

// C++ program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
 
// Util function to find minimum sum for a path
int minSumPath(vector<vector<int> >& A)
{
    // For storing the result in a 1-D array,
    // and simultaneously updating the result.
    int memo[A.size()];
    int n = A.size() - 1;
 
    // For the bottom row
    for (int i = 0; i < A[n].size(); i++) 
        memo[i] = A[n][i];    
 
    // Calculation of the remaining rows,
    // in bottom up manner.
    for (int i = A.size() - 2; i >= 0; i--) 
        for (int j = 0; j < A[i].size(); j++) 
            memo[j] = A[i][j] + min(memo[j],
                                    memo[j + 1]);
 
    // return the top element
    return memo[0];
}
 
/* Driver program to test above functions */
int main()
{
    vector<vector<int> > A{ { 2 },
                            { 3, 9 },
                            { 1, 6, 7 } };
    cout << minSumPath(A);
    return 0;
}

Java

// Java program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
import java.io.*;
import java.util.*;
 
class GFG
{
    static int A[][] = {{2}, 
                        {3, 9}, 
                        {1, 6, 7}};
                         
    // Util function to find 
    // minimum sum for a path
    static int minSumPath()
    {
        // For storing the result
        // in a 1-D array, and 
        // simultaneously updating 
        // the result.
        int []memo = new int[A.length];
        int n = A.length - 1;
     
        // For the bottom row
        for (int i = 0; 
                 i < A[n].length; i++) 
            memo[i] = A[n][i];
     
        // Calculation of the 
        // remaining rows, in
        // bottom up manner.
        for (int i = A.length - 2; 
                 i >= 0; i--) 
            for (int j = 0; 
                     j < A[i].length; j++) 
                memo[j] = A[i][j] + 
                          (int)Math.min(memo[j], 
                                   memo[j + 1]);
     
        // return the 
        // top element
        return memo[0];
    }
     
    // Driver Code
    public static void main(String args[])
    {
        System.out.print(minSumPath());
    }
}
 
// This code is contributed by 
// Manish Shaw (manishshaw1)

Python3

# Python3 program for Dynamic
# Programming implementation of
# Min Sum Path in a Triangle
 
# Util function to find 
# minimum sum for a path
def minSumPath(A):
     
    # For storing the result in 
    # a 1-D array, and simultaneously 
    # updating the result.
    memo = [None] * len(A)
    n = len(A) - 1
     
    # For the bottom row
    for i in range(len(A[n])): 
        memo[i] = A[n][i] 
 
    # Calculation of the
    # remaining rows,
    # in bottom up manner.
    for i in range(len(A) - 2, -1,-1): 
        for j in range( len(A[i])): 
            memo[j] = A[i][j] + min(memo[j],
                                    memo[j + 1]);
 
    # return the top element
    return memo[0]
 
# Driver Code
A = [[ 2 ],
    [3, 9 ],
    [1, 6, 7 ]]
print(minSumPath(A))
 
# This code is contributed
# by ChitraNayal

C#

// C# program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG {
     
    // Util function to find 
    // minimum sum for a path
    static int minSumPath(ref List<List<int>> A)
    {
         
        // For storing the result in a 1-D array,
        // and simultaneously updating the result.
        int []memo = new int[A.Count];
        int n = A.Count - 1;
     
        // For the bottom row
        for (int i = 0; i < A[n].Count; i++) 
            memo[i] = A[n][i]; 
     
        // Calculation of the remaining rows,
        // in bottom up manner.
        for (int i = A.Count - 2; i >= 0; i--) 
            for (int j = 0; j < A[i + 1].Count - 1; j++) 
                memo[j] = A[i][j] + 
                          (int)Math.Min(memo[j], 
                                   memo[j + 1]);
     
        // return the top element
        return memo[0];
    }
     
    // Driver Code
    public static void Main()
    {
        List<List<int>> A = new List<List<int>>();
        A.Add(new List<int> {2});
        A.Add(new List<int> {3, 9});
        A.Add(new List<int> {1, 6, 7});
        Console.WriteLine(minSumPath(ref A));
    }
}
 
// This code is contributed by 
// Manish Shaw (manishshaw1)

PHP

<?php
// PHP program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
 
// Util function to find
// minimum sum for a path
function minSumPath(&$A)
{
    // For storing the result 
    // in a 1-D array, and
    // simultaneously updating 
    // the result.
    $memo = array();
    for ($i = 0; $i < count($A); $i++) 
        $memo[$i] = 0;
 
    $n = count($A) - 1;
 
    // For the bottom row
    for ($i = 0; 
         $i < count($A[$n]); $i++) 
        $memo[$i] = $A[$n][$i]; 
 
    // Calculation of 
    // the remaining rows,
    // in bottom up manner.
    for ($i = count($A) - 2; $i >= 0; $i--) 
        for ($j = 0; 
             $j < count($A[$i + 1]) - 1; $j++) 
            $memo[$j] = $A[$i][$j] + 
                        min($memo[$j],
                        $memo[$j + 1]);
 
    // return the 
    // top element
    return $memo[0];
}
 
// Driver Code
$A = array(array(2),
           array(3, 9),
           array(1, 6, 7));
echo (minSumPath($A)); 
 
// This code is contributed 
// by Manish Shaw(manishshaw1)
?>

Javascript

<script>
 
// JavaScript program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
let A = [[2], [3, 9], [1, 6, 7]];
                       
// Util function to find 
// minimum sum for a path
function minSumPath()
{
     
    // For storing the result
    // in a 1-D array, and 
    // simultaneously updating 
    // the result.
    let memo = [];
    let n = A.length - 1;
   
    // For the bottom row
    for(let i = 0; i < A[n].length; i++) 
        memo[i] = A[n][i];
   
    // Calculation of the 
    // remaining rows, in
    // bottom up manner.
    for(let i = A.length - 2; i >= 0; i--) 
        for(let j = 0; 
                j < A[i].length; j++) 
            memo[j] = A[i][j] + 
                      Math.min(memo[j], 
                               memo[j + 1]);
   
    // Return the 
    // top element
    return memo[0];
}
  
// Driver code
document.write(minSumPath());
 
// This code is contributed by splevel62
 
</script>

Output

Time Complexity: O(N*M) where N = number of rows and M = number of columns

Auxiliary Space: O(N)

Space Optimization Approach: Instead of using another array we can store results in the same array.

C++

// C++ program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
#include <bits/stdc++.h>
using namespace std;
 
// Util function to find minimum sum for a path
int minSumPath(vector<vector<int> >& A)
{
    int n = A.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int minimum = INT_MAX;
        // the maximum element in each row is equal to row
        // number
        for (int j = 0; j <= i; j++) {
            if (i == 0 && j == 0) {
                // if both zero means first element
                minimum = min(minimum, A[i][j]);
                continue;
            }
            // if j==i means the last element so we will not
            // calculate up of the last element
            if (j == i) {
                A[i][j] = A[i][j] + A[i - 1][j - 1];
                minimum = min(minimum, A[i][j]);
                continue;
            }
            // The value at i,j will be calculated using
            // [i-1][j-1] or either [i-1][j] either the
            // element just above or the left of the upper
            // row
            int up = A[i][j], down = A[i][j];
            if (j > 0) {
                up += A[i - 1][j - 1];
            }
            else {
                up = INT_MAX;
            }
            down += A[i - 1][j];
            A[i][j] = min(up, down);
            // This minimum is to keep track of the minimum
            // from each row so that we don't have to
            // calculate it separately
            minimum = min(minimum, A[i][j]);
        }
        ans = minimum;
    }
 
    return ans;
}
 
/* Driver program to test above functions */
int main()
{
    vector<vector<int> > A{ { 2 }, { 3, 9 }, { 1, 6, 7 } };
    cout << minSumPath(A);
    return 0;
}

Java

// Java program for Dynamic
// Programming implementation of
// Min Sum Path in a Triangle
import java.io.*;
import java.util.*;
 
class GFG {
    static int A[][] = { { 2 }, { 3, 9 }, { 1, 6, 7 } };
 
    // Util function to find
    // minimum sum for a path
    static int minSumPath()
    {
 
        int n = A.length;
 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int minimum = Integer.MAX_VALUE;
            // the maximum element in each row is equal to
            // row number
            for (int j = 0; j <= i; j++) {
                if (i == 0 && j == 0) {
                    // if both zero means first element
                    minimum = Math.min(minimum, A[i][j]);
                    continue;
                }
                // if j==i means the last element so we will
                // not calculate up of the last element
                if (j == i) {
                    A[i][j] = A[i][j] + A[i - 1][j - 1];
                    minimum = Math.min(minimum, A[i][j]);
                    continue;
                }
                // The value at i,j will be calculated using
                // [i-1][j-1] or either [i-1][j] either the
                // element just above or the left in the
                // upper row
                int up = A[i][j], down = A[i][j];
                if (j > 0) {
                    up += A[i - 1][j - 1];
                }
                else {
                    up = Integer.MAX_VALUE;
                }
                down += A[i - 1][j];
                A[i][j] = Math.min(up, down);
                // This minimum is to keep track of the
                // minimum
                // from each row so that we don't have to
                // calculate it separately
                minimum = Math.min(minimum, A[i][j]);
            }
            ans = minimum;
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        System.out.print(minSumPath());
    }
}
 
// This code is contributed by
// Manish Shaw (manishshaw1)

Python3

# Python program for Dynamic
# Programming implementation of
# Min Sum Path in a Triangle
 
# Util function to find minimum sum for a path
def minSumPath(A):
    n = len(A)
    ans = 0
    for i in range(n):
        minimum = float("inf")
         
        # the maximum element in each row is equal to row
        # number
        for j in range(i+1):
            if i == 0 and j == 0:
               
                # if both zero means first element
                minimum = min(minimum, A[i][j])
                continue
                 
        # if j==i means the last element so we will not
        # calculate up of the last element
            if j == i:
                A[i][j] = A[i][j]+A[i-1][j-1]
                minimum = min(minimum, A[i][j])
                continue
 
            # The value at i,j will be calculated using
            # [i-1][j-1] or either [i-1][j] either the
            # element just above or the left of the upper
            # row
            up = A[i][j]
            down = A[i][j]
            if j > 0:
                up += A[i-1][j-1]
            else:
                up = float("inf")
            down += A[i-1][j]
 
            A[i][j] = min(up, down)
             
            #  This minimum is to keep track of the minimum
            # from each row so that we don't have to
            # calculate it separately
            minimum = min(minimum, A[i][j])
        ans = minimum
    return ans
 
#  Driver program to test above functions
A = [[2], [3, 9], [1, 6, 7]]
print(minSumPath(A))
 
# This Code is Contributed By Vivek Maddeshiya

C#

// C# program for Dynamic Programming 
// implementation of Min Sum Path in a Triangle
using System;
using System.Collections.Generic;
using System.Linq;
 
public class HelloWorld
{
 
    static List<List<int>> A = new List<List<int>>();
 
 
    // Util function to find minimum sum for a path
    public static int minSumPath()
    {
 
        int n = A.Count;
 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int minimum = Int32.MaxValue;
           
            // the maximum element in each row is equal to row number
            for (int j = 0; j <= i; j++)
            {
                if (i == 0 && j == 0)
                {
                   
                    // if both zero means first element
                    minimum = Math.Min(minimum, A[i][j]);
                    continue;
                }
                // if j==i means the last element so 
              // we will not calculate up of the last element
                if (j == i) {
                    A[i][j] = A[i][j] + A[i - 1][j - 1];
                    minimum = Math.Min(minimum, A[i][j]);
                    continue;
                }
               
                // The value at i,j will be calculated 
              // using [i-1][j-1] or either [i-1][j] 
              // either the element just above or the left in the upper row
                int up = A[i][j], down = A[i][j];
                if (j > 0) {
                    up += A[i - 1][j - 1];
                }
                else {
                    up = Int32.MaxValue;
                }
                down += A[i - 1][j];
                A[i][j] = Math.Min(up, down);
               
                // This minimum is to keep track of 
              // the minimum from each row so that
              // we don't have to calculate it spublic eparately
                minimum = Math.Min(minimum, A[i][j]);
            }
            ans = minimum;
        }
 
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        A.Add(new List<int> {2});
        A.Add(new List<int> {3, 9});
        A.Add(new List<int> {1, 6, 7});
        Console.Write(minSumPath());
    }
}
 
// This code is contributed by ajaymakvana

Javascript

<script>
    // Javascript program for Dynamic
    // Programming implementation of
    // Min Sum Path in a Triangle
     
    // Util function to find minimum sum for a path
    function minSumPath(A)
    {
        let n = A.length;
        let ans = 0;
        for (let i = 0; i < n; i++) {
            let minimum = Number.MAX_SAFE_INTEGER;
            // the maximum element in each row is equal to row
            // number
            for (let j = 0; j <= i; j++) {
                if (i == 0 && j == 0) {
                    // if both zero means first element
                    minimum = Math.min(minimum, A[i][j]);
                    continue;
                }
                // if j==i means the last element so we will not
                // calculate up of the last element
                if (j == i) {
                    A[i][j] = A[i][j] + A[i - 1][j - 1];
                    minimum = Math.min(minimum, A[i][j]);
                    continue;
                }
                // The value at i,j will be calculated using
                // [i-1][j-1] or either [i-1][j] either the
                // element just above or the left of the upper
                // row
                let up = A[i][j], down = A[i][j];
                if (j > 0) {
                    up += A[i - 1][j - 1];
                }
                else {
                    up = Number.MAX_SAFE_INTEGER;
                }
                down += A[i - 1][j];
                A[i][j] = Math.min(up, down);
                // This minimum is to keep track of the minimum
                // from each row so that we don't have to
                // calculate it separately
                minimum = Math.min(minimum, A[i][j]);
            }
            ans = minimum;
        }
     
        return ans;
    }
     
    /* Driver program to test above functions */
     
        let A=[ [ 2 ], [ 3, 9 ], [ 1, 6, 7] ];
        document.write(minSumPath(A));
    // This Code is Contributed By Aman Kumar
</script>

Output:

Time Complexity: O(N*M) where N = number of rows and M = number of columns

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Minimum Sum Path in a Triangle

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

LEAVE A REPLY Cancel reply

Most Popular

Recent Comments

EDITOR PICKS

POPULAR POSTS

POPULAR CATEGORY

ABOUT US

FOLLOW US