NUHMAN.com

Introduction

LeetCode 120: Triangle asks us to find the minimum path sum from the top to the bottom of a triangle, where each step can move to an adjacent number in the row directly below. This problem is a classic dynamic programming (DP) problem, which can be efficiently solved using a bottom-up approach.

The triangle is represented as a 2D array, and the objective is to minimize the sum of the path starting from the top of the triangle and moving to adjacent numbers on each row until the bottom is reached.

Problem Statement

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

Each step you may move to an adjacent number of the row below. More formally, if you are on element triangle[i][j], you may move to either triangle[i+1][j] or triangle[i+1][j+1].

Example:

go

Input: 
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

Output: 11
Explanation: The minimum path sum is 2 + 3 + 5 + 1 = 11.

Approach:

Dynamic Programming Approach:

This problem can be solved efficiently using dynamic programming, specifically a bottom-up approach.

• Step 1: Start from the second-to-last row of the triangle and move upward. For each element in the row, update it by adding the minimum of the two adjacent elements in the row directly below it. This ensures that each element stores the minimum sum from that element to the bottom of the triangle.
• Step 2: After processing all rows, the top element of the triangle will hold the minimum path sum from the top to the bottom.

The reason we process the triangle from the bottom up is that each element depends only on the two elements directly below it, which makes it easy to update the values in place.

Go Implementation

Solution Using Bottom-Up Dynamic Programming

go

package main

import "fmt"

// minimumTotal returns the minimum path sum from top to bottom
func minimumTotal(triangle [][]int) int {
    // Start from the second-to-last row and move upwards
    for row := len(triangle) - 2; row >= 0; row-- {
        for col := 0; col <= row; col++ {
            // Update the current element to be the sum of itself and the minimum of the two adjacent elements in the row below
            triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1])
        }
    }
    
    // The top element now contains the minimum path sum
    return triangle[0][0]
}

// min function to return the minimum of two integers
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    triangle := [][]int{
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3},
    }
    result := minimumTotal(triangle)
    fmt.Println(result) // Output: 11
}

Explanation:

1. minimumTotal Function:

• The minimumTotal function iterates over the rows of the triangle from bottom to top (starting from the second-to-last row).
• For each element in the current row, we update its value to the sum of itself and the minimum of the two adjacent elements directly below it. This ensures that we are calculating the minimum sum for each path.
• The updated element now holds the minimum path sum starting from that element down to the bottom of the triangle.

1. min Function:

• The min function simply returns the smaller of two integers, which is used to calculate the minimum between the two adjacent elements in the row below.

1. Main Function:

• The main function demonstrates how to use the minimumTotal function by passing a sample triangle and printing the result.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Time Complexity:

• The time complexity is O(n), where n is the total number of elements in the triangle. We visit each element once to compute the minimum sum.

Space Complexity:

• The space complexity is O(1) because we are updating the triangle in place and not using any extra space apart from the input triangle.

Edge Cases

1. Edge Case: Empty Triangle

• Input: []
• Output: 0
• Explanation: If the triangle is empty, the minimum path sum is trivially 0.

1. Edge Case: Single Element Triangle

• Input: [[1]]
• Output: 1
• Explanation: A triangle with a single element has only one path, which is the element itself.

1. Edge Case: Large Triangle

• Input: A large triangle of size 1000x1000.
• Output: Efficient solution that computes the minimum path sum in O(n) time and O(1) space.

Conclusion

LeetCode 120: Triangle is a classic example of solving problems with dynamic programming using a bottom-up approach. By updating the triangle in place and calculating the minimum path sum iteratively, we achieve an optimal solution with both time and space complexity of O(n) and O(1), respectively.

This approach ensures efficiency, even for large inputs, and avoids the need for extra space for storing intermediate results.