LeetCode 120: Triangle Solution in Python – A Step-by-Step Guide

What Is LeetCode 120: Triangle?

In LeetCode 120: Triangle, you’re given a triangle represented as a list of lists, where each sublist is a row, and the number of elements increases by one as you go down. Starting at the top (row 0), you can move to an adjacent number in the row below (either directly below or one position to the right). Your goal is to find the minimum path sum from top to bottom. For example, with triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]], the minimum sum is 11 (2 → 3 → 5 → 1).

Problem Statement

• Input: A list of lists triangle representing the triangle.
• Output: An integer—the minimum path sum from top to bottom.
• Rules:
• Start at the top (row 0, index 0).
• Move to an adjacent number in the next row (j or j+1).
• Sum all numbers along the path.

Constraints

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

Examples

• Input: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
• Output: 11
• Why: Path 2 → 3 → 5 → 1 = 11.
• Input: triangle = [[-10]]
• Output: -10
• Why: Single number is the path.
• Input: triangle = [[1], [2, 3]]
• Output: 3
• Why: 1 → 2 = 3 (minimum of 3 or 4).

Understanding the Problem: Finding the Shortest Path

To solve LeetCode 120: Triangle in Python, we need to compute the minimum sum of a path from the top to the bottom of a triangle, moving only to adjacent numbers. A brute force approach—trying every possible path—takes O(2^n) time, which is impractical for up to 200 rows. Instead, we’ll use optimization techniques:

• Best Solution (Bottom-Up DP): O(n²) time, O(n) space—works upward efficiently.
• Alternative Solution (Top-Down Recursive with Memoization): O(n²) time, O(n²) space—explores downward with memory.

Let’s dive into the Best Solution—bottom-up dynamic programming—and break it down step-by-step.

Best Solution: Bottom-Up Dynamic Programming with O(n) Space

Why This Is the Best Solution

The bottom-up DP approach is the champion because it’s both time-efficient—O(n²)—and space-efficient—O(n), where n is the number of rows. It starts at the bottom and works up, using a single array to track minimum sums, overwriting as it goes. It’s like climbing the triangle backward, picking the best steps as you ascend—smart and lean!

How It Works

Here’s the strategy:

• Step 1: Start at the Bottom:
• Initialize a DP array with the bottom row’s values.
• Step 2: Work Upward:
• For each row from bottom-1 to top:
• For each element, compute the minimum sum by adding it to the smaller of the two possible sums below (j or j+1).
• Update the DP array in-place.
• Step 3: Result:
• The top element (dp[0]) is the minimum path sum.

Step-by-Step Example

Example: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]

• Bottom Row (dp): [4, 1, 8, 3].
• Row 2 (6, 5, 7):
• dp[0] = 6 + min(4, 1) = 6 + 1 = 7.
• dp[1] = 5 + min(1, 8) = 5 + 1 = 6.
• dp[2] = 7 + min(8, 3) = 7 + 3 = 10.
• dp = [7, 6, 10].
• Row 1 (3, 4):
• dp[0] = 3 + min(7, 6) = 3 + 6 = 9.
• dp[1] = 4 + min(6, 10) = 4 + 6 = 10.
• dp = [9, 10].
• Row 0 (2):
• dp[0] = 2 + min(9, 10) = 2 + 9 = 11.
• dp = [11].
• Result: 11.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # Step 1: Initialize dp with bottom row
        dp = triangle[-1].copy()

        # Step 2: Work up from second-to-last row
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                # Min sum = current + min of two below
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

        # Step 3: Return top element
        return dp[0]

• Line 4: Copy bottom row to dp.
• Line 7: Loop from second-to-last row to top.
• Line 8-9: For each element in row i:
• Line 9: Update dp[j] with current value plus min of two below.
• Line 12: Return minimum sum at top.
• Time Complexity: O(n²)—each element processed once, total ~n²/2.
• Space Complexity: O(n)—single array of size equal to bottom row.

This climbs up with minimal baggage!

Alternative Solution: Top-Down Recursive with Memoization

Why an Alternative Approach?

The top-down recursive approach with memoization offers a different perspective—O(n²) time, O(n²) space. It explores paths from the top down, caching results to avoid recomputation. It’s like scouting every route with a map to remember where you’ve been—intuitive but heavier on space.

How It Works

Here’s the plan:

• Step 1: Define recursive function min_path(row, col):
• Minimum path sum from triangle[row][col] to bottom.
• Step 2: Base Case:
• If row == len(triangle) - 1, return the bottom row value.
• Step 3: Recurrence:
• Return current value + min of paths to left and right below.
• Step 4: Memoize to optimize.

Step-by-Step Example

Example: triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]

• min_path(0, 0):
• 2 + min(min_path(1, 0), min_path(1, 1)).
• min_path(1, 0):
• 3 + min(min_path(2, 0), min_path(2, 1)) = 3 + min(6+4, 6+1) = 3 + 7 = 10.
• min_path(1, 1):
• 4 + min(min_path(2, 1), min_path(2, 2)) = 4 + min(5+1, 5+8) = 4 + 6 = 10.
• min_path(0, 0):
• 2 + min(10, 10) = 11.
• Result: 11.

Code for Recursive Approach

Copy codeclass Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        memo = {}

        def min_path(row, col):
            if row == len(triangle) - 1:
                return triangle[row][col]
            if (row, col) in memo:
                return memo[(row, col)]

            left = min_path(row + 1, col)
            right = min_path(row + 1, col + 1)
            memo[(row, col)] = triangle[row][col] + min(left, right)
            return memo[(row, col)]

        return min_path(0, 0)

• Line 4: Memoization dictionary.
• Line 6-14: Recursive function:
• Line 7-8: Base case—bottom row.
• Line 10-12: Compute min of left and right paths.
• Line 13: Cache and return.
• Time Complexity: O(n²)—each position computed once.
• Space Complexity: O(n²)—memo table.

It’s a top-down explorer with a memory boost!

Comparing the Two Solutions

• Bottom-Up DP (Best):
• Pros: O(n²) time, O(n) space, iterative, efficient.
• Cons: Less intuitive direction.
• Top-Down Recursive (Alternative):
• Pros: O(n²) time, O(n²) space, natural pathfinding.
• Cons: More space, recursion overhead.

Bottom-up wins for space efficiency.

Additional Examples and Edge Cases

• [[1]]: 1.
• [[-1], [2, 3]]: 1 (-1 + 2).
• [[1], [2, 3], [1, -5, -10]]: -4 (1 + 2 + -5).

Both handle these well.

Complexity Breakdown

• Bottom-Up: Time O(n²), Space O(n).
• Recursive: Time O(n²), Space O(n²).

Bottom-up’s leaner space shines.

Key Takeaways

• Bottom-Up: Climb up smartly!
• Top-Down: Explore with memory!
• Paths: Min choices at each step.
• Python Tip: Arrays optimize—see [Python Basics](/python/basics).

Final Thoughts: Sum It Down

LeetCode 120: Triangle in Python is a pathfinding treat. The bottom-up DP approach scales efficiently, while top-down recursion offers clarity. Want more DP fun? Try LeetCode 64: Minimum Path Sum or LeetCode 1143: Longest Common Subsequence. Ready to find your path? Head to Solve LeetCode 120 on LeetCode and minimize that sum today!