120. Triangle
Triangle (LeetCode 120) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
How to solve Triangle
Triangle is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.
Work towards the solution in these steps:
- Think about using dynamic programming to solve this problem efficiently by breaking it down into smaller subproblems.
- Consider defining a state that represents the minimum path sum to reach each position in the current row.
- Use the relation that the minimum path sum at a given position depends on the minimum path sums of adjacent positions from the previous row.
The reference solution runs in O(n^2) time and O(1) space.
The Triangle solution and editorial walks through the full approach with reference code.
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 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
- -104 <= triangle[i][j] <= 104
Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
Topics and companies
Topics: Array, Dynamic Programming.
Reported in interviews at Amazon, Bloomberg.
How to practise Triangle on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(1) space.
Open Triangle in the code editor, or read the Triangle editorial for a worked solution with its approach and complexity analysis.
Where Triangle sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 2D Array (Unique Paths on Grid) subpattern
- The full DSA patterns sheet
Problems related to Triangle
Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:
- Count Square Submatrices with All Ones — Medium, same subpattern
- Interleaving String — Medium, same subpattern
- Longest Increasing Path in a Matrix — Hard, same subpattern
- Maximal Square — Medium, same subpattern
- Minimum Falling Path Sum — Medium, same subpattern
- Minimum Path Sum — Medium, same subpattern
Triangle FAQ
What is the LeetCode number of Triangle?
Triangle is LeetCode problem 120, rated Medium.
What pattern is used to solve Triangle?
Triangle is a Unique Paths on Grid problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
What is the time complexity of Triangle?
The reference solution runs in O(n^2) time and O(1) space.
Which companies ask Triangle?
Triangle has been reported in interviews at Amazon, Bloomberg.