modified the solution to inplace class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: if not triangle: return 0
for row in range(len(triangle)-2, -1, -1): for index, value in enumerate(triangle[row]): triangle[row][index] = value + min(triangle[row+1][index], triangle[row+1][index+1]) return triangle[0][0]
As someone who has absolutely NO coding background and just started at mid-to-late August, I just want to THANK YOU for making these terrific videos! I just passed the first round of tech interview at Huawei only because of you!!! I highly recommend your channel to everyone who wants to become a swe!!!
@@larrygoldstein2438 Sorry I got mistaken with what's on leetcode and whats the example that Neetcode has here in his video. It is actually 7 in his example. however on leetcode, the example given is [[2],[3,4],[6,5,7],[4,1,8,3]]. Which is 10. In the example that Neetcode has here he is evaluating [[2],[3,4],[6,5,4],[4,1,8,3]]
This channel is a legitimate goldmine. I solved this problem top-down but I'm grateful I checked out this channel all the same because the bottom-up solution is 10x more elegant.
the question is quite similar to minimum path sum in grid..... so here is the soln : class Solution { public: int minimumTotal(vector& triangle) {
vector dp(201, vector(201, -1)); int result = solve(triangle, triangle.size(), 0, 0, dp); return result; } int solve(vector& triangle, int m, int i , int j , vector& dp){ int n = triangle[i].size(); if(i >= m && j >= n) return INT_MAX; if(i == m-1) return triangle[i][j]; if(dp[i][j] != -1) return dp[i][j]; int ans1 = solve(triangle, m, i+1, j, dp); int ans2 = solve(triangle, m, i+1, j+1, dp); int res = min(ans1, ans2) + triangle[i][j]; return dp[i][j] = res; } };
I dont think anyone can draw and explain recursive or dfs trees better than you. Thanks @neetcode. I added this question to 'Favorites' on my leetcode.
Excellent visualization and explanation of your problems. Your voice is best suited for professor of any big university. Just one question - What tool do you use for visualization?
I did it myself, but thanks to NeetCode, I had no coding background, no degree, its been 4 months Ive started coding in Leetcode and unity ( a game engine ). I learned a lot in this channel.
After 1 hour and a half of grinding, i solved it with a "Runtime: 88 ms, faster than 44.09% of Python3 online submissions for Triangle."(with dfs and memoization), i wouldn't have found it in an interview setting in a million years xD These pbs are tough...
dp[i] = n + min(dp[i], dp[i+1]) is neet! After updating dp[0], we don't need its value for the rest of updates till we are done with the current row. This is due to the shape of a triangle. Update: You explained it already after the code :)
C++ solution for the same question class Solution { public: int minimumTotal(vector& nums) { int n = nums.size(); int last = nums[n-1].size(); int ans=nums[0][0];
You made a mistake when explaining your intuition at 14:09, when you replaced 8 with 12, but should have been 7 i.e. (4 + min(8, 3)). Not something big but just telling FYI. Thanks for all the content
Why not to store dp actually in triangle row itself? You gonna reduce unnecessar space usage, this my solution (JAVA): public int minimumTotal(List triangle) {
for (int row = triangle.size()-2; row >= 0; row--){
List currRow = triangle.get(row); List prevRow = triangle.get(row+1); for ( int i = 0; i < currRow.size(); i++){ currRow.set(i, currRow.get(i) + Math.min(prevRow.get(i), prevRow.get(i+1))); } } return triangle.get(0).get(0); }
I am new at dp, I somehow manage to write the code but have trouble with memoization, can anyone help with this code? def total(i, row, count): if i>=len(triangle[row]): return float("inf") count+=triangle[row][i] if row==len(triangle)-1: return count return min(total(i, row+1, count), total(i+1, row+1, count))
class Solution { public: int minimumTotal(vector& triangle) { int n = triangle.size();
for(int i=n-2; i>=0; i--){ int m = triangle[i].size();
for(int j=0; j initially we have considered last row as leafs it-0: trriangle[3] = [4, 1, 8, 3] Now, start traversing triangle from 2nd last row to the top: it-1: triangle[2] = [7, 6, 10] it-2: triangle[1] = [9, 10] it-3: triangle[0] = [11] // final iteration storing our result at triangle[0] */
Just a word of advice, not include dynamic programming in the title or hash tag, it's kind of a spoiler for many viewers who are attempting to solve the question first before watching your videos.
INPLACE SOLUTION, YOU CAN CHOOSE NOT TO USE THE EXTRA TABLE IF WANT TO. THANK YOU. ``` class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: if not triangle: return 0
for row in range(len(triangle)-2, -1, -1): for index, value in enumerate(triangle[row]): triangle[row][index] = value + min(triangle[row+1][index], triangle[row+1][index+1]) return triangle[0][0] ```
Both works. Enumerating is just a shorter way to write code so you can: 1. Avoid writing range(len(array)) 2. Avoid writing array[idx] to get the item at the current `idx` index If you are not comfortable with enumerate yet just avoid it for now and use in range len. It does the exact same thing. ```python # slightly shorter enumerate code for idx, num in enumerate(array): ... # this is equivalent to above for loop for idx in range(len(array)): num = array[idx] ... ```
If someone(like me) wants to start from 1 row and go all the way to the last: def min_path_sum(triangle): dp = [float('inf')] * len(triangle[-1]) dp[0] = triangle[0][0] for row in triangle[1:]: for index, element in reversed(list(enumerate(row))): if index != 0: dp[index] = element + min(dp[index], dp[index-1]) else: dp[index] = element + dp[0] return min(dp)
![[UNCUT] “บอสณวัฒน์” ลากไส้!! ใครหนุนหลัง "แม่ตั๊ก ป๋าเบียร์" I คนดังนั่งเคลียร์ I 30 ก.ย. 67](http://i.ytimg.com/vi/QlD7mU2KKRk/mqdefault.jpg)
Dynamic Programming Playlist: th-cam.com/video/73r3KWiEvyk/w-d-xo.html
modified the solution to inplace
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle:
return 0
for row in range(len(triangle)-2, -1, -1):
for index, value in enumerate(triangle[row]):
triangle[row][index] = value + min(triangle[row+1][index], triangle[row+1][index+1])
return triangle[0][0]
I lost the hope when I realized my IQ was -90.
As someone who has absolutely NO coding background and just started at mid-to-late August, I just want to THANK YOU for making these terrific videos! I just passed the first round of tech interview at Huawei only because of you!!! I highly recommend your channel to everyone who wants to become a swe!!!
Thanks for the video. I've been following along. 14:10 should be 3+4 = 7 I think.
It actually should be 10.
[4, 1, 8, 3, 0]
[7, 6, 10]
[9, 10]
[11]
@@DoJoStan Why should it be 10 instead of 7? Thanks
@@larrygoldstein2438 Sorry I got mistaken with what's on leetcode and whats the example that Neetcode has here in his video. It is actually 7 in his example. however on leetcode, the example given is [[2],[3,4],[6,5,7],[4,1,8,3]]. Which is 10.
In the example that Neetcode has here he is evaluating [[2],[3,4],[6,5,4],[4,1,8,3]]
Right
This channel is a legitimate goldmine. I solved this problem top-down but I'm grateful I checked out this channel all the same because the bottom-up solution is 10x more elegant.
I finally understood dynamic programming. Whoever fully understands the concepts in this video, will definitely pass the algorithm interview.
me understanding the theory but being too dumb for programming by myself
@@SK-cd9kk you need practice. Do not give up so quick. How do you think people get good at something?
@@yilmazbingol4838 i am just at the beginning of learning solving algorithms, so i will go on
Same! It feels so cool to finally understand the concepts, good luck on your programming journeys everyone
I did something clever and instead of allocating new memory I just reused the given array, starting from second last row to the top
That's smart, I didn't think of that, nice!
*THE* clearest way I've seen on this problem! Really appreciate the drawing at the end on how the algorithms stores the result. Thank you so much!!
the question is quite similar to minimum path sum in grid.....
so here is the soln :
class Solution {
public:
int minimumTotal(vector& triangle) {
vector dp(201, vector(201, -1));
int result = solve(triangle, triangle.size(), 0, 0, dp);
return result;
}
int solve(vector& triangle, int m, int i , int j , vector& dp){
int n = triangle[i].size();
if(i >= m && j >= n) return INT_MAX;
if(i == m-1) return triangle[i][j];
if(dp[i][j] != -1) return dp[i][j];
int ans1 = solve(triangle, m, i+1, j, dp);
int ans2 = solve(triangle, m, i+1, j+1, dp);
int res = min(ans1, ans2) + triangle[i][j];
return dp[i][j] = res;
}
};
@14:13, dp row should be 7, 6, 7, right? 4+ min(8, 3) = 7
It should be 7 in given example but in leetcode, there is 7 instead of 4. So, it should be 10 i.e., 7 + min(8, 3) = 10
@@inFamous16 Thanks, I was so confused !
after 120 consecutive days of practicing, now i can solve problem just after seeing your visual explanation.
I dont think anyone can draw and explain recursive or dfs trees better than you. Thanks @neetcode. I added this question to 'Favorites' on my leetcode.
The solution just blew my mind. This approach is simply genius ! Thank You.
@neetcode knows how to teach ds algo in the correct way... kudos to you
Excellent visualization and explanation of your problems. Your voice is best suited for professor of any big university. Just one question - What tool do you use for visualization?
I did it myself, but thanks to NeetCode, I had no coding background, no degree, its been 4 months Ive started coding in Leetcode and unity ( a game engine ).
I learned a lot in this channel.
your leetcode id?
@@moulee007
Pramit Samanta
user5010fN
Ive just started and Im a civil engineer
why time complexity is n^2 ? we pass through every element once with options of choice (O(2N)) = O(N) no ?
You are the best, you always make problems easier than they really are. Kudos!!!!!
what a cool solution! Had fun watching1
Such an intuitive solution! Thanks!
I think just to optimize space, you don't have to create a new array, you can replace the existing array provided.
Best explanation on TH-cam, you make it seem so easy, thank you! :)
good solution for confusing problme
Brilliant Explanation ! Please keep making more videos like this . Thanks
why from the bottom to the top? why not from the top to bottom? thx~
After your explanation , this problem is butter
This solution is genius! Nice work.
Your visuals are unparalleled !!
One of my fav videos!
So, I have IQ of more than 90, yay!
In my opinion, this problem is the easiest of all medium Dynamic Programming problems on LC.
After 1 hour and a half of grinding, i solved it with a "Runtime: 88 ms, faster than 44.09% of Python3 online submissions for Triangle."(with dfs and memoization), i wouldn't have found it in an interview setting in a million years xD These pbs are tough...
best explanation ever! Thank you
I am always able to draw the decision tree for DP/recursive problems but am never able to convert it to code executable logic!!
You should practice more on implementation
@@techbarikcom yeah man you are right
Can you just start out with dp[] = last row and iterate from the second to last row up to the first?
why the time complexity is O(n) not O(n^2)?
one can do O(1) space if use triangle matrix itself for DP matrix.
no need for a bigger DP: we can just start from one-to-last row and move up
Thank you for such a clear explanation!
I solved this in
Time taken: 16 m 3 s
is it normal(easy) or i am in right track of learning
This might be my favorite DP problem
I definitely think it's underrated!
dp[i] = n + min(dp[i], dp[i+1]) is neet!
After updating dp[0], we don't need its value for the rest of updates till we are done with the current row. This is due to the shape of a triangle.
Update: You explained it already after the code :)
Can you comment a little on the input size?
C++ solution for the same question
class Solution {
public:
int minimumTotal(vector& nums) {
int n = nums.size();
int last = nums[n-1].size();
int ans=nums[0][0];
vectordp(last+1,0);
for(int i=n-1;i>=0;i--){
for(int j=0;j
I love your channel, and your videos
Top Down code for the idea described here, if anyone's interested :)
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
@cache
def dfs(i, j):
if i + 1 == len(triangle):
return triangle[i][j]
left = triangle[i][j] + dfs(i + 1, j)
right = triangle[i][j] + dfs(i + 1, j + 1)
return min(left, right)
return dfs(0, 0)
You made a mistake when explaining your intuition at 14:09, when you replaced 8 with 12, but should have been 7 i.e. (4 + min(8, 3)). Not something big but just telling FYI. Thanks for all the content
you are right
@@tiyaaaa3917 haha
You are a legend indeed!!!!!!!
Time complexity is O(n)
Why not to store dp actually in triangle row itself? You gonna reduce unnecessar space usage, this my solution (JAVA):
public int minimumTotal(List triangle) {
for (int row = triangle.size()-2; row >= 0; row--){
List currRow = triangle.get(row);
List prevRow = triangle.get(row+1);
for ( int i = 0; i < currRow.size(); i++){
currRow.set(i, currRow.get(i) + Math.min(prevRow.get(i), prevRow.get(i+1)));
}
}
return triangle.get(0).get(0);
}
I am new at dp, I somehow manage to write the code but have trouble with memoization, can anyone help with this code?
def total(i, row, count):
if i>=len(triangle[row]):
return float("inf")
count+=triangle[row][i]
if row==len(triangle)-1:
return count
return min(total(i, row+1, count), total(i+1, row+1, count))
return min(total(0, 1, count), total(1,1,count))
You are the best
謝謝！
I solved this problem before looking at this video so I'm glad my IQ of >= 90 is confirmed.
thank you that really helps
Glad it helped!
class Solution {
public:
int minimumTotal(vector& triangle) {
int n = triangle.size();
for(int i=n-2; i>=0; i--){
int m = triangle[i].size();
for(int j=0; j initially we have considered last row as leafs
it-0: trriangle[3] = [4, 1, 8, 3]
Now, start traversing triangle from 2nd last row to the top:
it-1: triangle[2] = [7, 6, 10]
it-2: triangle[1] = [9, 10]
it-3: triangle[0] = [11] // final iteration storing our result at triangle[0]
*/
wonderful!! Excellent preparation for SW dev interview!!
Just a word of advice, not include dynamic programming in the title or hash tag, it's kind of a spoiler for many viewers who are attempting to solve the question first before watching your videos.
INPLACE SOLUTION, YOU CAN CHOOSE NOT TO USE THE EXTRA TABLE IF WANT TO.
THANK YOU.
```
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle:
return 0
for row in range(len(triangle)-2, -1, -1):
for index, value in enumerate(triangle[row]):
triangle[row][index] = value + min(triangle[row+1][index], triangle[row+1][index+1])
return triangle[0][0]
```
Can someone tell me when tu enumerate and when not to?
Both works. Enumerating is just a shorter way to write code so you can:
1. Avoid writing range(len(array))
2. Avoid writing array[idx] to get the item at the current `idx` index
If you are not comfortable with enumerate yet just avoid it for now and use in range len. It does the exact same thing.
```python
# slightly shorter enumerate code
for idx, num in enumerate(array):
...
# this is equivalent to above for loop
for idx in range(len(array)):
num = array[idx]
...
```
WOW 🤩 now I am feeling like I have 130 IQ 😎
awesome
LOoks like I have IQ less than 90.
my IQ definitely below the 90
me watching this knowing that I have an IQ of float("-inf")
LET'S GO ANSWERED WITHOUT SOLUTION
Great video, nice clickbait haha How did you learn data structures and algorithms?
If someone(like me) wants to start from 1 row and go all the way to the last:
def min_path_sum(triangle):
dp = [float('inf')] * len(triangle[-1])
dp[0] = triangle[0][0]
for row in triangle[1:]:
for index, element in reversed(list(enumerate(row))):
if index != 0:
dp[index] = element + min(dp[index], dp[index-1])
else:
dp[index] = element + dp[0]
return min(dp)
This sounds like a tree with extra steps
Hahaha i have an iq of 136 ;) can solve this lolz
my iq 😥