LeetCode Q329: Longest Increasing Path in a Matrix (hard)

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

It is not hard to think of DFS. But, its expensive to start a DFS for each entry. When thinking deeper, we notice that, we don't have to do DFS again at some entries if these entries have been accessed before with longest path already computed. To accelerate our computation, we can use memoization to save these information.

	class Solution {
	public:
	int DFS(int row, int col, vector<vector<int> >& matrix, vector<vector<int> >& steps){
	if(steps[row][col]!=0)
	return steps[row][col];
	int maxLen=INT_MIN;
	int dir[8] = {-1, 0, 1, 0, 0, -1, 0, 1};
	for(int i=0; i<4; i++){
	int r = row+dir[i*2];
	int c = col+dir[i*2+1];
	if(r<0||r>=matrix.size()||c<0||c>=matrix[0].size()||matrix[r][c]<=matrix[row][col])
	continue;
	maxLen = max(DFS(r, c, matrix, steps)+1, maxLen);
	}
	steps[row][col]=maxLen==INT_MIN? 1:maxLen;
	return steps[row][col];
	}
	int longestIncreasingPath(vector<vector<int>>& matrix) {
	if(matrix.empty())
	return 0;
	vector<vector<int> > steps(matrix.size(), vector<int>(matrix[0].size(), 0));
	int maxLen=INT_MIN;
	for(int i=0; i<matrix.size(); i++)
	for(int j=0; j<matrix[0].size(); j++)
	maxLen=max(maxLen, DFS(i, j, matrix, steps));
	return maxLen;
	}
	};

view raw Q329.cpp hosted with ❤ by GitHub