Triangle (Leetcode 120)

Difficulty: Medium Link: Day 21: April Leetcode Challenge

Problem Description

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?

Solution

Recursion

This is a classical Dynamic Programming problem but focus on breaking the problem down into smaller sub problems. If we imagine the triangle into a n x n representation, then would be easier to visualise the next possible sub problems. In every row, the number of columns are same as row count, so the first row has 1 col and Nth row has N columns.

Matrix Representation of the triangle

We can observe that at any cell in the matrix, there could be maximum two paths ie, the down (same column) and the diagonal (increment) the columns. So for [i , j] element the possible paths would be [i + 1, j ] (Down) or [i +1, j + 1] (diagonal) path. Which ever path we choose, the total sum of that path would be equal to the element + min of the possible paths (Down/ Diagonal).

func getMinimumPath(for row:Int, col: Int) {
// conditions
// Down
let sumDown = minTotalHelper(triangle, row + 1, col)
// Diagonal
let sumDiagonal = minTotalHelper(triangle,row + 1, col + 1)
// Add the min of both paths to the element
let totalSum = triangle[row][col] + min(sumNextColumn, sumSameColumn)
}
view raw min_path.swift hosted with ❤ by GitHub

We can start from the first row and keep doing that till the last. The sub problems would be solved in the following manner. We also need to take care of the terminal conditions for row and cols, 0 <= row < n.

Code

Swift : Recursive Approach(Top – down)

class Solution {
func minimumTotal(_ triangle: [[Int]]) -> Int {
let minPath = minTotalHelper(triangle, 0 ,0)
return minPath
}
func minTotalHelper(_ triangle:[[Int]],_ row: Int, _ col:Int) -> Int{
guard row >= 0, col >= 0, row < triangle.count else { return 0}
if col > row { return 0}
let sumSameColumn = minTotalHelper(triangle, row + 1, col)
let sumNextColumn = minTotalHelper(triangle,row + 1, col + 1)
let totalSum = triangle[row][col] + min(sumNextColumn, sumSameColumn)
return totalSum
}
}

Dynamic Programming : Memoization

When submitting the same solution we would get TLE(Time limit exceed) for huge input values. Hence we can use dynamic programming to cache the subproblems result to save time. We can maintain a Memoization table for storing the results for every [row][col]. I have used a dictionary here because we do not require the random access and used the key format “row:col” to query and save the key value pairs.

Swift: DP

class Solution {
var dp: [String:Int]!
func minimumTotal(_ triangle: [[Int]]) -> Int {
dp = [String:Int]()
let minPath = minTotalHelper(triangle, 0 ,0)
return minPath
}
func minTotalHelper(_ triangle:[[Int]],_ row: Int, _ col:Int) -> Int{
guard row >= 0, col >= 0, row < triangle.count else { return 0}
if col > row { return 0}
let key = "\(row):\(col)"
if let cachedValue = dp[key]{
return cachedValue
}
let sumSameColumn = minTotalHelper(triangle, row + 1, col)
let sumNextColumn = minTotalHelper(triangle,row + 1, col + 1)
let totalSum = triangle[row][col] + min(sumNextColumn, sumSameColumn)
dp[key] = totalSum
return totalSum
}
}
view raw triangle_dp.swift hosted with ❤ by GitHub

Complexity Analysis

Since there are n rows and the number of columns are same as the row, the total elements are O(n2). The recursive helper function would be called once atleast for every element hence, O(n2) operations would be done. Similarly, even though the recursion stack would be O(N) space but the maximum number of elements that can we stored are n2.

Time = O(n2)

Space = O(n2)

Leave a Reply

Your email address will not be published. Required fields are marked *