Longest Increasing Path in a Matrix LeetCode solution in C++

1
class Solution {
2
 public:
3
  // declare a dp
4

5
  int dp[205][205];
6

7
  // direction coordinates of left, right, up, down
8

9
  vector<int> dx = {-1, 0, 1, 0};
10

11
  vector<int> dy = {0, 1, 0, -1};
12

13
  // dfs function
14

15
  int dfs(vector<vector<int>> &matrix, int i, int j, int n, int m) {
16
    // if value is already calculated for (i, j)th cell
17

18
    if (dp[i][j] != -1) return dp[i][j];
19

20
    // take the maximum of longest increasing path from all four directions
21

22
    int maxi = 0;
23

24
    for (int k = 0; k < 4; k++) {
25
      int new_i = i + dx[k];
26

27
      int new_j = j + dy[k];
28

29
      if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < m &&
30
          matrix[new_i][new_j] > matrix[i][j]) {
31
        maxi = max(maxi, dfs(matrix, new_i, new_j, n, m));
32
      }
33
    }
34

35
    // store the res and return it
36

37
    return dp[i][j] = 1 + maxi;
38
  }
39

40
  int longestIncreasingPath(vector<vector<int>> &matrix) {
41
    int n = matrix.size();
42

43
    int m = matrix[0].size();
44

45
    // initialize dp with -1
46

47
    memset(dp, -1, sizeof(dp));
48

49
    // find the longest increasing path for each cell and take maximum of it
50

51
    int maxi = INT_MIN;
52

53
    for (int i = 0; i < n; i++) {
54
      for (int j = 0; j < m; j++) {
55
        int ans = dfs(matrix, i, j, n, m);
56

57
        maxi = max(maxi, ans);
58
      }
59
    }
60

61
    return maxi;
62
  }
63
};