BiruLyu
8/16/2017 - 4:48 PM

## 329. Longest Increasing Path in a Matrix(#1).java

``````// Topological Sort Based Solution
// An Alternative Solution
public class Solution {
private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;
public int longestIncreasingPath(int[][] grid) {
int m = grid.length;
if (m == 0) return 0;
int n = grid[0].length;
// padding the matrix with zero as boundaries
// assuming all positive integer, otherwise use INT_MIN as boundaries
int[][] matrix = new int[m + 2][n + 2];
for (int i = 0; i < m; ++i)
System.arraycopy(grid[i], 0, matrix[i + 1], 1, n);

// calculate outdegrees
int[][] outdegree = new int[m + 2][n + 2];
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
for (int[] d: dir)
if (matrix[i][j] < matrix[i + d[0]][j + d[1]])
outdegree[i][j]++;

// find leaves who have zero out degree as the initial level
n += 2;
m += 2;
List<int[]> leaves = new ArrayList<>();
for (int i = 1; i < m - 1; ++i)
for (int j = 1; j < n - 1; ++j)
if (outdegree[i][j] == 0) leaves.add(new int[]{i, j});

// remove leaves level by level in topological order
int height = 0;
while (!leaves.isEmpty()) {
height++;
List<int[]> newLeaves = new ArrayList<>();
for (int[] node : leaves) {
for (int[] d:dir) {
int x = node[0] + d[0], y = node[1] + d[1];
if (matrix[node[0]][node[1]] > matrix[x][y])
if (--outdegree[x][y] == 0)
}
}
leaves = newLeaves;
}
return height;
}
}``````
``````public class Solution {
private static final int[][] dirs = new int[][] {{0,1}, {1, 0}, {0, -1}, {-1, 0}};
private int dfs(int[][] matrix, int[][] dp, int r, int c) {
if (dp[r][c] != 0) return dp[r][c];
int m = matrix.length, n = matrix[0].length;
for (int[] d : dirs) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[r][c]) {
dp[r][c] = Math.max(dp[r][c], dfs(matrix, dp, x, y));
}
}
return ++dp[r][c];
}
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length < 1) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = Math.max(res, dfs(matrix, dp, i, j));
}
}
return res;
}
}``````
``````// Naive DFS Solution O(2^(m+n))
// Time Limit Exceeded

public class Solution {
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private int m, n;

public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
m = matrix.length;
n = matrix[0].length;
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(matrix, i, j));
return ans;
}

private int dfs(int[][] matrix, int i, int j) {
int ans = 0;
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
ans = Math.max(ans, dfs(matrix, x, y));
}
return ++ans;
}
}``````