Triangle

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Top down
  • Top is the pointy top of the triangle.
  • On each iteration, you have a choice.
    • Collect the current plus ith index in the next row.
    • Collect the current plus the i + 1th index in the next row.
• Bottom up
  • Bottom is the last row
  • Starting from the second to last row, one “collects” as such:
    • The current position is itself plus the next row’s same position, or itself plus the next row’s i + 1th index position added up.
• One needs not do a check for out of bounds, since there is guaranteed to be an index i and i + 1.
  • This is because in the next row, the row expands by one to the left and one to the right.

Complexity

Runtime

• $O(MN)$, where M is the number of rows and N is the number of columns.
• And N increases by the row plus one each time, so this could be written as $O(M^2)$ (due to Summation Formulations arithmetic series).

Space

• $O(1)$ since we are using the original triangle to store our computations.

Code

Bottom Up

Simplified

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for row in reversed(range(len(triangle) - 1)): # Starting from the bottom going upwards
            for col in range(len(triangle[row])): # For row one below the current one
                triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])
        return triangle[0][0]

Unnecessary If Check

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for row in reversed(range(len(triangle) - 1)): # Starting from the bottom going upwards
            for col in range(len(triangle[row])): # For row one below the current one
                sr1 = triangle[row + 1][col] if 0 <= col < len(triangle[row + 1]) else inf
                sr2 = triangle[row + 1][col + 1] if 0 <= col + 1 < len(triangle[row + 1]) else inf
                triangle[row][col] += min(sr1, sr2)
        return triangle[0][0]

Top Down

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        @cache
        def r(r_idx, c_idx):
            if r_idx == n or c_idx >= n:
                return 0
            sr1 = r(r_idx + 1, c_idx)
            sr2 = r(r_idx + 1, c_idx + 1)
            return triangle[r_idx][c_idx] + min(sr1, sr2)
        return r(0, 0)

Notes

Cards

START Basic Front: Triangle Back: Starting from the 2nd to last row, collect the ith and i + 1th index plus yourself, and then build upwards from there.

END

---

References

• Triangle