329. Longest Increasing Path in a Matrix
Description
Given an m x n
integers matrix
, return the length of the longest increasing path inmatrix
.
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].
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1
Tags
Depth-first Search, Topological Sort, Memoization
Solution
We build a 2D array dp
with the same size of matrix
to store the Longest Increasing Path starting from matrix[i][j]
, with all elements initialized with 1. We also need an 1D array of all elements in descending order. It allows us to find the longest path in decreasing way. Then we perform BFS for each elements of this 1D array, and update the longest path.
Complexity
Time complexity:
Space complexity:
Code
func longestIncreasingPath(matrix [][]int) int {
ans, elements := 1, make([][]int, 0, len(matrix)*len(matrix[0]))
for i, line := range matrix {
for j, v := range line {
elements = append(elements, []int{v, i, j})
}
}
sort.Slice(elements, func(i, j int) bool {
return elements[i][0] > elements[j][0]
})
dp, dirs := make([][]int, len(matrix)), [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for i := range dp {
dp[i] = make([]int, len(matrix[0]))
for j := range dp[i] {
dp[i][j] = 1
}
}
for _, e := range elements {
v, i, j := e[0], e[1], e[2]
for _, d := range dirs {
if x, y := i+d[0], j+d[1]; x >= 0 && y >= 0 && x < len(matrix) && y < len(matrix[0]) && matrix[x][y] > v && dp[i][j] < dp[x][y]+1 {
dp[i][j] = dp[x][y] + 1
}
}
if dp[i][j] > ans {
ans = dp[i][j]
}
}
return ans
}
Reference
Last updated
Was this helpful?