Algorithm
Problem Name: 329. Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: matrix = [[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.
Example 3:
Input: matrix = [[1]] Output: 1
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define IDX(I, J, L) ((I) * (L) + (J))
int depth(int **matrix, int rowsz, int colsz, int *dep, int row, int col) {
int s, x, z, y;
int d = 0;
d = dep[IDX(row, col, colsz)];
if (d) {
return d;
}
if (row == 0 || matrix[row][col] < = matrix[row - 1][col]) {
s = 1;
} else {
s = depth(matrix, rowsz, colsz, dep, row - 1, col) + 1;
}
if (row == rowsz - 1 || matrix[row][col] < = matrix[row + 1][col]) {
x = 1;
} else {
x = depth(matrix, rowsz, colsz, dep, row + 1, col) + 1;
}
if (col == 0 || matrix[row][col] < = matrix[row][col - 1]) {
z = 1;
} else {
z = depth(matrix, rowsz, colsz, dep, row, col - 1) + 1;
}
if (col == colsz - 1 || matrix[row][col] < = matrix[row][col + 1]) {
y = 1;
} else {
y = depth(matrix, rowsz, colsz, dep, row, col + 1) + 1;
}
d = s;
d = d > x ? d : x;
d = d > z ? d : z;
d = d > y ? d : y;
dep[IDX(row, col, colsz)] = d;
return d;
}
int longestIncreasingPath(int** matrix, int matrixRowSize, int matrixColSize) {
int i, j;
int *dep;
int d, max = 0;
if (matrixRowSize < = 0 || matrixColSize <= 0) return 0;
dep = calloc(matrixRowSize * matrixColSize, sizeof(int));
//assert(dep);
for (i = 0; i < matrixRowSize; i ++) {
for (j = 0; j < matrixColSize; j ++) {
d = depth(matrix, matrixRowSize, matrixColSize, dep, i, j);
max = max < d ? d : max;
}
}
free(dep);
return max;
}
Input
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output
4
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int m = matrix.size() , n = matrix[0].size();
vector<vector < int>>dp(m, vector<int>(n));
vector < vector<int>>visited(m, vector<int>(n));
int maxlen = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
maxlen = max(maxlen, DFS(matrix, visited, dp, i, j, m, n));
return maxlen;
}
int DFS(vector < vector<int>>& matrix, vector < vector<int>>& visited, vector < vector<int>>& dp, int r, int c, int m, int n){
if(visited[r][c]) return 0;
if(dp[r][c]) return dp[r][c];
visited[r][c] = 1;
int up(1), down(1), left(1), right(1>;
if(r - 1 >= 0 && matrix[r - 1][c] > matrix[r][c]) up = DFS(matrix, visited, dp, r - 1, c, m, n) + 1;
if(r + 1 < m && matrix[r + 1][c] > matrix[r][c]) down = DFS(matrix, visited, dp, r + 1, c, m, n) + 1;
if(c - 1 >= 0 && matrix[r][c - 1] > matrix[r][c]) left = DFS(matrix, visited, dp, r, c - 1, m, n) + 1;
if(c + 1 < n && matrix[r][c + 1] > matrix[r][c]) right = DFS(matrix, visited, dp, r, c + 1, m, n) + 1;
visited[r][c] = 0;
dp[r][c] = max(up, max(down, max(left, right)));
return dp[r][c];
}
};
Input
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output
4
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
private final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public int longestIncreasingPath(int[][] matrix) {
int numRows = matrix.length;
int numCols = matrix[0].length;
int maxPathLength = 0;
int[][] cache = new int[numRows][numCols];
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
maxPathLength = Math.max(maxPathLength, helper(matrix, numRows, numCols, i, j, cache));
}
}
return maxPathLength;
}
private int helper(int[][] matrix, int numRows, int numCols, int i, int j, int[][] cache) {
if (cache[i][j] != 0) {
return cache[i][j];
}
for (int[] dir : DIRS) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && y >= 0 && x < numRows && y < numCols && matrix[x][y] > matrix[i][j]) {
cache[i][j] = Math.max(cache[i][j], helper(matrix, numRows, numCols, x, y, cache));
}
}
return ++cache[i][j];
}
}
Input
matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output
4
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const longestIncreasingPath = function(matrix) {
const m = matrix.length, n = matrix[0].length
let res = 1
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const memo = Array.from({ length: m }, () => Array(n).fill(0))
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
const len = dfs(i, j)
res = Math.max(res, len)
}
}
return res
function dfs(i, j) {
const v = matrix[i][j]
if(memo[i][j] !== 0) return memo[i][j]
let len = 1
for(const [dx, dy] of dirs) {
const nx = i + dx, ny = j + dy
if(nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > v) {
const tmp = 1 + dfs(nx, ny)
len = Math.max(len, tmp)
}
}
memo[i][j] = len
return len
}
};
Input
matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output
4
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestIncreasingPath(self, matrix):
def dfs(i, j):
if not dp[i][j]:
dp[i][j] = 1+max((dfs(x,y) for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)) if 0 <=x matrix[i][j]),default=0)
return dp[i][j]
m, n, = len(matrix), len(matrix and matrix[0])
dp = [[0] * n for _ in range(m)]
return max((dfs(i,j) for i in range(m) for j in range(n)),default=0)
Input
matrix = [[1]]
Output
1
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0329_LongestIncreasingPathInAMatrix
{
private readonly static int[][] dirs = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
public int LongestIncreasingPath(int[][] matrix)
{
if (matrix.Length == 0) return 0;
int M = matrix.Length, N = matrix[0].Length;
var cache = new int[M, N];
var maxValue = 0;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
maxValue = Math.Max(maxValue, DFS(cache, matrix, M, N, i, j));
return maxValue + 1;
}
private int DFS(int[,] cache, int[][] matrix, int M, int N, int i, int j)
{
if (cache[i, j] != 0) return cache[i, j];
foreach (var dir in dirs)
{
int x = i + dir[0], y = j + dir[1];
if (0 < = x && x < M && 0 <= y && y < N)
if (matrix[x][y] > matrix[i][j])
cache[i, j] = Math.Max(cache[i, j], DFS(cache, matrix, M, N, x, y) + 1);
}
return cache[i, j];
}
}
}
Input
matrix = [[1]]
Output
1