329. Longest Increasing Path in a Matrix

• Difficulty: Hard

• Topics: Depth-first Search, Topological Sort, Memoization

• Similar Questions:

Problem:

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.

Solutions:

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        unordered_map<int, int> memory;
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        if (n == 0) return 0;

        int ret = 0;

        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                ret = max(ret, dfs(matrix, m, n, row, col, memory));
            }
        }

        return ret;
    }

    int dfs(const vector<vector<int>>&matrix, int m , int n, int row, int col, unordered_map<int, int>& memory) {
        int coord = n * row + col;
        if (memory.count(coord) > 0) {
            return memory[coord];
        } else {
            int maxPathLen = 1;
            for (int d = 0; d < 4; ++d) {
                int nextRow = row + directions[d][0];
                int nextCol = col + directions[d][1];
                if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n)  continue;
                if (matrix[nextRow][nextCol] <= matrix[row][col]) continue;
                maxPathLen = max(maxPathLen, 1 + dfs(matrix, m, n, nextRow, nextCol, memory));
            }
            memory[coord] = maxPathLen;
            return maxPathLen;
        }
    }
private:
    int directions[4][2] = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

};