Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Triangle | Leetcode 120 | All 4 DP Solutions
    Data Structures & Algorithms

    Triangle | Leetcode 120 | All 4 DP Solutions

    codeanddebugBy codeanddebug4 August 2025No Comments6 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve triangle
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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?

    Contents:
    • Solution 1: Brute Force (Recursion)
      • Intuition
      • Approach
      • Code
      • Code Explanation
      • Time and Space Complexity
      • Simplified
    • Solution 2: Memoization (Top-Down DP)
      • Intuition
      • Approach
      • Code
      • Code Explanation
      • Time and Space Complexity
      • Simplified
    • Solution 3: Tabulation (Bottom-Up DP)
      • Intuition
      • Approach
      • Code
      • Code Explanation
      • Dry Run Example
      • Time and Space Complexity
      • Simplified
    • Solution 4: Space-Optimized Tabulation (Optimal)
      • Intuition
      • Approach
      • Code
      • Code Explanation
      • Dry Run Example
      • Time and Space Complexity
      • Simplified
    • Summary Table
    • Conclusion

    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

    ApproachTimeSpaceBest Use
    Recursion (Brute Force)O(2^n)O(n)Learning, tiny triangles
    Memoization (Top-Down DP)O(n²)O(n²)Coding rounds, clarity
    Tabulation (Bottom-Up DP)O(n²)O(n²)Systematic, easy to debug
    Space-Optimized TabulationO(n²)O(n)Production/interview

    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!

    Join our Advance DSA COURSE

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

    Dynamic Programming on 2D Arrays Medium
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleMinimum Path Sum | Leetcode 64 | All 4 DP Solutions
    Next Article Minimum Falling Path Sum | Leetcode 931 | Variable Starting and Ending Points
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Minimum Falling Path Sum | Leetcode 931 | Variable Starting and Ending Points

    4 August 2025
    Data Structures & Algorithms

    Minimum Path Sum | Leetcode 64 | All 4 DP Solutions

    2 August 2025
    Data Structures & Algorithms

    Unique Paths II | Leetcode 63 | All 4 DP Solutions

    2 August 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (168)
      • Beginner (62)
      • Expert (39)
      • Intermediate (67)
    • Uncategorised (1)
    Recent Posts

    Minimum Falling Path Sum | Leetcode 931 | Variable Starting and Ending Points

    4 August 2025

    Triangle | Leetcode 120 | All 4 DP Solutions

    4 August 2025

    Minimum Path Sum | Leetcode 64 | All 4 DP Solutions

    2 August 2025

    Unique Paths II | Leetcode 63 | All 4 DP Solutions

    2 August 2025

    Unique Paths | Leetcode 62 | All 4 DP Solutions

    2 August 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.