MediumNo. 0120

Triangle — LeetCode 120 Python Solution

Topics
Array, Dynamic Programming
On a study list
Top Interview 150
Reading time
2 min

The problem

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.

Example

Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
Explanation
The triangle looks like:

Python solution

PythonSolution
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        f = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1):
                f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j]
        return f[0][0]

Complexity

Time
O(n2)
Space · auxiliary
O(n)where n is the number of rows in the triangle

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 120. Triangle is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 120. Triangle?

LeetCode 120. Triangle is rated Medium on LeetCode.

What is the time complexity of LeetCode 120. Triangle?

The Python solution on this page runs in O(n2).

What is the space complexity of LeetCode 120. Triangle?

The Python solution on this page uses O(n), where n is the number of rows in the triangle auxiliary space.

What topics does LeetCode 120. Triangle cover?

LeetCode 120. Triangle is tagged Array and Dynamic Programming on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.