Google Coding Interview Tutorial - Longest Increasing Path in a Matrix [LeetCode 329]

In this video I explain the solution of a common coding interview question “Longest Increasing Path in a Matrix” [LeetCode 329].
You can find it here - leetcode.com/p...
If there is a coding interview problem you would like me to cover, let me know in the comments.

[@jlecampana]

This is Fantastic, you're the Wonder Girl for LeetCode explanations! I was wondering if the caching itself is the reason Why Leetcode calls this one a DP problem.

[@ShiranAfergan]

Thanks :) It’s marked as dynamic programming because it’s possible to solve it with dynamic programming, it’s just more complicated. I say a few sentences about that starting at timestamp 3:41

[@abhimanyuambastha2595]

@@ShiranAfergan I love your explanations, but I am saddened that you have so little. Any plans to resume posting more hard problems? There are a lot of videos on mainstream and easy/medium problems, but your intuition on hard problems are fantastic. Especially liked your approach from brute-better-optimal in the Min Cost to hire K workers Video. It has been my reference on how to approach an unknown problem and optimize. Hopefully you can resume your videos someday

[@444not]

Very good explanation. I watched 5 videos before stumbling on this one. Your explanation is very clear and easy to understand.

[@ShiranAfergan]

Thanks! I’m glad it helped :)

[@dnitdgp]

wow! very nice explanation.

[@user-rw6wl5qx3r]

I really liked your coding of this problem! Thanks a lot!

[@mehmetfrataksoy4009]

Thank you for having the best explanation possible for this question. Respects from Turkey

[@ShiranAfergan]

Thank you! I’m glad you liked it :)

[@uptonogood300]

wow! such crystal clear explanation.
initially i thought of some backtracking soln but this is simpler, thanks

[@ShiranAfergan]

Thanks 😊 I’m glad it helped

[@sidforreal]

Clean explanation!!

[@iamparitosh]

This is the problem I tried after 3 months gap and I literally feel bad for not able to devise the solution to the problems I used to be really good at :/
By the way, your explanation was really to the point,

[@lakshaysharma8144]

Great explanation

[@karthikshetty2875]

Nicely Explained! Thanks a lot!

[@janedoe2763]

Thanks for making this very easy to understand!

[@ShiranAfergan]

You’re welcome:) I’m glad it helped.

[@rishibansal8722]

Nice explanation. If coding part is bit slow and more explained that will be better.

[@ShiranAfergan]

Thanks for the feedback! :)

[@prasannapm3220]

thank you maam

[@sushantsingh5689]

Nice explanation !
I have a qn ..why can't we do this problem with tabular DP w/o using recursion and memorization ??

[@ShiranAfergan]

That’s a good question! You can do it, but it will be more complex. You would have to perform topological sorting first to get the order of dependencies (We need to know which cells have no valid increasing directions so we can start there and move backwards)

[@tejassrivastava6971]

Can we do this using modified dijkstra...putting every element in minheap and then start by selecting smallest ones?

[@blaaarp4u]

in other words you did a DFS.

[@amanjain9958]

Can you please share which app you are using for drawing. Btw great explanation, subscribed.☺️

[@ShiranAfergan]

Sure :) it’s GootNotes

[@Suryabasettydustin]

Can we solve it using graphs also right? We can take each possible edge with weight 1 and find all possible Source Destination and get maximum?

[@ShiranAfergan]

Good start. Now think of how you would construct this graph. The adjacency list for each node will contain its 4 neighbors. Do we need to create this graph or do we have this information in the matrix already? In the DFS traversal, instead of iterating the adjacency list, you can iterate the 4 directions in the matrix. You will end up with the same solution :)

[@tejas5331]

You sound so Cool....