Longest Increasing Path in a Matrix (DFS + Memoization)

🎧 Join the community Discord:   / discord  
💰 Support me on Patreon:   / michaelmuinos  
🔗Follow me on LinkedIn:   / michael-muinos  
📂Follow me on Github: https://github.com/MichaelMuinos

Check out my interview prep platform for learning the patterns!
📢 Interview Prep Platform: https://algoswithmichael.com

In this video, I go over the hard algorithm problem called "longest increasing path in a matrix" asked at many tech companies including Google, Facebook, Microsoft, Uber, and LinkedIn. This problem involves the knowledge of writing recursive algorithms, DFS implementation, and memoization usage. To solve this problem in the most efficient way, memoization is the key technique because we can cache previously computed recursive results. If we did not use memoization, then the approach would be a brute force algorithm.

We iterate over our input matrix and at each element we start the recursive algorithm to search all neighbors in the left, up, right, and down directions that are strictly greater than our current position. As we visit each element, we cache the result that we compute in order to not have to do it again at a later stage. By the end of iteration, we should have the longest path in the matrix.

The time and space complexity of our algorithm is O(N*M) where N is the number of rows and M is the number of columns. If we did not use memoization, the algorithm would be exponential since we would need to revisit many different paths in the matrix.