15ms Concise Java Solution


  • 144

    To get max length of increasing sequences:

    1. Do DFS from every cell
    2. Compare every 4 direction and skip cells that are out of boundary or smaller
    3. Get matrix max from every cell's max
    4. Use matrix[x][y] <= matrix[i][j] so we don't need a visited[m][n] array
    5. The key is to cache the distance because it's highly possible to revisit a cell

    Hope it helps!

    public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];
        int max = 1;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int len = dfs(matrix, i, j, m, n, cache);
                max = Math.max(max, len);
            }
        }   
        return max;
    }
    
    public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) {
        if(cache[i][j] != 0) return cache[i][j];
        int max = 1;
        for(int[] dir: dirs) {
            int x = i + dir[0], y = j + dir[1];
            if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
            int len = 1 + dfs(matrix, x, y, m, n, cache);
            max = Math.max(max, len);
        }
        cache[i][j] = max;
        return max;
    }

  • 0
    G

    Hello! yavinci. My version is C++,I do not know why my runtime is 84ms.

    int longestIncreasingPath(vector<vector<int>>& matrix) {
    int rows=matrix.size();
    if(rows==0) return 0;
    int cols=matrix[0].size();
    if(cols==0) return 0;
    vector<vector<int> >dp(rows,vector<int>(cols,0));
    int res=0;
    for(int i=0; i<rows; i++) {
    	for(int j=0; j<cols; j++) {
    		int tmp=helper(matrix,i,j,dp);
    		res=max(res,tmp);
    	}
    }
    return res;
    

    }
    int helper(vector<vector<int> >& matrix,int i,int j,vector<vector<int> >&dp) {
    int rows=matrix.size();
    int cols=matrix[0].size();
    int res1=1,res2=1,res3=1,res4=1;

    //if(i<0||i>rows||j<0||j>cols) return 0;
    
    if(dp[i][j]>0) return dp[i][j];
    
    if(i>0&&matrix[i][j]<matrix[i-1][j]) res1=1+helper(matrix,i-1,j,dp);
    if(i<rows-1&&matrix[i][j]<matrix[i+1][j]) res2=1+helper(matrix,i+1,j,dp);
    if(j>0&&matrix[i][j]<matrix[i][j-1]) res3=1+helper(matrix,i,j-1,dp);
    if(j<cols-1&&matrix[i][j]<matrix[i][j+1]) res4=1+helper(matrix,i,j+1,dp);
    
    int r1=max(res1,res2);
    int r2=max(res3,res4);
    dp[i][j]=max(r1,r2);
    return max(r1,r2);
    

    }


  • 0
    G
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0

    Thanks for your clean and nice implementation ! Your coding style is much better than my.


  • 0
    K

    What is the complexity of your code? I think it is N^2 and cannot be improved. Just want to validate it.


  • 0
    O

    I convert your solution to cpp version.

    class Solution {
    private:
        vector<vector<int>> cache;
        vector<pair<int, int>> direction;
        int m, n;
        int DFS(int i, int j, vector<vector<int>>& matrix) {
            if(cache[i][j] != 0) return cache[i][j];
            int longest = 1;
            for(auto dir : direction) {
                int x = i + dir.first, y = j + dir.second;
                if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) {
                    continue;
                } else {
                    longest = max(longest, DFS(x, y, matrix) + 1);
                }
            }
            cache[i][j] = longest;
            return longest;
        }
    public:
        int longestIncreasingPath(vector<vector<int>>& matrix) {
            if(matrix.empty()) return 0;
            m = matrix.size(), n = matrix[0].size();
            direction.push_back(pair<int, int>(0, 1));
            direction.push_back(pair<int, int>(0, -1));
            direction.push_back(pair<int, int>(1, 0));
            direction.push_back(pair<int, int>(-1, 0));
            cache = vector<vector<int>>(m, vector<int>(n, 0));
            int longest = 1;
            for (int i = 0; i < m; i++) {
               for(int j = 0; j < n; j++) {
                   longest = max(longest, DFS(i, j, matrix));
               } 
            }
            return longest;
        }
    };

  • 0
    E

    Can you please explain point #4? how is matrix[x][y] <= matrix[i][j] avoids needing a visited[m][n] array, sorry for the silly question :)


  • 1
    V

    @eran We are only going to explore nodes that will help in increasing the sequence. If the value in neighboring cell is lesser we don't care about it.
    This way, if you have a < b, then you will explore b from a but not a from b, this helps in avoiding repeated calls.


  • 0
    K

    I implements your idea using python.

    class Solution(object):
    def longestIncreasingPath(self, matrix):
    	self.dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    	if len(matrix) == 0:
    		return 0
    	m, n = len(matrix), len(matrix[0])
    	cache = [[0 for _ in range(n)] for _ in range(m)]
    	maxValue = 1
    	for i in xrange(m):
    		for j in xrange(n):
    			lens = self.dfs(matrix, i, j, m, n, cache)
    			maxValue = max(maxValue, lens)
    	#print cache
    	return maxValue
    
    def dfs(self, matrix, i, j, m, n, cache):
    	if cache[i][j] != 0:
    		return cache[i][j]
    	maxValue = 1
    	for d in self.dirs:
    		x, y = i + d[0], j + d[1]
    		if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] <= matrix[i][j]:
    			continue
    		lens = 1 + self.dfs(matrix, x, y, m, n, cache)
    		maxValue = max(maxValue, lens)
    	cache[i][j] = maxValue
    	return maxValue

  • 1
    O

    Let me give another solution without DFS.

    You sort the positions by height. And do the same DP along the sorted position sequence.

    public class Solution {
        private final static int[] dx = {0, -1, 1, 0};
        private final static int[] dy = {-1, 0, 0, 1};
        
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix.length < 1) return 0;
            int n = matrix.length, m = matrix[0].length, len = m * n;
            int[][] opt = new int[n][m];
            int[][] h = new int[len][2];
            for (int i = 0; i < len; i++) {
                h[i][0] = matrix[i / m][i % m];
                h[i][1] = i;
            }
            
            Arrays.sort(h, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return a[0] - b[0];
                }
            });
            
            int ans = 0;
            for (int[] cur : h) {
                int i = cur[1] / m, j = cur[1] % m, tmp = 1;
                for (int dir = 0; dir < 4; dir++) 
                    if (i + dx[dir] >= 0 && i + dx[dir] < n 
                    && j + dy[dir] >= 0 && j + dy[dir] < m
                    && matrix[i + dx[dir]][j + dy[dir]] < cur[0])
                        tmp = Math.max(tmp, opt[i + dx[dir]][j + dy[dir]] + 1);
                opt[i][j] = tmp;
                ans = Math.max(ans, tmp);
            }
            return ans;
        }
    }

  • 0
    C

    What's the time complexity of this solution?

    I found that DFS solution using various pruning techniques will affect eh analysis of time complexity.

    Thanks


  • 0
    X

    Hi, thanks for sharing. I am just curious about the time complexity. Would it be better using DP + memorization instead of DFS because of the reuse?


  • 0
    P

    Hello Can someone please explain me....

    Are we considering the visited in the solution ..

    If we are storing the cache[][] means we are revisiting the matrix cells


  • 0
    J

    Nice one sir, upvoted.

    One thing to make the run time 14 ms: check for 0 in the double for loop before calling dfs, and only perform when the cell is actually 0 at the time.


  • 15
    J

    @coder2 @XindiWang the DFS here is basically like DP with memorization. Every cell that has been computed will not be computed again, only a value look-up is performed. So this is O(mn), m and n being the width and height of the matrix.
    To be exact, each cell can be accessed 5 times at most: 4 times from the top, bottom, left and right and one time from the outermost double for loop. 4 of these 5 visits will be look-ups except for the first one. So the running time should be lowercase o(5mn), which is of course O(mn).


  • 2

    Same idea but using if condition rather than for loop:
    public class Solution {

    private int m;
    private int n;
    private int[][] maxILen;
    private int[][] matrix;
    
    public int longestIncreasingPath(int[][] matrix) {
        
        m = matrix.length;
        if(m < 1) return 0;
        n = matrix[0].length;
        this.matrix = matrix;
        
        maxILen = new int[m][n];
        int max = 1;
        
        for(int i=0;i<m;i++){
            
            for(int j=0;j<n;j++){
                max = Math.max(max, maxDFS(i,j));                        
            }
        }
        
        return max;
    }
    
    private int maxDFS(int i,int j){
        if(maxILen[i][j] != 0) return maxILen[i][j];
        
        int max = 1;
        if(i+1 < m && matrix[i+1][j] > matrix[i][j]) max = Math.max(max, 1 + maxDFS(i+1,j));
        if(i-1 >= 0 && matrix[i-1][j] > matrix[i][j]) max = Math.max(max, 1 + maxDFS(i-1,j));
        if(j+1 < n && matrix[i][j+1] > matrix[i][j]) max = Math.max(max, 1 + maxDFS(i,j+1));
        if(j-1 >= 0 && matrix[i][j-1] > matrix[i][j]) max = Math.max(max, 1 + maxDFS(i,j-1));
        maxILen[i][j] = max;
        return max;
    }
    

    }


  • 3
    T

    Good idea!
    The key observation is that the sequence is strictly increasing, so it can not have loops. So we have the following:

    longest(i,j) = longest increasing path from (i,j) to (k,l) + longest(k,l)
    where longest(i,j) is longest increasing path starting with (i,j).


  • 0

    @kamal444 said in 15ms Concise Java Solution:

    complexity

    In my opinion, the time complexity is O(m* n). Every element in the matrix can be only visited once cuz we use the cache.


  • 0

    Nice Solution
    Python code following your thought

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            if not matrix:
                return 0
            m, n = len(matrix), len(matrix[0])
            f = [[0] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    self.helper(matrix, i, j, m, n, f)
            return max(map(max,f))
            
        def helper(self, matrix, i, j, m, n, f):
            if f[i][j]:
                return f[i][j]
            f[i][j] = 1
            for a, b in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
                if 0 <= a < m and 0 <= b < n and matrix[a][b] > matrix[i][j]:
                    f[i][j] = max(f[i][j], 1 + self.helper(matrix, a, b, m, n, f))
            return f[i][j]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.