Longest Increasing Path in Matrix
You are given a 2-D grid of integers matrix, where each integer is greater than or equal to 0.
Return the length of the longest strictly increasing path within matrix.
From each cell within the path, you can move either horizontally or vertically. You may not move diagonally.
Example 1:
Input: matrix = [[5,5,3],[2,3,6],[1,1,1]]
Output: 4Explanation: The longest increasing path is [1, 2, 3, 6] or [1, 2, 3, 5].
Example 2:
Input: matrix = [[1,2,3],[2,1,4],[7,6,5]]
Output: 7Explanation: The longest increasing path is [1, 2, 3, 4, 5, 6, 7].
Constraints:
1 <= matrix.length, matrix[i].length <= 100
Recommended Time & Space Complexity
You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given matrix.
Hint 1
If we move from one cell to an adjacent cell with a greater value, we won't revisit a cell, as the path is strictly increasing. A brute force approach would be to run a dfs from every cell and return the longest path found. This approach is exponential. Can you think of a way to optimize it to avoid redundant calculations?
Hint 2
We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.