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.
Use 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 answer