Longest Increasing Path in a Matrix


  • 0

    Click here to see the full article post


  • 0
    J

    the time complexity of the second solution should be O(mn) in total, isn't it?


  • 0
    H

    can you give more examples of questions where onion peeling is used for solving the question?


  • 0
    D

    class Solution {
    public int longestIncreasingPath(int[][] matrix) {

        if(matrix.length == 0 || matrix[0].length==0){
            return 0;
        }
        
        int [][] maxpath = new int [matrix.length][matrix[0].length];
        
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j< matrix[0].length; j++)
                    maxpath[i][j] = -1;
                
        }
        
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j< matrix[0].length; j++)
                findMax(matrix, maxpath, i, j);
        }
        
        
        
        int max = -1;
        
         for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j< matrix[0].length; j++)
                if(maxpath[i][j]> max){
                    max = maxpath[i][j];
                }
        }
        
        return max;
        
    }
    
    public void findMax(int[][] matrix, int[][] maxpath, int i, int j){
        
        if(maxpath[i][j] != -1){
            return;
        }
        
        int[][] adj = {{0, -1}, {-1, 0}, {0, 1}, {1,0}};
        int result = -1;
        for(int k = 0; k < 4; k++){
            int newx = i+adj[k][0];
            int newy = j+adj[k][1];
                
            if(newx >= 0 && newx < matrix.length && newy >= 0 && newy< matrix[0].length){
                if(matrix[newx][newy]> matrix[i][j]){
                    findMax(matrix, maxpath, newx, newy);
                    if( maxpath[newx][newy] + 1 > result)
                        result = maxpath[newx][newy] + 1;
                }
            }
            
        }
        
        if(result == -1){
            maxpath[i][j] = 1;
        }else{
            maxpath[i][j] = result;
        }
        
        
    } 
    

    }


Log in to reply
 

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