Triangle

Why Greedy Approach will not work:

As the question asks for minimum path sum, the first approach that comes to our mind is to take a greedy approach and always form a path by locally choosing the cheaper option. At every cell, we have two choices, to move to the bottom cell or move to the bottom-right cell. Our ultimate aim is to provide a path that provides us the least path sum. Therefore at every cell, we will make the choice to move which costs us less.

We can clearly see the issue with the greedy solution. When we make local choices, we might select a path that ends up costing us much more later on.

Therefore, the only alternative left to us is to generate all possible paths and determine which path has the minimum path sum. To generate all paths, we will use recursion.

Steps to form the recursive solution:

Express the problem in terms of indexes: We are given a triangular matrix with the number of rows equal to N. We can define the function with two parameters i and j, where i and j represent the row and column of the matrix.

Now, our ultimate aim is to reach the last row. We can define f(i,j) such that it gives us the minimum path sum from the cell [i][j] to the last row.

Try out all possible choices at a given index: At every index there are two choices, one to go to the bottom cell(↓) other to the bottom-right cell(↘). To go to the bottom, increase i by 1, and to move towards the bottom-righ, increase both i and j by 1.

Now when we get our answer for the recursive call (f(i+1,j) or f(i+1,j+1)), the current cell value also needs to be added to it as we have to include it too for the current path sum

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(i,j){
    //Base case
    down =  mat[i][j] + f(i+1, j)
    diagonal = mat[i][j] + f(i+1, j+1)
}

Take the minimum of all choices: As question asks to find the minimum path sum of all the possible unique paths, return the minimum of the choices(down and diagonal)

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(i,j){
    //Base case
    down =  mat[i][j] + f(i+1, j)
    diagonal = mat[i][j] + f(i+1, j+1)
    return min(down, diagonal)
}

Base cases:

When i == N-1, that means we have reached the last row, so the minimum path from that cell to the last row will be the value of that cell itself, hence we return mat[i][j].

At every cell, we have two options to move to the bottom cell(↓) or to the bottom-right cell(↘). If we closely observe the triangular grid, at max we can reach the last row from where we return so we will not move out of the index of the grid. Therefore only one base condition is required.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(i,j){
    if(i == N-1)   return mat[i][j]
    //code
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to find the minimum path sum recursively
    int func(int i, int j, vector<vector<int> > &triangle, int n) {
        // If we're at bottom row, return value of current cell
        if (i == n - 1)
            return triangle[i][j];

        // Calculate the sum of two possible paths
        int down = triangle[i][j] + func(i + 1, j, triangle, n);
        int diagonal = triangle[i][j] + func(i + 1, j + 1, triangle, n);

        // Return the minimum of the two paths
        return min(down, diagonal);
   }
public:
    //Function to find out the minimum path sum
    int minTriangleSum(vector<vector<int>>& triangle) {
        // Get the number of rows in the triangle
        int n = triangle.size();
    
        //Return the minimum path sum
        return func(0, 0, triangle, n);
    }
};
int main() {
    vector<vector<int> > triangle{{1},
                                   {2, 3},
                                   {3, 6, 7},
                                   {8, 9, 6, 10}};
    
    //Create an instance of the Solution class
    Solution sol;
    
    // Call the minimumPathSum function and print result
    cout << sol.minTriangleSum(triangle);

    return 0;
}
import java.util.*;

class Solution {
    // Function to find the minimum path sum recursively
    private int func(int i, int j, int[][] triangle, int n) {
        // If we're at bottom row, return value of current cell
        if (i == n - 1)
            return triangle[i][j];

        // Calculate the sum of two possible paths
        int down = triangle[i][j] + func(i + 1, j, triangle, n);
        int diagonal = triangle[i][j] + func(i + 1, j + 1, triangle, n);

        // Return the minimum of the two paths
        return Math.min(down, diagonal);
    }

    // Function to find out the minimum path sum
    public int minTriangleSum(int[][] triangle) {
        // Get the number of rows in the triangle
        int n = triangle.length;

        // Return the minimum path sum
        return func(0, 0, triangle, n);
    }

    public static void main(String[] args) {
        int[][] triangle = {
            {1},
            {2, 3},
            {3, 6, 7},
            {8, 9, 6, 10}
        };

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the minTriangleSum function and print result
        System.out.println("Minimum path sum in triangle: " + sol.minTriangleSum(triangle));
    }
}
class Solution:
    # Function to find the minimum path sum recursively
    def func(self, i, j, triangle, n):
        # If we're at bottom row, return value of current cell
        if i == n - 1:
            return triangle[i][j]

        # Calculate the sum of two possible paths
        down = triangle[i][j] + self.func(i + 1, j, triangle, n)
        diagonal = triangle[i][j] + self.func(i + 1, j + 1, triangle, n)

        # Return the minimum of the two paths
        return min(down, diagonal)

    # Function to find out the minimum path sum
    def minTriangleSum(self, triangle):
        # Get the number of rows in the triangle
        n = len(triangle)

        # Return the minimum path sum
        return self.func(0, 0, triangle, n)

if __name__ == "__main__":
    triangle = [
        [1],
        [2, 3],
        [3, 6, 7],
        [8, 9, 6, 10]
    ]

    # Create an instance of Solution class
    sol = Solution()

    # Call the minTriangleSum function and print result
    print("Minimum path sum in triangle:", sol.minTriangleSum(triangle))
class Solution {
    // Function to find the minimum path sum recursively
    func(i, j, triangle, n) {
        // If we're at bottom row, return value of current cell
        if (i === n - 1)
            return triangle[i][j];

        // Calculate the sum of two possible paths
        let down = triangle[i][j] + this.func(i + 1, j, triangle, n);
        let diagonal = triangle[i][j] + this.func(i + 1, j + 1, triangle, n);

        // Return the minimum of the two paths
        return Math.min(down, diagonal);
    }

    // Function to find out the minimum path sum
    minTriangleSum(triangle) {
        // Get the number of rows in the triangle
        let n = triangle.length;

        // Return the minimum path sum
        return this.func(0, 0, triangle, n);
    }
}

const triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
];

// Create an instance of Solution class
const sol = new Solution();

// Call the minTriangleSum function and print result
console.log("Minimum path sum in triangle:", sol.minTriangleSum(triangle));

Complexity Analysis:

Time Complexity: O(2^N), where N is the number of rows . As, each cell has 2 choices and at max the number of subproblems can be N.

Space Complexity:O(N), The depth of the recursion is proportional to the height of the triangle N. Therefore, the space used by the call stack is O(N).

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

The dp array stores the calculations of subproblems, dp[i][j] represents the minimum path sum to reach last row from (i,j). Initially, fill the array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.

Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to find the minimum path sum using memoization
    int func(int i, int j, vector<vector<int> > &triangle, int n, vector<vector<int> > &dp) {
        /* If the result for this cell is
        already calculated, return it*/
        if(dp[i][j] != -1) return dp[i][j];
        
        // If we're at bottom row, return value of current cell
        if (i == n - 1)
            return triangle[i][j];

        // Calculate the sum of two possible paths
        int down = triangle[i][j] + func(i + 1, j, triangle, n, dp);
        int diagonal = triangle[i][j] + func(i + 1, j + 1, triangle, n, dp);

        // Store the sum in dp and return it
        return dp[i][j] = min(down, diagonal);
   }
public:
    //Function to find out the minimum path sum
    int minTriangleSum(vector<vector<int>>& triangle) {
        // Get the number of rows in the triangle
        int n = triangle.size();
        
        /* Initialize a memoization table
        to store computed results*/
        vector<vector<int> > dp(n, vector<int>(n, -1));
    
        //Return the minimum path sum
        return func(0, 0, triangle, n, dp);
    }
};
int main() {
    vector<vector<int> > triangle{{1},
                                   {2, 3},
                                   {3, 6, 7},
                                   {8, 9, 6, 10}};
    
    //Create an instance of the Solution class
    Solution sol;
    
    // Call the minimumPathSum function and print result
    cout << sol.minTriangleSum(triangle);

    return 0;
}
import java.util.*;

class Solution {
    // Function to find the minimum path sum using memoization
    private int func(int i, int j, int[][] triangle, int n, int[][] dp) {
        /* If the result for this cell is
        already calculated, return it*/
        if (dp[i][j] != -1)
            return dp[i][j];

        // If we're at bottom row, return value of current cell
        if (i == n - 1)
            return triangle[i][j];

        // Calculate the sum of two possible paths
        int down = triangle[i][j] + func(i + 1, j, triangle, n, dp);
        int diagonal = triangle[i][j] + func(i + 1, j + 1, triangle, n, dp);

        // Store the minimum sum in dp and return it
        return dp[i][j] = Math.min(down, diagonal);
    }

    // Function to find out the minimum path sum
    public int minTriangleSum(int[][] triangle) {
        // Get the number of rows in the triangle
        int n = triangle.length;

        // Initialize a memoization table to store computed results
        int[][] dp = new int[n][n];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // Return the minimum path sum
        return func(0, 0, triangle, n, dp);
    }

    public static void main(String[] args) {
        int[][] triangle = {{1},
                            {2, 3},
                            {3, 6, 7},
                            {8, 9, 6, 10}};

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the minTriangleSum function and print result
        System.out.println("Minimum path sum in triangle: " + sol.minTriangleSum(triangle));
    }
}
class Solution:
    # Function to find the minimum path sum using memoization
    def func(self, i, j, triangle, n, dp):
        """ If the result for this cell is
        already calculated, return it"""
        if dp[i][j] != -1:
            return dp[i][j]

        # If we're at bottom row, return value of current cell
        if i == n - 1:
            return triangle[i][j]

        # Calculate the sum of two possible paths
        down = triangle[i][j] + self.func(i + 1, j, triangle, n, dp)
        diagonal = triangle[i][j] + self.func(i + 1, j + 1, triangle, n, dp)

        # Store the minimum sum in dp and return it
        dp[i][j] = min(down, diagonal)
        return dp[i][j]

    # Function to find out the minimum path sum
    def minTriangleSum(self, triangle):
        # Get the number of rows in the triangle
        n = len(triangle)

        """ Initialize a memoization table
        to store computed results"""
        dp = [[-1] * n for _ in range(n)]

        # Return the minimum path sum
        return self.func(0, 0, triangle, n, dp)

triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
]

# Create an instance of Solution class
sol = Solution()

# Call the minTriangleSum function and print result
print("Minimum path sum in triangle:", sol.minTriangleSum(triangle))
class Solution {
    // Function to find the minimum path sum using memoization
    func(i, j, triangle, n, dp) {
        /* If the result for this cell is
        already calculated, return it*/
        if (dp[i][j] !== -1) {
            return dp[i][j];
        }

        // If we're at bottom row, return value of current cell
        if (i === n - 1) {
            return triangle[i][j];
        }

        // Calculate the sum of two possible paths
        let down = triangle[i][j] + this.func(i + 1, j, triangle, n, dp);
        let diagonal = triangle[i][j] + this.func(i + 1, j + 1, triangle, n, dp);

        // Store the minimum sum in dp and return it
        dp[i][j] = Math.min(down, diagonal);
        return dp[i][j];
    }

    // Function to find out the minimum path sum
    minTriangleSum(triangle) {
        // Get the number of rows in the triangle
        let n = triangle.length;

        /* Initialize a memoization table
        to store computed results*/
        let dp = Array.from({ length: n }, () => Array(n).fill(-1));

        // Return the minimum path sum
        return this.func(0, 0, triangle, n, dp);
    }
}

let triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
];

// Create an instance of Solution class
let sol = new Solution();

// Call the minTriangleSum function and print result
console.log("Minimum path sum in triangle:", sol.minTriangleSum(triangle));

Complexity Analysis:

Time Complexity: O(N), where N is the number of rows. As the total number of different subproblems can go upto N.

Space Complexity:O(N) + O(N*N), We are using a recursion stack space of N and an extra DP array of size N*N.

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp[] array of size [n][n]: As there are two changing parameters(i and j) in the recursive solution, and the maximum value they can attain is (n-1) and (n-1), where n is number of rows. So we will require a dp matrix of n*n. The dp array stores the calculations of subproblems, dp[i][j] represents the minimum path sum to reach (0,0) from (i,j).

Setting Base Cases in the Array: In the recursive code, we knew that, when i = n-1, it means we have reached the last row and the minimum path to reach the last row from here is the cell value itself. So fill the last row of the dp matrix to the last row of the triangle matrix, dp[n - 1][j] = triangle[n - 1][j].

Iterative Computation Using Loops: We can use two nested loops to have this traversal. If we see the memoized code, the values required for dp[i][j] are dp[i+1][j] and dp[i+1][j+1]. So the values from the ‘i+1’ row is required only. The last row (i=N-1) is already filled for the base case, so, now move from row ‘N-2’ row and move upwards to find the values correctly.

Choosing the minimum: As the question asks for minimum path sum, so update dp[i][j] as the minimum of (down and diagonal).

Returning the first element: The first element dp[0][0] of the dp array is returned because it holds the optimal solution to the entire problem after the top-down computation has been completed.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to find the minimum path sum using tabulation
    int func(vector<vector<int> > &triangle, int n, vector<vector<int> > &dp) {
        /* Initialize the bottom row of dp 
        with the values from the triangle*/
        for (int j = 0; j < n; j++) {
            dp[n - 1][j] = triangle[n - 1][j];
        }

        // Iterate through the triangle rows in reverse order
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // Calculate the minimum path sum for current cell
                int down = triangle[i][j] + dp[i + 1][j];
                int diagonal = triangle[i][j] + dp[i + 1][j + 1];

                // Store the minimum of the two possible paths in dp
                dp[i][j] = min(down, diagonal);
            }
        }
        // Top-left cell of dp now contains the minimum path sum
        return dp[0][0];
    }
public:
    //Function to find out the minimum path sum
    int minTriangleSum(vector<vector<int>>& triangle) {
        // Get the number of rows in the triangle
        int n = triangle.size();
        
        /* Initialize a memoization table
        to store computed results*/
        vector<vector<int> > dp(n, vector<int>(n, -1));
    
        //Return the minimum path sum
        return func(triangle, n, dp);
    }
};
int main() {
    vector<vector<int> > triangle{{1},
                                   {2, 3},
                                   {3, 6, 7},
                                   {8, 9, 6, 10}};
    
    //Create an instance of the Solution class
    Solution sol;
    
    // Call the minimumPathSum function and print result
    cout << sol.minTriangleSum(triangle);

    return 0;
}
class Solution {
    // Function to find the minimum path sum using tabulation
    private int func(int[][] triangle, int n, int[][] dp) {
        /* Initialize the bottom row of dp 
        with the values from the triangle*/
        for (int j = 0; j < n; j++) {
            dp[n - 1][j] = triangle[n - 1][j];
        }

        // Iterate through the triangle rows in reverse order
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // Calculate the minimum path sum for current cell
                int down = triangle[i][j] + dp[i + 1][j];
                int diagonal = triangle[i][j] + dp[i + 1][j + 1];

                // Store the minimum of the two possible paths in dp
                dp[i][j] = Math.min(down, diagonal);
            }
        }
        // Top-left cell of dp now contains the minimum path sum
        return dp[0][0];
    }

    // Function to find out the minimum path sum
    public int minTriangleSum(int[][] triangle) {
        // Get the number of rows in the triangle
        int n = triangle.length;
        
        /* Initialize a memoization table
        to store computed results*/
        int[][] dp = new int[n][n];
    
        // Return the minimum path sum
        return func(triangle, n, dp);
    }

    public static void main(String[] args) {
        int[][] triangle = {
            {1},
            {2, 3},
            {3, 6, 7},
            {8, 9, 6, 10}
        };
        
        // Create an instance of the Solution class
        Solution sol = new Solution();
        
        // Call the minTriangleSum function and print result
        System.out.println(sol.minTriangleSum(triangle));
    }
}
class Solution:
    # Function to find the minimum path sum using tabulation
    def func(self, triangle, n, dp):
        """ Initialize the bottom row of dp
        with the values from the triangle"""
        for j in range(n):
            dp[n - 1][j] = triangle[n - 1][j]

        # Iterate through the triangle rows in reverse order
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                # Calculate the minimum path sum for current cell
                down = triangle[i][j] + dp[i + 1][j]
                diagonal = triangle[i][j] + dp[i + 1][j + 1]

                # Store the minimum of the two possible paths in dp
                dp[i][j] = min(down, diagonal)

        # Top-left cell of dp now contains the minimum path sum
        return dp[0][0]

    # Function to find out the minimum path sum
    def minTriangleSum(self, triangle):
        # Get the number of rows in the triangle
        n = len(triangle)

        # Initialize a memoization table to store computed results
        dp = [[0] * n for _ in range(n)]

        # Return the minimum path sum
        return self.func(triangle, n, dp)

triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
]

# Create an instance of Solution class
sol = Solution()

# Call the minTriangleSum function and print result
print(sol.minTriangleSum(triangle))
class Solution {
    // Function to find the minimum path sum using tabulation
    func(triangle, n, dp) {
        /* Initialize the bottom row of dp
        with the values from the triangle*/
        for (let j = 0; j < n; j++) {
            dp[n - 1][j] = triangle[n - 1][j];
        }

        // Iterate through the triangle rows in reverse order
        for (let i = n - 2; i >= 0; i--) {
            for (let j = i; j >= 0; j--) {
                // Calculate the minimum path sum for current cell
                let down = triangle[i][j] + dp[i + 1][j];
                let diagonal = triangle[i][j] + dp[i + 1][j + 1];

                // Store the minimum of the two possible paths in dp
                dp[i][j] = Math.min(down, diagonal);
            }
        }
        // Top-left cell of dp now contains the minimum path sum
        return dp[0][0];
    }

    // Function to find out the minimum path sum
    minTriangleSum(triangle) {
        // Get the number of rows in the triangle
        let n = triangle.length;
        
        /* Initialize a memoization table
        to store computed results*/
        let dp = new Array(n).fill().map(() => new Array(n).fill(0));
    
        // Return the minimum path sum
        return this.func(triangle, n, dp);
    }
}

let triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
];

// Create an instance of Solution class
let sol = new Solution();

// Call the minTriangleSum function and print result
console.log(sol.minTriangleSum(triangle));

Complexity Analysis:

Time Complexity: O(N*N), where N is the number of rows. As the whole triangle is traversed once using two nested loops.

Space Complexity:O(N*N), As an external DP Array of size ‘N*N’ is used to store the intermediate calculations.

If we closely look at the relationship obltained in the tabulation approach, dp[i][j] = dp[i+1][j] + dp[i+1][j+1]), We see that the next row is only needed, in order to calculate dp[i][j]. Therefore space optimization can be applied on tabulation approach.

Initially we can take a dummy row ( say front). It is initialized to the triangle matrix's last row( as done in tabulation).

Now the current row(say cur) only needs the front row’s value in order to calculate dp[i][j].

At the next step, the 'cur' array becomes the 'front' of the next step and using its values we can still calculate the next row’s values.

At last, front [0] will give us the required answer for bottom-up approach.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // Function to find minimum path sum using space optimization
    int func(vector<vector<int> > &triangle, int n) {
        /* Create two arrays to store the
        current and previous row values*/
        
        // Represents the previous row
        vector<int> front(n, 0); 
        
        // Represents the current row
        vector<int> cur(n, 0);   
    
        /* Initialize the front array with values
        from the last row of the triangle*/
        for (int j = 0; j < n; j++) {
            front[j] = triangle[n - 1][j];
        }
    
        // Iterate through triangle rows in reverse order
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // Calculate minimum path sum for current cell
                int down = triangle[i][j] + front[j];
                int diagonal = triangle[i][j] + front[j + 1];
            
                /* Store the minimum of the two 
                possible paths in the current row*/
                cur[j] = min(down, diagonal);
            }
            /* Update the front array with
            the values from the current row*/
            front = cur;
        }
    
        /* The front array now contains the minimum path 
        sum from the top to the bottom of the triangle*/
        return front[0];
    }
public:
    //Function to find out the minimum path sum
    int minTriangleSum(vector<vector<int>>& triangle) {
        // Get the number of rows in the triangle
        int n = triangle.size();
    
        //Return the minimum path sum
        return func(triangle, n);
    }
};
int main() {
    vector<vector<int> > triangle{{1},
                                   {2, 3},
                                   {3, 6, 7},
                                   {8, 9, 6, 10}};
    
    //Create an instance of the Solution class
    Solution sol;
    
    // Call the minimumPathSum function and print result
    cout << sol.minTriangleSum(triangle);

    return 0;
}
class Solution {
    // Function to find minimum path sum using space optimization
    private int func(int[][] triangle, int n) {
        /* Create two arrays to store the
        current and previous row values*/
        
        // Represents the previous row
        int[] front = new int[n];
        
        // Represents the current row
        int[] cur = new int[n];
    
        /* Initialize the front array with values
        from the last row of the triangle*/
        for (int j = 0; j < n; j++) {
            front[j] = triangle[n - 1][j];
        }
    
        // Iterate through triangle rows in reverse order
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j >= 0; j--) {
                // Calculate minimum path sum for current cell
                int down = triangle[i][j] + front[j];
                int diagonal = triangle[i][j] + front[j + 1];
            
                /* Store the minimum of the two 
                possible paths in the current row*/
                cur[j] = Math.min(down, diagonal);
            }
            /* Update the front array with
            the values from the current row*/
            front = cur.clone();
        }
    
        /* The front array now contains the minimum path 
        sum from the top to the bottom of the triangle*/
        return front[0];
    }

    // Function to find out the minimum path sum
    public int minTriangleSum(int[][] triangle) {
        // Get the number of rows in the triangle
        int n = triangle.length;
    
        // Return the minimum path sum
        return func(triangle, n);
    }

    public static void main(String[] args) {
        int[][] triangle = {
            {1},
            {2, 3},
            {3, 6, 7},
            {8, 9, 6, 10}
        };
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the minTriangleSum function and print result
        System.out.println(sol.minTriangleSum(triangle));
    }
}
class Solution:
    # Function to find minimum path sum using space optimization
    def func(self, triangle, n):
        # Represents the previous row
        front = [0] * n
        
        # Represents the current row
        cur = [0] * n
    
        """ Initialize the front array with values
        from the last row of the triangle"""
        for j in range(n):
            front[j] = triangle[n - 1][j]
    
        # Iterate through triangle rows in reverse order
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                # Calculate minimum path sum for current cell
                down = triangle[i][j] + front[j]
                diagonal = triangle[i][j] + front[j + 1]
            
                """ Store the minimum of the two 
                possible paths in the current row"""
                cur[j] = min(down, diagonal)
            
            # Update front array with the values from current row
            front = cur[:]
    
        """ The front array now contains the minimum path
        sum from the top to the bottom of the triangle"""
        return front[0]

    # Function to find out the minimum path sum
    def minTriangleSum(self, triangle):
        # Get the number of rows in the triangle
        n = len(triangle)
    
        # Return the minimum path sum
        return self.func(triangle, n)

triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
]

# Create an instance of Solution class
sol = Solution()

# Call the minTriangleSum function and print result
print(sol.minTriangleSum(triangle))

class Solution {
    // Function to find minimum path sum using space optimization
    func(triangle, n) {
        // Represents the previous row
        let front = new Array(n).fill(0);
        
        // Represents the current row
        let cur = new Array(n).fill(0);
        
        /* Initialize the front array with values
        from the last row of the triangle*/
        for (let j = 0; j < n; j++) {
            front[j] = triangle[n - 1][j];
        }
        
        // Iterate through triangle rows in reverse order
        for (let i = n - 2; i >= 0; i--) {
            for (let j = 0; j <= i; j++) {
                // Calculate minimum path sum for current cell
                let down = triangle[i][j] + front[j];
                let diagonal = triangle[i][j] + front[j + 1];
                
                /* Store the minimum of the two 
                possible paths in the current row*/
                cur[j] = Math.min(down, diagonal);
            }
            // Update front array with the values from current row
            front.splice(0, i + 1, ...cur.slice(0, i + 1));
        }
        
        /* The front array now contains the minimum path 
        sum from the top to the bottom of the triangle*/
        return front[0];
    }

    // Function to find out the minimum path sum
    minTriangleSum(triangle) {
        // Get the number of rows in the triangle
        let n = triangle.length;
        
        // Return the minimum path sum
        return this.func(triangle, n);
    }
}

let triangle = [
    [1],
    [2, 3],
    [3, 6, 7],
    [8, 9, 6, 10]
];

// Create an instance of Solution class
let sol = new Solution();

// Call the minTriangleSum function and print result
console.log(sol.minTriangleSum(triangle));

Complexity Analysis:

Time Complexity: O(N*N), where N is the number of rows. As the whole triangle is traversed once using two nested loops.

Space Complexity:O(N)+O(N), As two external array of size ‘N’ is used to store the intermediate calculations of rows.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Why Greedy Approach will not work:

Steps to form the recursive solution:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code