329. Longest Increasing Path in a Matrix , Why it is hard??
Ref: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
INITIAL Thoughts: We can solve this problem using backtracking
We could look for each path which obeys strictly increasing property between numbers starting from each possible position in the Matrix. At each point, we have 4 directions(left, right, top, down) to walk through. We need to return the maximum (longest) length path among all the paths that go through 4 directions.
Though this solution would give the correct result in O(n³) complexity, it would result in time complexity exceeds error.
Hence we need to check where we can save time? If carefully seen, there are many times we are reaching a particular place in the matrix again and again when we are walking through paths initiated from different starting positions in the matrix. This means the paths further associated with those repeated positions will be traversed again and again and results in time-consumption.
Now that we know this is consuming time let’s save it ….. But how to avoid walking through the same path (or subpath) again and again? DPPPPPP(CACHING Trade-off between time and memory) if we already performed a traversal starting from the matrix(i,j) then at any time we come back to this position through a different positions let’s say(matrix[i][j-1]), we can actually skip the walkthrough (i,j) (or path through matrix[i,j]) by caching or storing the result during the first walk through this position. That is we can memorize the max length walks using a dp table dp[i][j].
Time complexity decrease down to O(n²).
To check out the code you can click the given link or check the gist:
Thanks for your time for any suggestions or query mail at nonathebarbie@gmail.com …. id is funny i know :D ;) .
