🤖 leetcode 329. Longest Increasing Path in a Matrix | hard | graph | javascript

🗒️ Problem

Longest Increasing Path in a Matrix - LeetCode

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).

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

🍀 Intuition

💡 use cache

• While traversing the graph, it is necessary to find each increasing path while searching with DFS at all points, so if you just do it, TLE will occur.
• top level recursion with memoization is needed.

💡 recursive DFS traversal

• In BFS, traverse often checks the condition beforehand and traverses it if it is true.
• In DFS, there are many cases in which after traversing, the condition is checked in the node and returned if it is invalid.

💡 how to return value in recursive DFS

• How to update and return response in recursive DFS.

const dfs = (r, c, parent) => {
    ...
  let localMax = -Infinity

  for (const [dR, dC] of directions) {
    const newR = r + dR
    const newC = c + dC

    localMax = Math.max(localMax, 1 + dfs(newR, newC, matrix[r][c]))
  }

  return localMax
}

💡 How to manage visited nodes

• In the graph traverse, visited management is inevitable.
• But, this time it is a process of finding an increasing path, so it doesn't visit the previous smaller node back agin.
• No need to manage the visited nodes.

🔥♻️ My Solution

var longestIncreasingPath = function (matrix) {
  const [ROWS, COLS] = [matrix.length, matrix[0].length];

  let max = -Infinity;
  const cache = new Map();

  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];
  const isValid = (r, c) => !(r < 0 || r >= ROWS || c < 0 || c >= COLS);
  const genKey = (r, c) => `${r}:${c}`;

  const dfs = (r, c, parent) => {
    if (!isValid(r, c)) return 0;
    if (parent >= matrix[r][c]) return 0;
    if (cache.has(genKey(r, c))) return cache.get(genKey(r, c));

    let localMax = -Infinity;

    for (const [dR, dC] of directions) {
      const newR = r + dR;
      const newC = c + dC;

      localMax = Math.max(localMax, 1 + dfs(newR, newC, matrix[r][c]));
    }

    cache.set(genKey(r, c), localMax);
    return localMax;
  };

  for (let r = 0; r < ROWS; r += 1) {
    for (let c = 0; c < COLS; c += 1) {
      max = Math.max(max, dfs(r, c, -Infinity));
    }
  }

  return max;
};