Jobs

Interviews

Discussions

Triangle

Medium

Oracle

1 view

Topics:

ArraysDynamic Programming

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 triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

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⁴ <= triangle[i][j] <= 10⁴

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Triangle

Medium

Oracle

1 view

Topics:

ArraysDynamic Programming

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 triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

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⁴ <= triangle[i][j] <= 10⁴

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the triangle (number of rows)?
Can the values in the triangle be negative, zero, or only positive integers?
Is the input triangle guaranteed to be a valid triangle (e.g., row i has i+1 elements)?
Are we looking for *a* minimum path sum, or *all* minimum path sums? If multiple such paths exist, can I return any one of them?
Can the triangle be empty (i.e., have zero rows)? If so, what should I return?

Brute Force Solution

Approach

The brute force approach to this problem involves exploring every single possible path from the top to the bottom of the triangle. It's like trying out every route you could take, no matter how silly it seems at first. By checking every possibility, we guarantee we'll find the best one.

Here's how the algorithm would work step-by-step:

Start at the top of the triangle.
Consider every possible path downwards. At each step, you can go to either the number directly below you, or the number to the right of that.
For each path from the top to the bottom, add up all the numbers you encounter along that path.
Keep track of the sum for every possible path.
Once you've explored every single path from top to bottom and have the sum for each, compare all the sums.
The smallest sum represents the minimum path sum; that's your answer.

Code Implementation

def find_minimum_total_brute_force(triangle):
    minimum_total = float('inf')

    def calculate_path_sum(row_index, column_index, current_path_sum):
        nonlocal minimum_total

        current_path_sum += triangle[row_index][column_index]

        # If we've reached the bottom, check minimum.
        if row_index == len(triangle) - 1:
            minimum_total = min(minimum_total, current_path_sum)
            return

        # Explore moving down.
        calculate_path_sum(row_index + 1, column_index, current_path_sum)

        # Explore moving down and right, if possible.
        if column_index + 1 < len(triangle[row_index + 1]):

            calculate_path_sum(row_index + 1, column_index + 1, current_path_sum)

    # Start recursion at the top of triangle.
    calculate_path_sum(0, 0, 0)

    return minimum_total

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores every possible path from the top to the bottom of the triangle. At each level of the triangle, we have two choices: move to the directly below element or the right-of-the-directly-below element. Since there are approximately n levels in the triangle, and we have 2 choices at each level, the number of paths we explore grows exponentially. Therefore, the total number of paths is roughly 2 * 2 * ... * 2 (n times), which is 2^n. Hence the time complexity is O(2^n).

Space Complexity

O(N!) – The brute force approach described explores every possible path from the top to the bottom of the triangle. The number of paths grows factorially with the number of rows, N, in the triangle. To store each of these paths to calculate their sums, we'd need to store path information, although implicitly. Therefore, the space needed is related to the number of paths, which is roughly proportional to N! Thus, the auxiliary space complexity is O(N!).

Optimal Solution

Approach

The goal is to find the smallest path from the top of the triangle to the bottom. We can efficiently solve this by working backward from the bottom, building up the solution using previously calculated minimum path sums.

Here's how the algorithm would work step-by-step:

Start at the second-to-last row of the triangle.
For each number in this row, find the smaller of the two numbers directly below it in the next row.
Add this smaller number to the current number in the row we're looking at. Replace the current number with the sum.
Move up one row and repeat the process, always choosing the smaller number in the row below and adding it to the current number.
Continue this process until you reach the top of the triangle. The single number at the top will be the smallest possible total path sum.

Code Implementation

def minimum_total_path(triangle):
    number_of_rows = len(triangle)

    # Iterate from the second to last row to the top.
    for i in range(number_of_rows - 2, -1, -1):
        for j in range(len(triangle[i])):
            # Find the smaller of the two numbers directly below.
            smaller_path = min(triangle[i + 1][j], triangle[i + 1][j + 1])

            # Add the smaller path to the current number.
            triangle[i][j] += smaller_path

    # The top element now contains the minimum total path sum.
    return triangle[0][0]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the triangle from the second-to-last row up to the top row. The number of elements in each row increases from 1 to n where n is the number of rows in the triangle. The inner operation involves a constant-time comparison and addition for each element in each row. The total number of elements processed is approximately n * (n+1) / 2. The algorithm processes each number once, and because the number of total elements in the triangle is n * (n+1) / 2, the time complexity is O(n).

Space Complexity

O(1) – The algorithm modifies the input triangle in-place. It doesn't use any auxiliary data structures like temporary lists, hashmaps, or recursion stack frames that scale with the input size. Although the triangle itself occupies space, we are only considering *auxiliary* space complexity, which is the extra memory used *beyond* the input. Since the algorithm operates directly on the input triangle by overwriting its values and uses only a few constant memory integer variables for indexing, the auxiliary space complexity is constant, O(1).

Edge Cases

Case	How to Handle
Empty triangle (triangle is null or empty)	Return 0 since there's no path or any element in the triangle
Triangle with only one row (triangle.length == 1)	Return the single element in the row triangle[0][0] directly as the minimum path sum
Triangle with a row containing a very large negative number	The dynamic programming solution will handle negative numbers correctly, potentially lowering the overall sum, but need to check for integer overflow if sums become too large
Triangle with a row containing a very large positive number	Ensure that integer overflow doesn't occur when accumulating path sums, which can be mitigated using larger data types or modulo operations (if applicable given prompt constraints)
Triangle with all elements being zero	The algorithm should correctly compute the minimum path sum as zero
Triangle with skewed distribution (e.g., first few rows have small values, later rows have very large values)	Dynamic programming will still find the optimal path, but the skewed values could expose potential integer overflow issues, so we should watch out for those
Maximum sized triangle (large number of rows)	Ensure the solution's space complexity remains within acceptable bounds, using dynamic programming with row optimization, which avoids storing the entire triangle's sum matrix
Integer overflow when summing path values in the triangle	Use long data type to store intermediate sums to avoid overflow or consider using modulo arithmetic if problem constraints allow/require it

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the triangle (number of rows)?
Can the values in the triangle be negative, zero, or only positive integers?
Is the input triangle guaranteed to be a valid triangle (e.g., row i has i+1 elements)?
Are we looking for *a* minimum path sum, or *all* minimum path sums? If multiple such paths exist, can I return any one of them?
Can the triangle be empty (i.e., have zero rows)? If so, what should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the top of the triangle.
Consider every possible path downwards. At each step, you can go to either the number directly below you, or the number to the right of that.
For each path from the top to the bottom, add up all the numbers you encounter along that path.
Keep track of the sum for every possible path.
Once you've explored every single path from top to bottom and have the sum for each, compare all the sums.
The smallest sum represents the minimum path sum; that's your answer.

Code Implementation

def find_minimum_total_brute_force(triangle):
    minimum_total = float('inf')

    def calculate_path_sum(row_index, column_index, current_path_sum):
        nonlocal minimum_total

        current_path_sum += triangle[row_index][column_index]

        # If we've reached the bottom, check minimum.
        if row_index == len(triangle) - 1:
            minimum_total = min(minimum_total, current_path_sum)
            return

        # Explore moving down.
        calculate_path_sum(row_index + 1, column_index, current_path_sum)

        # Explore moving down and right, if possible.
        if column_index + 1 < len(triangle[row_index + 1]):

            calculate_path_sum(row_index + 1, column_index + 1, current_path_sum)

    # Start recursion at the top of triangle.
    calculate_path_sum(0, 0, 0)

    return minimum_total

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the second-to-last row of the triangle.
For each number in this row, find the smaller of the two numbers directly below it in the next row.
Add this smaller number to the current number in the row we're looking at. Replace the current number with the sum.
Move up one row and repeat the process, always choosing the smaller number in the row below and adding it to the current number.
Continue this process until you reach the top of the triangle. The single number at the top will be the smallest possible total path sum.

Code Implementation

def minimum_total_path(triangle):
    number_of_rows = len(triangle)

    # Iterate from the second to last row to the top.
    for i in range(number_of_rows - 2, -1, -1):
        for j in range(len(triangle[i])):
            # Find the smaller of the two numbers directly below.
            smaller_path = min(triangle[i + 1][j], triangle[i + 1][j + 1])

            # Add the smaller path to the current number.
            triangle[i][j] += smaller_path

    # The top element now contains the minimum total path sum.
    return triangle[0][0]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty triangle (triangle is null or empty)	Return 0 since there's no path or any element in the triangle
Triangle with only one row (triangle.length == 1)	Return the single element in the row triangle[0][0] directly as the minimum path sum
Triangle with a row containing a very large negative number	The dynamic programming solution will handle negative numbers correctly, potentially lowering the overall sum, but need to check for integer overflow if sums become too large
Triangle with a row containing a very large positive number	Ensure that integer overflow doesn't occur when accumulating path sums, which can be mitigated using larger data types or modulo operations (if applicable given prompt constraints)
Triangle with all elements being zero	The algorithm should correctly compute the minimum path sum as zero
Triangle with skewed distribution (e.g., first few rows have small values, later rows have very large values)	Dynamic programming will still find the optimal path, but the skewed values could expose potential integer overflow issues, so we should watch out for those
Maximum sized triangle (large number of rows)	Ensure the solution's space complexity remains within acceptable bounds, using dynamic programming with row optimization, which avoids storing the entire triangle's sum matrix
Integer overflow when summing path values in the triangle	Use long data type to store intermediate sums to avoid overflow or consider using modulo arithmetic if problem constraints allow/require it