329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

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

Example 2:

Input: nums = 
[
  [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.

Solution

Approach 1: DP + backtracking -- memoized search on the grid.

Approach 2: alternatively, think of the grid as a DAG and find the longest path on the DAG.

Code (Python)

Approach 1:

class Solution:
    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
        # no need to consider path overlaps since it's always increasing
        if not matrix or not matrix[0]:
            return 0
        memory = {}
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                self._explore(row, col, matrix, memory)
        return max(memory.values())
    
    def _explore(self, row, col, matrix, memory):
        if (row, col) in memory:
            return memory[(row, col)]
        max_length = 0
        for delta in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            new_row, new_col = row + delta[0], col + delta[1]
            if 0 <= new_row < len(matrix) and 0 <= new_col < len(matrix[0]) and matrix[new_row][new_col] > matrix[row][col]:
                max_length = max(max_length, self._explore(new_row, new_col, matrix, memory))
        max_length = max_length + 1
        memory[(row, col)] = max_length
        return max_length

Code (C++)

Approach 1:

class Solution {
private:
    vector<vector<int>> pathLens;
    void doSearch(vector<vector<int>>& matrix, int row, int col) {
        if (pathLens[row][col] > 0)
            return;
        pathLens[row][col] = 1;
        int m = matrix.size();
        int n = matrix[0].size();
/*
        if (row > 0 && matrix[row][col] < matrix[row-1][col])
        {
            doSearch(matrix, row-1, col);
            pathLens[row][col] = std::max(pathLens[row][col], pathLens[row-1][col]+1);
        }
        if (row < m-1 && matrix[row][col] < matrix[row+1][col])
        {
            doSearch(matrix, row+1, col);
            pathLens[row][col] = std::max(pathLens[row][col], pathLens[row+1][col]+1);
        }
        if (col >0 && matrix[row][col] < matrix[row][col-1])
        {
            doSearch(matrix, row, col-1);
            pathLens[row][col] = std::max(pathLens[row][col], pathLens[row][col-1]+1);
        }
        if (col < n-1 && matrix[row][col] < matrix[row][col+1])
        {
            doSearch(matrix, row, col+1);
            pathLens[row][col] = std::max(pathLens[row][col], pathLens[row][col+1]+1);
        }
*/
        int rowNext[] = {-1, 1, 0, 0};
        int colNext[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; ++i)
        {
            int row2 = row + rowNext[i];
            int col2 = col + colNext[i];
            if (row2 >= 0 && row2 < m && col2 >= 0 && col2 < n &&
               matrix[row][col] < matrix[row2][col2])
            {
                doSearch(matrix, row2, col2);
                pathLens[row][col] = std::max(pathLens[row][col], pathLens[row2][col2]+1);
            }
        }
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        if (n == 0) return 0;
        pathLens = vector<vector<int>>(m, vector<int>(n, 0));
        int maxPathLen = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                doSearch(matrix, i, j);
                maxPathLen = std::max(maxPathLen, pathLens[i][j]);
            }
        }
        return maxPathLen;
    }
};