Solution
Approach 1: DFS + memoization
The approach is pretty straightforward and we just have to perform DFS on the matrix starting from each cell. The trick is to also do memoization because we visit the same position in the matrix a lot of times. Without memoization the judge will give TLE. Algorithm:
- Do DFS from every cell
- Compare every 4 direction and skip cells that are out of boundary or smaller
- Get matrix max from every cell’s max
- The key is to cache the distance because it’s highly possible to revisit a cell (memoization)
C++ implementation:
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
// sanity check
if (matrix.size() == 0)
return 0;
vector<vector<int>> memo(matrix.size(), vector<int>(matrix[0].size(), 0));
int ans = 1;
for (int i=0; i<matrix.size(); i++)
for (int j=0; j<matrix[0].size(); j++)
ans = max(ans, helper(matrix, memo, i, j, INT_MIN));
return ans;
}
int helper (vector<vector<int>>& matrix, vector<vector<int>>& memo, int i, int j, int prev) {
if (i<0 || j<0 || i>=matrix.size() || j>=matrix[0].size() || prev>=matrix[i][j])
return 0;
if (memo[i][j] != 0)
return memo[i][j];
int maxPath = 1;
maxPath = max(maxPath, helper(matrix, memo, i+1, j, matrix[i][j])+1);
maxPath = max(maxPath, helper(matrix, memo, i-1, j, matrix[i][j])+1);
maxPath = max(maxPath, helper(matrix, memo, i, j+1, matrix[i][j])+1);
maxPath = max(maxPath, helper(matrix, memo, i, j-1, matrix[i][j])+1);
memo[i][j] = maxPath;
return maxPath;
}
};
Approach 2: Max Heap + DP
This approach was pointed out by han_xuan and I found it pretty interesting! This is a very non-standard way of solving this question.
Say we sort all the numbers in the matrix is descending order and then start picking the numbers. The first number we pick will be the largest so its longest increasing path length = 1. If we pick a number at index i, assuming we have longest increasing path lengths for all index 0..i-1, the increasing path length for this number will be equal to 1 + maximum increasing path length of its neighbors. Notice that if the neighbor > number at i, we have already found its longest increasing path length as it would have an index < i (array sorted in descending order). Let’s translate this idea into priority queues and DP:
- For all cells in the matrix, store in a max priority queue {row, column, value of cell}
- Until priority queue is empty, do: a. Get the top of the queue and pop it b. For all neighbors of that element, set dp[i][j] = max(dp[i][j], 1+dp[neighbor_row][neighbor_col]) where i and j are the row and col of the element popped from queue
- Max length will be the maximum value present in dp matrix
private static int[][] dir = new int[][]{ {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
private int maxLen = 0;
public int longestIncreasingPath(int[][] matrix) {
// Algo thinking: reverse thinking
// (1) Use a maxPQ
// (2) DP
// time = O(N*M*lg(N*M)), space = O(N*M)
if (matrix == null || matrix.length == 0) return 0;
int n = matrix.length;
int m = matrix[0].length;
PriorityQueue<int[]> maxPQ = new PriorityQueue<>((a, b) -> b[2] - a[2]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
maxPQ.offer(new int[]{i, j, matrix[i][j]});
}
}
int[][] dp = new int[n][m];
while (!maxPQ.isEmpty()) {
int[] cell = maxPQ.poll();
int i = cell[0], j = cell[1];
dp[i][j] = 1;
for (int[] d: dir) {
int newI = i + d[0], newJ = j + d[1];
if (newI < 0 || newI >= n || newJ < 0 || newJ >= m || matrix[i][j] >= matrix[newI][newJ]) continue;
dp[i][j] = Math.max(dp[i][j], dp[newI][newJ] + 1);
}
maxLen = Math.max(maxLen, dp[i][j]);
}
return maxLen;
}
Time complexity: O(NMlg(NM))
Space complexity: O(NM)