Java SIMPLE TO UNDERSTAND - Reverse Water flow


  • 1
    J
    public class Solution {
        public List<int[]> pacificAtlantic(int[][] matrix) {
            if(matrix.length == 0) return new ArrayList();
            
            HashSet<ArrayList<Integer>> pacific = new HashSet<ArrayList<Integer>>();
            HashSet<ArrayList<Integer>> atlantic = new HashSet<ArrayList<Integer>>();
            
            for(int i = 0; i < matrix.length; i++) discover(matrix, i, 0, pacific); //Left Column
            for(int i = 0; i < matrix[0].length; i++) discover(matrix, 0, i, pacific); // Top Row
        
            for(int i = 0; i < matrix.length; i++) discover(matrix, i, matrix[0].length-1, atlantic); //Right Column
            for(int i = 0; i < matrix[0].length; i++) discover(matrix, matrix.length-1, i, atlantic); //Bottom Row
            
            ArrayList results = new ArrayList<int[]>();
            for(ArrayList<Integer> coords : pacific) if(atlantic.contains(coords)) results.add(new int[] {coords.get(0), coords.get(1)});
            return results;
        }
        
        public void discover(int[][] matrix, int i, int j, HashSet<ArrayList<Integer>> ocean) {
            ArrayList<Integer> coord = new ArrayList<Integer>();
            coord.add(i);
            coord.add(j);
            if(!ocean.add(coord)) return;
            if(i-1 > -1 && matrix[i-1][j] >= matrix[i][j]) discover(matrix, i-1, j, ocean);
            if(j-1 > -1 && matrix[i][j-1] >= matrix[i][j]) discover(matrix, i, j-1, ocean);
            if(i+1 < matrix.length && matrix[i+1][j] >= matrix[i][j]) discover(matrix, i+1, j, ocean);
            if(j+1 < matrix[0].length && matrix[i][j+1] >= matrix[i][j]) discover(matrix, i, j+1, ocean);   
        }
    }
    
    

Log in to reply
 

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