esay-to-understand 41ms java solution with explaintion


  • 0
    4

    The ideal can divided into two steps:
    1.Create two two-dimensional boolean arrays to store the information that which cells can flow to "Atlantic ocean" and "Pacific ocean" respectively.
    2.Seek the intersection of two sets.

    // Horizontal, vertical coordinates and value of each unit
    	public class Pair {
    		int row;
    		int clo;
    		int height;
    
    		public Pair(int r, int c, int h) {
    			this.row = r;
    			this.clo = c;
    			this.height = h;
    		}
    	}
    
    	public List<int[]> pacificAtlantic(int[][] matrix) {
    		List<int[]> res = new ArrayList<>();
    		if (matrix == null || matrix.length == 0) {
    			return res;
    		}
    		// define the cells which can reach "Atlantic ocean".
    		boolean[][] canReachA = new boolean[matrix.length][matrix[0].length];
    
    		// define the cells which can reach "Pacific ocean".
    		boolean[][] canReachP = new boolean[matrix.length][matrix[0].length];
    		int[][] direct = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    		// Define the sort mode to use PriorityQueue to traverse.
    		Comparator<Pair> order = new Comparator<Solution.Pair>() {
    
    			@Override
    			public int compare(Pair arg0, Pair arg1) {
    				if (arg0.row != arg1.row) {
    					return arg0.row - arg1.row;
    				} else {
    					return arg0.clo - arg1.clo;
    				}
    			}
    		};
    
    		// initialize the cells which can reach "Pacific ocean" and
    		// "Atlantic ocean" respectively.
    
    		Queue<Pair> queueP = new PriorityQueue<>(order);
    		Queue<Pair> queueA = new PriorityQueue<>(order);
    		for (int i = 0; i < matrix.length; i++) {
    			queueP.add(new Pair(i, 0, matrix[i][0]));
    			canReachP[i][0] = true;
    			queueA.add(new Pair(i, matrix[0].length - 1,
    					matrix[i][matrix[0].length - 1]));
    			canReachA[i][matrix[0].length - 1] = true;
    		}
    		for (int i = 1; i < matrix[0].length - 1; i++) {
    			queueP.add(new Pair(0, i, matrix[0][i]));
    			canReachP[0][i] = true;
    			queueA.add(new Pair(matrix.length - 1, i,
    					matrix[matrix.length - 1][i]));
    			canReachA[matrix.length - 1][i] = true;
    		}
    		queueP.add(new Pair(0, matrix[0].length - 1,
    				matrix[0][matrix[0].length - 1]));
    		canReachP[0][matrix[0].length - 1] = true;
    		queueA.add(new Pair(matrix.length - 1, 0, matrix[matrix.length - 1][0]));
    		canReachA[matrix.length - 1][0] = true;
    
    		// Traversing array to obtain all units which can reach "Pacific ocean"
    		// and "Atlantic ocean" respectively.
    		helpPA(queueP, canReachP, direct, matrix);
    		helpPA(queueA, canReachA, direct, matrix);
    		
    		//Seek the intersection of two sets.
    		for (int i = 0; i < matrix.length; i++) {
    			for (int j = 0; j < matrix[0].length; j++) {
    				if (canReachA[i][j] && canReachP[i][j]) {
    					res.add(new int[] { i, j });
    				}
    			}
    		}
    		return res;
    	}
    
    	private void helpPA(Queue<Pair> queue, boolean[][] canReach,
    			int[][] direct, int[][] matrix) {
    		while (!queue.isEmpty()) {
    			Pair temp = queue.poll();
    			for (int[] is : direct) {
    				int nRow = temp.row + is[0];
    				int nCol = temp.clo + is[1];
    				if (nRow >= 0 && nRow < canReach.length && nCol >= 0
    						&& nCol < canReach[0].length
    						&& canReach[nRow][nCol] == false
    						&& matrix[nRow][nCol] >= temp.height) {
    					canReach[nRow][nCol] = true;
    					queue.offer(new Pair(nRow, nCol, matrix[nRow][nCol]));
    				}
    			}
    		}
    
    	}
    

Log in to reply
 

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