Difficulty: Medium Link: Day 21: April Leetcode Challenge
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.
Input: triangle = [,[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).
Input: triangle = [[-10]] Output: -10
1 <= triangle.length <= 200
triangle.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?
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.
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).
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.
Swift : Recursive Approach(Top – down)
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.
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)