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}