LeetCode 120: Triangle Solution

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We start from the second bottom row of the triangle and calculate the minimum path sum for each element by adding the element value to the minimum of the adjacent elements in the row below. We continue this process until we reach the top of the triangle.

Algorithm:
1. Start from the second bottom row of the triangle.
2. For each element in the row, update it to the minimum path sum: triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]).
3. Repeat this process moving upwards row by row until reaching the top of the triangle.
4. The top element will contain the minimum path sum.
Time Complexity: O(n^2), where n is the number of rows in the triangle.
Space Complexity: O(n), where n is the number of rows in the triangle.

Solution Code

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        
        return dp[0];
    }
}

Frequently Asked Questions

How to solve LeetCode 120 (Triangle)?

This page provides optimized solutions for LeetCode problem 120 (Triangle) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 120 (Triangle)?

The time complexity for LeetCode 120 (Triangle) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 120 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 120 in Java, C++, or Python.