Longest Increasing Path in a Matrix

---

Longest Increasing Path in a Matrix: 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] <= 2^31 - 1

---

Try this Problem on your own or check similar problems:

1. Number of Increasing Paths in a Grid

Solution:

Java

class Solution {
    int[][] directions  = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxLength = 1;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                maxLength = Math.max(maxLength, dfs(matrix, i, j, dp));
            }
        }
        return maxLength;
    }

    public int dfs(int[][] matrix, int row, int col, int[][] dp){
        if(dp[row][col] != 0) return dp[row][col];

        int maxLength = 1;

        for(int[] d: directions){
          int newRow = row + d[0];
          int newCol = col + d[1];
          if(newRow < 0 || newRow >= matrix.length || newCol < 0 || newCol >= matrix[0].length || matrix[newRow][newCol] <= matrix[row][col]) continue;
          maxLength = Math.max(maxLength, 1 + dfs(matrix, newRow, newCol, dp));
        }

        dp[row][col] = maxLength;
        return maxLength;
    }
}

JavaScript

/**
 * @param {number[][]} matrix
 * @return {number}
 */

const directions = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];

var longestIncreasingPath = function (matrix) {
  if (!matrix.length || !matrix[0].length) return 0;
  const m = matrix.length;
  const n = matrix[0].length;
  const dp = Array.from(Array(m), () => Array(n).fill(0));
  let maxLength = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      maxLength = Math.max(maxLength, dfs(matrix, i, j, dp));
    }
  }
  return maxLength;
};

function dfs(matrix, row, col, dp) {
  if (dp[row][col] !== 0) return dp[row][col];
  let maxLength = 1;
  for (const [dx, dy] of directions) {
    const newRow = row + dx;
    const newCol = col + dy;
    if (
      newRow < 0 ||
      newRow >= matrix.length ||
      newCol < 0 ||
      newCol >= matrix[0].length ||
      matrix[newRow][newCol] <= matrix[row][col]
    ) {
      continue;
    }
    maxLength = Math.max(maxLength, 1 + dfs(matrix, newRow, newCol, dp));
  }
  dp[row][col] = maxLength;
  return maxLength;
}

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        max_length = 1
        for i in range(m):
            for j in range(n):
                max_length = max(max_length, self.dfs(matrix, i, j, dp, directions))
        return max_length

    def dfs(self, matrix, row, col, dp, directions):
        if dp[row][col] != 0:
            return dp[row][col]
        max_length = 1
        for d in directions:
            new_row = row + d[0]
            new_col = col + d[1]
            if new_row < 0 or new_row >= len(matrix) or new_col < 0 or new_col >= len(matrix[0]) or matrix[new_row][new_col] <= matrix[row][col]:
                continue
            max_length = max(max_length, 1 + self.dfs(matrix, new_row, new_col, dp, directions))
        dp[row][col] = max_length
        return max_length

C++

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
         if (matrix.empty())
            return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        vector<vector<int>> directions{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int max_length = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                max_length = max(max_length, dfs(matrix, i, j, dp, directions));
            }
        }
        return max_length;
    }

private:
    int dfs(vector<vector<int>>& matrix, int row, int col, vector<vector<int>>& dp, vector<vector<int>>& directions) {
        if (dp[row][col] != 0)
            return dp[row][col];
        int max_length = 1;
        for (const auto& d : directions) {
            int new_row = row + d[0];
            int new_col = col + d[1];
            if (new_row < 0 || new_row >= matrix.size() || new_col < 0 || new_col >= matrix[0].size() || matrix[new_row][new_col] <= matrix[row][col])
                continue;
            max_length = max(max_length, 1 + dfs(matrix, new_row, new_col, dp, directions));
        }
        dp[row][col] = max_length;
        return max_length;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

We have a classic depth first search, so our time complexity is O(mn), we also store the max length for each of the cell leading to the same space complexity. From each cell we run a DFS search and check if we can increase the maximum length. We use directions array to search for neighboring matrix cells and only continue our search from the cells leading to increasing sequence. We also store the max length found for the cell in dp since we could revisit the cell in searches from other cells, so we're preventing an infinitive loop by returning early if(dp[row][col] != 0) return dp[row][col];. Why don't we have a visited array to mark the cells visited so we don't end up with a cycle coming back to the initial cell we began our search from? Note that we're only continuing our search if the next cell is larger than the previous, so we can't go back to the initial cell, since the path is strictly increasing (for example we can't have 1->2->1 since we will never go to 1 from 2 because 1 < 2). Time and space complexity are O(mn) since we visit all elements in the matrix, while for space we have additional data structure holding maximum lengh for each element in the matrix.