23ms easy Java dfs solution


  • 0
    I
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length== 0) return 0;
        int[][] val=new int[matrix.length][matrix[0].length];
        boolean[][] visited=new boolean[matrix.length][matrix[0].length];
        int max=0;
        
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(!visited[i][j]) dfs(matrix,i,j,val,visited);
                if(max< val[i][j]) max=val[i][j];
            }
        }
        
        return max;
    }
    
    private void dfs(int[][] matrix, int row, int col, int[][] val,boolean[][] visited){
    
        visited[row][col]=true;
        int[] x={-1,0,0,1};
        int[] y={0,1,-1,0};
        
        for(int i=0;i<4;i++){
          if(row+x[i]>=0 && row+x[i]<matrix.length && col+y[i]>=0 && col+y[i]<matrix[0].length && matrix[row+x[i]][col+y[i]]>matrix[row][col]){
                if(!visited[row+x[i]][col+y[i]]) dfs(matrix,row+x[i],col+y[i],val,visited);
                       
                val[row][col]=val[row][col]>1+val[row+x[i]][col+y[i]]? val[row][col]:1+val[row+x[i]][col+y[i]];
                 
               }
           } 
    
           if(val[row][col]==0) val[row][col]=1;
           
    }

Log in to reply
 

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