Proficient Level
Implement the longestIncreasingPathMatrix method that returns the longest strictly increasing path length in a matrix.
You are given a matrix of integers. From any cell, you may move up, down, left, or right to a neighboring cell with a strictly larger value.
Return the length of the longest path that can be formed. Diagonal movement is not allowed.
Example 1
Input
matrix (int[][]) =
[[9,9,4],[6,6,8],[2,1,1]]rows (int) =
3cols (int) =
3Returns (int)
4Example 2
Input
matrix (int[][]) =
[[3,4,5],[3,2,6],[2,2,1]]rows (int) =
3cols (int) =
3Returns (int)
4Example 3
Input
matrix (int[][]) =
[[1]]rows (int) =
1cols (int) =
1Returns (int)
1Use depth-first search with memoization.
For each cell, compute the longest increasing path starting from that cell. If the result for a cell has already been calculated, reuse it. From the current cell, try all four neighbors that have a larger value and keep the best path length.
The final answer is the maximum memoized value over all cells.
Pseudocode:
function longestIncreasingPathMatrix(matrix, rows, cols):
memo = rows by cols table filled with 0
function dfs(r, c):
if memo[r][c] != 0:
return memo[r][c]
best = 1
for each direction:
nr = r + direction.row
nc = c + direction.col
if inside matrix and matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
memo[r][c] = best
return best
answer = 0
for each cell:
answer = max(answer, dfs(cell))
return answerReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run