Given a triangle array, return the minimum path sum from top to bottom.

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.

Here’s the [Problem Link] to begin with.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Solution 1: Brute Force (Recursion)

Intuition

At every cell (row, col), you have two choices:

• Move down (to (row+1, col))
• Move diagonal (to (row+1, col+1))
  Recursively try both, summing the cell value and picking the path with the minimum sum.

Approach

• Base case: If you’re at the last row, simply return the triangle’s value at that cell.
• Recursive case: Add current cell’s value to the min sum of the two options below.

Code

class Solution:
    def solve(self, row, col, triangle):
        # Base: Last row reached, only option is to take value
        if row == len(triangle) - 1:
            return triangle[row][col]
        # Option 1: Go down in the triangle
        down = triangle[row][col] + self.solve(row + 1, col, triangle)
        # Option 2: Go down-diagonal
        diagonal = triangle[row][col] + self.solve(row + 1, col + 1, triangle)
        # Return the minimum path sum
        return min(down, diagonal)

    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # Start recursion from the top of triangle
        return self.solve(0, 0, triangle)

Code Explanation

• Start at the top of the triangle.
• At each stage, recursively branch to both child positions (down/down-diagonal).
• At the leaf row, just return the number itself.
• The recursion automatically tries every possible valid top-to-bottom path.

Time and Space Complexity

• Time: O(2^n) (exponential, since each cell can branch to two children)
• Space: O(n) (recursion stack depth, n = number of rows)

Simplified

Simple, but tries all possible routes, quickly exponential for large triangles!

Solution 2: Memoization (Top-Down DP)

Intuition

Many subpaths are recalculated repeatedly. Use a 2D DP table, dp[row][col], to remember already computed minimums. Before recursion, check if the answer is cached!

Approach

• Create dp table, initialized to None.
• Before recursing, check if dp[row][col] is set.
• Store and re-use computed results.

Code

class Solution:
    def solve(self, row, col, triangle, dp):
        # Base: last row
        if row == len(triangle) - 1:
            return triangle[row][col]
        # Check if already computed
        if dp[row][col] is not None:
            return dp[row][col]
        # Recursively find minimum for down and diagonal
        down = triangle[row][col] + self.solve(row + 1, col, triangle, dp)
        diagonal = triangle[row][col] + self.solve(row + 1, col + 1, triangle, dp)
        dp[row][col] = min(down, diagonal)
        return dp[row][col]

    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        # DP table same size as triangle, all None
        dp = [[None] * n for _ in range(n)]
        return self.solve(0, 0, triangle, dp)

Code Explanation

• Adds a memoization table, so each (row, col) is evaluated once.
• If path sum from current cell is already solved, return it instantly.
• Converts exponential to polynomial time.

Time and Space Complexity

• Time: O(n²) (every cell solved only once)
• Space: O(n²) for dp + O(n) stack

Simplified

The “ACE” DP method for triangle: fast, clear, no repeats.

Solution 3: Tabulation (Bottom-Up DP)

Intuition

DP bottom-up: minimum path to reach each cell, starting from the last row (just its own values). Every upper cell is the cell value + the min of its two children (directly below and diagonal right).

Approach

• dp[i][j] means: min path starting at (i,j) down to base.
• Start: Fill last row.
• Move upwards, at each cell:
  dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])

Code

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        # Initiate DP grid, filled with None
        dp = [[None] * n for _ in range(n)]
        # Bottom row: path sum is value itself
        for j in range(n):
            dp[n - 1][j] = triangle[n - 1][j]
        # Build up from second-last row to top
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                # Option 1: Down
                down = triangle[i][j] + dp[i + 1][j]
                # Option 2: Down-diagonal
                diagonal = triangle[i][j] + dp[i + 1][j + 1]
                dp[i][j] = min(down, diagonal)
        return dp[0][0]

Code Explanation

• Fills from the bottom row upward.
• At every (i,j), you only need its two children (j, j+1) on the row below.
• Result: dp stores the minimum path from top.

Dry Run Example

With the same triangle:
Bottom-up, every cell gets its best min path, for the whole triangle.

Time and Space Complexity

• Time: O(n²) (every cell filled once)
• Space: O(n²) (explicit DP table)

Simplified

Traditional DP synthesis for triangle, very easy to trace. Efficient for interview use.

Solution 4: Space-Optimized Tabulation (Optimal)

Intuition

Each row only needs the DP values from the row below. Use two 1D arrays (prev and curr), switching as you move up the triangle.

Approach

• Initiate 1D prev array as the last row of triangle.
• For each upper row, make a new curr array of its length.
• For each cell, calculate min path using prev[j] and prev[j+1].
• At end of each row, set prev = curr.

Code

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        # Last row forms the initial DP array
        prev = [-1] * n
        for j in range(n):
            prev[j] = triangle[n - 1][j]
        # Move upwards from second-last row
        for i in range(n - 2, -1, -1):
            curr = [-1] * (i + 1)
            for j in range(i + 1):
                # Minimum path sum for current cell
                down = triangle[i][j] + prev[j]
                diagonal = triangle[i][j] + prev[j + 1]
                curr[j] = min(down, diagonal)
            prev = curr  # Update prev to current for next iteration
        return prev[0]

Code Explanation

• Only memory for two rows at a time.
• Seamlessly reduces O(n²) space to O(n).
• At the top, prev gives the answer.

Dry Run Example

Same triangle; at each step up, fill out the best in a 1D rolling array.

Time and Space Complexity

• Time: O(n²)
• Space: O(n) (just two rows at any time)

Simplified

Perfect for coding rounds with space constraints!

Summary Table

Conclusion

The Triangle Minimum Path Sum problem is a classic on LeetCode and a beautiful showcase for dynamic programming. If you’re new, start with recursion to build intuition. Move to memoization and iterative tabulation for true efficiency, and finish with space optimization for slick, real-world-ready code. Keep practicing DP for your next big interview!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.