329. Longest Increasing Path in a Matrix

Description

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

 

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

Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

Input: matrix = [[1]]
Output: 1

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

 

Solutions

Solution: Depth-First Search + Memoization

• Time complexity: O(mn)
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} matrix
 * @return {number}
 */
const longestIncreasingPath = function (matrix) {
  const MIN_VALUE = Number.MIN_SAFE_INTEGER;
  const m = matrix.length;
  const n = matrix[0].length;
  const dp = new Array(m)
    .fill('')
    .map(_ => new Array(n).fill(MIN_VALUE));
  const dfsPath = (row, col, previous = MIN_VALUE, step = 0) => {
    if (row < 0 || col < 0 || row >= m || col >= n) return step;
    const value = matrix[row][col];

    if (previous >= value) return step;
    if (dp[row][col] > MIN_VALUE) return dp[row][col] + step;
    const left = dfsPath(row, col - 1, value, step + 1);
    const right = dfsPath(row, col + 1, value, step + 1);
    const up = dfsPath(row - 1, col, value, step + 1);
    const down = dfsPath(row + 1, col, value, step + 1);
    const maxStep = Math.max(left, right, up, down);

    dp[row][col] = maxStep - step;
    return maxStep;
  };
  let result = 0;

  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      const step = dfsPath(row, col);

      result = Math.max(step, result);
    }
  }
  return result;
};