# 329.Longest-Increasing-Path-in-a-Matrix

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

## ้ข็ฎๆ่ฟฐ

``````Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:
Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:
Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.``````

## ไปฃ็ 

### Approach #1 DFS + Memoization

``````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[][] cache = new int[m][n];
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, cache));
}
}
return ans;
}

private int dfs(int[][] matrix, int i, int j, int[][] cache) {
if (cache[i][j] != 0)        return cache[i][j];
for (int[] d: dirs) {
int x = i + d[0];
int y = j + d[1];
if (x >= 0 && x < m
&& y >= 0 y < n
&& matrix[x][y] > matrix[i][j]) {

cache[i][j] = Math.max(cache[i][j], dfs(matrix, x, y, cache));
}
}

return ++cache[i][j];
}
}``````

### Approach #3 Peeling Onion Confusion

``````// 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)
newLeaves.add(new int[]{x, y});
}
}
leaves = newLeaves;
}
return height;
}
}``````

### Appraoch #3 TLE

``````// Naive DFS Solution
// 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;
}
}``````

Last updated