Simple commented java solution with thinking progress O(n)


  • 11
    /*
    1.Naive solution:
        Standard dfs, which means for each point, we check if it can reach both pacific and atlantic, 
        for each point, we can possibly check all the rest of points, O(m*n * m*n)
    
    2.A little improvement:
        What about we 4 hash tables, they keep track of all the points we know so far that 
            can reach atlantic
            cannot reach atlantic
            can reach pacific
            cannot reach pacific
        It's doable, still hit TLE, although I didn't hit TLE when not submitting the code, but running it using the provided testing environment
    
    3.On the other hand, we can consider the flip side
        We can let the pacific and atlantic ocean "flow into" the matrix as much as possible,
        using 2 boolean arrays, one for each ocean. 
        The result are the points that are true in both boolean table
    */
    
    
    public class Solution {
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> result = new ArrayList<int[]>();
            if(matrix.length == 0 || matrix[0].length == 0) return result;   
            boolean[][] pacific = new boolean[matrix.length][matrix[0].length];  // the pacific boolean table
            boolean[][] atlantic = new boolean[matrix.length][matrix[0].length]; // the atlantic booean table
            //initially, all the top and left cells are flooded with pacific water
            //and all the right and bottom cells are flooded with atlantic water
            for(int i = 0; i < matrix.length; i++){
                pacific[i][0] = true;
                atlantic[i][matrix[0].length-1] = true;
            }
            for(int i = 0; i < matrix[0].length; i++){
                pacific[0][i] = true;
                atlantic[matrix.length-1][i] = true; 
            }
            //we go around the matrix and try to flood the matrix from 4 side.
            for(int i = 0; i < matrix.length; i++){
                boolean[][] pacificVisited = new boolean[matrix.length][matrix[0].length];
                boolean[][] atlanticVisited = new boolean[matrix.length][matrix[0].length];
                water(pacific, pacificVisited, matrix, i,0);
                water(atlantic, atlanticVisited, matrix, i, matrix[0].length - 1);            
            }
            for(int i = 0; i < matrix[0].length; i++){
                boolean[][] pacificVisited = new boolean[matrix.length][matrix[0].length];
                boolean[][] atlanticVisited = new boolean[matrix.length][matrix[0].length];
                water(pacific, pacificVisited, matrix, 0,i);
                water(atlantic, atlanticVisited, matrix, matrix.length - 1, i);            
            }
            //check the shared points among 2 tables
            for(int i = 0; i < matrix.length; i++){
                for(int j = 0; j < matrix[0].length; j++){
                    if(pacific[i][j] && atlantic[i][j]){
                        int[] element = {i,j};
                        result.add(element);
                    }
                }
            }
            return result;
        }
        //the flood function
        private void water(boolean[][] wet, boolean[][] visited, int[][] matrix, int i , int j){
            wet[i][j] = true;
            visited[i][j] = true;
            int[] x = {0,0,1,-1};
            int[] y = {1,-1,0,0};
            for(int k = 0; k < 4; k++){
                if(i+y[k] >= 0 && i+y[k] < matrix.length && j+x[k] >= 0 && j+x[k] < matrix[0].length 
                    && !visited[i+y[k]][j+x[k]] && matrix[i+y[k]][j+x[k]] >= matrix[i][j]){
                    water(wet, visited, matrix, i+y[k], j+x[k]);
                }
            }
        }
    }````
    
    P.S Sometimes you choose an option just because the alternative is just worse.....

  • 0
    L

    I think you don't need to initialize the boundaries, since every time you enter the water function, you just set the value to true.


  • 3

    "Sometimes you choose an option just because the alternative is just worse"

    ------Donald Trump


  • 12

    Obviously the O(n) claim in your title is wrong, as that's impossible. Typical Trump...


  • 3

    @StefanPochmann "What does N represent" is question you should ask before claiming I'm wrong. Typical trump hater.


  • 6

    @DonaldTrump said in Simple commented java solution with thinking progress O(n):

    @StefanPochmann "What does N represent" is question you should ask before claiming I'm wrong. Typical trump hater.

    Not N but n. And n is the number of columns. I don't need to ask. It's defined in the problem specification. And you yourself even correctly wrote "O(m*n * m*n)" for the "naive solution".


Log in to reply
 

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