# LeetCode: Longest Increasing Path In A Matrix Solution

1/**
2 * @param {number[][]} matrix
3 * @return {number}
4 */
5var longestIncreasingPath = function (matrix) {
6 const [M, N] = [matrix.length, matrix[0].length]
7 let memo = Array.from({ length: M }, _ => Array(N).fill(null))
8
9 const outOfBound = (i, j) => i < 0 || i >= M || j < 0 || j >= N
10
11 const recursion = (i, j, prevCell) => {
12 if (outOfBound(i, j) || matrix[i][j] <= prevCell) {
13 return 0
14 }
15
16 if (memo[i][j] !== null) {
17 return memo[i][j]
18 }
19
20 const path =
21 1 +
22 Math.max(
23 recursion(i + 1, j, matrix[i][j]),
24 recursion(i - 1, j, matrix[i][j]),
25 recursion(i, j + 1, matrix[i][j]),
26 recursion(i, j - 1, matrix[i][j])
27 )
28
29 return (memo[i][j] = path)
30 }
31
32 for (let i = 0; i < M; i++) {
33 for (let j = 0; j < N; j++) {
34 recursion(i, j, -Infinity)
35 }
36 }
37
38 return Math.max.apply(null, memo.flat())
39}

## Tags

leetcode

dynamic programming

dfs

topological sort

## Next Post

CodeWars: Dont Rely On Luck

Apr 10, 2021

Search Posts