[Algorithm] Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix

Problem Statement:

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:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution: Topological Sort + DP

The key to solving this problem is that we can view the matrix as a directed graph, each point in the matrix is a vertex and edge only exists among neighboring points when two point has increasing order the direction is from the smaller to the larger number (eg. matrix[i][j] -> matrix[i][j-1], if matrix[i][j] < matrix[i][j-1]). Topological sort can help us group the paths in this graph. And we can compare the length of different paths originated from each individual points in the matrix.

For example, in the following matrix, we could have multiple paths originating from "4" and we can find them by performing topological sort.

Another thing to notice is that we can update the start of previous found sequence as we pick another unvisited point as the starting point for another topological sort. Thus concatenating the sequence. For example, when we start with "4" we can find a sequence of "4->5->6->7->8->9->10" and when we start from "3" which is not visited the sequence "3" can be concatenated to "3->4->5->6->7->8->9->10" because there exists an edge "3->4".

Since our target is to find out the longest sequence, the DP concept comes into play. We know that we can concatenate topological order to form longer sequence, we just need to keep track of the longest sequence starting from each point in the matrix and we can also use this DP matrix as "visited" flag for all the points.

Code implementation:

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

class Solution { public: int longestIncreasingPath(vector<vector<int>>& matrix) { int n = matrix.size(); if (n == 0) return 0; int m = matrix[0].size(); if (m == 0) return 0; vector<vector<int> > topo(n, vector<int>(m, -1)); int maxLen = INT_MIN; for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (topo[i][j] == -1) { dfs(matrix, i, j, topo); } maxLen = max(maxLen, topo[i][j]); } } return maxLen; } void dfs(const vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& topo) { topo[i][j] = 1; /* visting neighbor */ if (i-1>=0 && matrix[i][j] < matrix[i-1][j]) { if (topo[i-1][j] == -1) { dfs(matrix, i-1, j, topo); } topo[i][j] = max(topo[i][j], topo[i-1][j]+1); } if (i+1<matrix.size() && matrix[i][j] < matrix[i+1][j]) { if (topo[i+1][j] == -1) { dfs(matrix, i+1, j, topo); } topo[i][j] = max(topo[i][j], topo[i+1][j]+1); } if (j-1>=0 && matrix[i][j] < matrix[i][j-1]) { if (topo[i][j-1] == -1) { dfs(matrix, i, j-1, topo); } topo[i][j] = max(topo[i][j], topo[i][j-1]+1); } if (j+1<matrix[0].size() && matrix[i][j] < matrix[i][j+1]) { if (topo[i][j+1] == -1) { dfs(matrix, i, j+1, topo); } topo[i][j] = max(topo[i][j], topo[i][j+1]+1); } } };