# LeetCode: Longest Increasing Path In A Matrix Solution

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[][]} matrix3 * @return {number}4 */5var longestIncreasingPath = function (matrix) {6  const [M, N] = [matrix.length, matrix.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 >= N10
11  const recursion = (i, j, prevCell) => {12    if (outOfBound(i, j) || matrix[i][j] <= prevCell) {13      return 014    }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