algoadvance

Leetcode 120. Triangle

Problem Statement

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.

Example 1:

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

Example 2:

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

Constraints:

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

Clarifying Questions

1. Q: Should I assume valid input where each row has exactly one more element than the previous row? A: Yes, you can assume the input follows the constraint where each row has exactly one more element than the previous row.

2. Q: Are we allowed to modify the input triangle? A: Yes, you can modify the input triangle if it helps simplify the solution.

Strategy

We will use Dynamic Programming (DP) to solve this problem. The idea is to start from the second-last row and move upwards, adjusting each element to represent the minimum path sum to the bottom starting from that element.

Steps:

1. Start from the second last row and move upwards.
2. For each element, calculate the minimum path sum by taking the current element value plus the minimum of the elements directly below and directly below-right.
3. Continue this process until the top of the triangle.
4. The top element will contain the minimum path sum from top to bottom.

Code

Here is the implementation in C++:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        // Start from the second last row and move upwards to the top
        for (int row = triangle.size() - 2; row >= 0; --row) {
            for (int col = 0; col < triangle[row].size(); ++col) {
                // Update the current value to the minimum path sum to the bottom
                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];
    }
};

Time Complexity

• Time Complexity: O(n^2), where n is the number of rows in the triangle. We iterate over each element once in a nested loop.
• Space Complexity: O(1) additional space since we modify the input triangle in place.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?