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:

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.

Constraints:

  1. 1 <= triangle.length <= 200
  2. triangle[0].length == 1
  3. triangle[i].length == i + 1 for i == 0, 1, 2, ..., triangle.length - 1
  4. -10^4 <= triangle[i][j] <= 10^4

Clarifying Questions

  1. Should we always expect the triangle to be non-empty as per the given constraints?
  2. Are there any negative numbers in the triangle array, and do they affect the calculation?
  3. Should the solution be optimized for time or space complexity in any specific way or can we use brute force if necessary?

Strategy

To solve the problem efficiently, we can use dynamic programming. Starting from the second to last row, we will iterate upwards back to the top row, updating each element to be the sum of itself and the minimum of the two elements directly below it. This will provide the minimum path sum from the top to the bottom:

  1. Start from the second to last row and move upwards.
  2. For each element, update it to be the sum of itself and the minimum of the two elements directly below it in the triangle.
  3. The top element in the modified triangle will contain the minimum path sum.

Code

Here is a Java implementation of the described strategy:

import java.util.List;

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // Start from the second to last row and move up to the top.
        for (int row = triangle.size() - 2; row >= 0; row--) {
            for (int col = 0; col < triangle.get(row).size(); col++) {
                // Update each element to be the sum of itself and the min of the elements below it
                int minSumBelow = Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1));
                triangle.get(row).set(col, triangle.get(row).get(col) + minSumBelow);
            }
        }
        
        // The top element now contains the minimum path sum
        return triangle.get(0).get(0);
    }
}

Time Complexity

The time complexity of this solution is O(n^2), where n is the number of rows in the triangle. This is because we are iterating through each row once and performing a constant amount of work for each element.

Space Complexity

The space complexity is O(1) (ignoring the input) because we are modifying the input list in place and not using any extra space.

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