## 329. 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.
``````

Thoughts:

1. DFS + memoization:
2. Topological sort: impose an directed edge a -> b if a < b. Then each time, delete the node with out degree zero, then the number of iteration is the result. (from post)

Code: DFS + Memoization: T:O(mn); S:O(mn)

``````class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0|| matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length, max = 0;
int dp [][]  = new int [m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
max = Math.max(max, dfs(matrix, m , n, i, j, dp));
}
}

return max;
}

private int dfs(int[][] matrix, int m, int n,int i, int j, int [][] dp){
if(dp[i][j] != 0) return dp[i][j]; // memoization
int cnt = 1;
int d[] = {0,1,0,-1,0};
for(int k = 0; k < 4; k++){
int x = i + d[k], y= j + d[k + 1];
if(x < 0 || x >= m || y < 0 || y>= n || matrix[i][j] >= matrix[x][y]) continue;
cnt = Math.max(cnt, dfs(matrix, m, n, x, y, dp) + 1);
}

dp[i][j] = cnt;
return cnt;
}
}
``````

Code: Python

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
def dfs(i,j):
if dp[i][j]: return dp[i][j]
cur = matrix[i][j]
dp[i][j] = 1 + max(dfs(i + 1, j) if i + 1 < m  and cur > matrix[i + 1][j] else 0,
dfs(i - 1, j) if i and cur > matrix[i - 1][j] else 0,
dfs(i, j + 1) if j + 1 < n and cur > matrix[i][j + 1] else 0,
dfs(i, j - 1) if j and cur > matrix[i][j - 1] else 0
)
return dp[i][j]

if not matrix or not matrix[0]: return 0
m,n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
return max(dfs(i,j) for j in range (n) for i in range(m))
``````

Code: Topological Sort O(mn * h), where h is the height of the order: (TLE)

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix or not matrix[0]: return 0

m, n = len(matrix), len(matrix[0])
count, res = m * n, 0

while count > 0:
s = set()
for i in range(m):
for j in range(n):
if matrix[i][j] == -sys.maxint-1: continue
up = (not i) or matrix[i][j] >= matrix[i - 1][j]
down = i + 1 == m or matrix[i][j] >= matrix[i + 1][j]
left = (not j) or matrix[i][j] >= matrix[i][j - 1]
right = j + 1 == n or matrix[i][j] >= matrix[i][j + 1]

if up and down and left and right: