Longest Growing Path in a Matrix

About the problem:

Return the length of the longest growing path in a matrix of n x m integers.
You can travel in one of four directions from each cell: left, right, up, or down. You are not permitted to travel diagonally or outside the boundaries.

References

This problem is considered a common interview question asked in companies like Google and Facebook. Therefore, before getting started with solutions, I recommend you give it a try on Leetcode.

Example 1:
Input: [[6,8,9],[5,1,3],[7,6,4]]
Output: 5
Explanation: Longest growing path is 1 -> 5 -> 6 -> 8 -> 9

Example 2:
Input: [[8,3,7,9],[2,5,1,3]]
Output: 3
Explanation: Longest growing path is 1 -> 3 -> 9 or 3 -> 7 -> 9

Approach #1: DFS + DP

The simple recursive solution can be found here. We are simply iterating over the matrix and traversing in a DFS fashion for up, down, left, and right with some constraints from each index of the matrix. At every recursive call, make sure that the traversing indexes, i,j, are always within the length bound, and that the previous element was not greater than the current element. If that happens, we are just going to return 0 and not continue on that route.
We are saving the path or number of items covered in each call, and then just returning the maximum of them, i.e. the maximum count out of the four directions we’re permitted to move in.

Code:

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
35
36
37
38
39
40
41
42
43
44
45
int dp[201][201];
int dx[4] = {
  0,
  0,
  -1,
  1
};
int dy[4] = {
  1,
  -1,
  0,
  0
};

int solve(int r, int c, vector < vector < int >> & matrix) {
  if (dp[r][c] > 0) return dp[r][c];
  int curr = matrix[r][c];
  int m = 0;

  for (int i = 0; i < 4; i++) {
    int x = r + dx[i];
    int y = c + dy[i];
    if (x >= matrix.size() || y >= matrix[0].size() || x < 0 || y < 0 || matrix[x][y] <= matrix[r][c]) continue;

    m = max(m, solve(x, y, matrix));
  }

  return dp[r][c] = m + 1;
}

int longestGrowingPath(vector < vector < int >> & matrix) {
  if (matrix.size() == 0)
    return 0;
  int n = matrix.size(), m = matrix[0].size();

  int ans = 0;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      int inc = solve(i, j, matrix);
      ans = max(ans, inc);
    }

  return ans;
}

Time complexity: O(4mn) = O(mn), we are making four recursive calls for every index i,j of matrix.
Space complexity: O(mn), to store the dp array.

Approach #2: Topological sort

Conduct a standard topological sort of the graph, noting the maximum depth we can reach.
For topological sorting, we start with all vertices of 0 indegrees, visit them, and decrement their adjacent neighbor’s indegrees by 1. If any of them are now 0, add them to our queue.

Algorithm:

1. Increase the indegrees of the smaller values that are related to the larger value that is near the four directions.

2. Push the coordinates with indegree 0 into the queue,

3. By decreasing indegree values, you may explore these co-ordinariates and eliminate them from the graph.

4. Check if it touches 0 after decrementing them, and if it does, add it to the queue.

5. The ultimate solution will be determined by the depth of the bfs performed.

Code:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int indegree[201][201];
int dx[4] = {
  0,
  0,
  -1,
  1
};
int dy[4] = {
  1,
  -1,
  0,
  0
};

int longestGrowingPath(vector < vector < int >> & matrix) {
  if (matrix.size() == 0)
    return 0;

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

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      for (int d = 0; d < 4; d++) {
        int nx = i + dx[d];
        int ny = j + dy[d];

        if (nx >= 0 && ny >= 0 && nx < n && ny < m && matrix[nx][ny] > matrix[i][j])
          indegree[i][j]++;
      }

  queue < pair < int, int >> q;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (indegree[i][j] == 0)
        q.push({
          i,
          j
        });

  int ans = 0;
  while (!q.empty()) {

    int s = q.size();
    for (int i = 0; i < s; i++) {
      auto[a, b] = q.front();
      q.pop();
      for (int d = 0; d < 4; d++) {
        int nx = a + dx[d];
        int ny = b + dy[d];
        if (nx >= 0 && ny >= 0 && nx < n && ny < m)
          if (matrix[nx][ny] < matrix[a][b] && --indegree[nx][ny] == 0)
            q.push({
              nx,
              ny
            });
      }
    }
    ans++;
  }

  return ans;
}

Time complexity: O(4mn) = O(mn), we are tracing through the matrix at least once.
Space complexity: O(mn), to store the dp array.