Back to DSA
Longest Increasing Path in a Matrix
hardGiven an m-by-n grid of integers, find the length of the longest path of strictly increasing values. From any cell, you may step to any of the four cardinal neighbors (up, down, left, right), but not diagonally and not outside the grid.
Examples
Example 1:
Input:
matrix = [[1,2,3],[6,5,4],[7,8,9]]Output:
9Explanation: The path 1->2->3->4->5->6->7->8->9 visits every cell in increasing order.
Example 2:
Input:
matrix = [[3,2,1],[4,5,6]]Output:
6Explanation: The path 1->2->3->4->5->6 covers all cells.
Hints
class Solution {
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] memo = new int[m][n];
int result = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
result = Math.max(result, dfs(matrix, memo, i, j));
return result;
}
private int dfs(int[][] matrix, int[][] memo, int i, int j) {
if (memo[i][j] != 0) return memo[i][j];
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int max = 1;
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < matrix.length && nj >= 0 && nj < matrix[0].length && matrix[ni][nj] > matrix[i][j]) {
max = Math.max(max, 1 + dfs(matrix, memo, ni, nj));
}
}
memo[i][j] = max;
return max;
}
}Time complexity
O(m * n)Space complexity
O(m * n)