329. Longest Increasing Path in a Matrix

Posted on Edited on In

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:

1
2
3
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:

1
2
3
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:

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

Constraints:

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

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    static constexpr int DIRs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    vector<vector<int>> steps;
    int m, n;

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        steps.resize(m, vector<int>(n, -1));
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = max(res, dfs(i, j, matrix));
            }
        }
        return res;
    }

    int dfs(int i, int j, vector<vector<int>>& matrix) {
        if (steps[i][j] != -1) {
            return steps[i][j];
        }
        int& val = steps[i][j];
        val = 1;
        for (int k = 0; k < 4; k++) {
            int dx = i + DIRs[k][0], dy = j + DIRs[k][1];
            if (dx >= 0 && dx < m && dy >= 0 && dy < n && matrix[dx][dy] < matrix[i][j]) {
                    steps[i][j] = max(steps[i][j], dfs(dx, dy, matrix) + 1);
            }
        }
        return val;
    }
};