23ms easy Java dfs solution

  • 0
    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){
        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.