Java 28ms DFS and 37 ms BFS


  • 0

    Java 37ms BFS
    ...
    public class Solution {
    public List<int[]> pacificAtlantic(int[][] matrix) {
    List<int[]> res = new ArrayList<int[]>();
    int len1 = matrix.length;
    if(len1 == 0) return res;
    int len2 = matrix[0].length;
    boolean[][] pacific = createMatrix(matrix, len1, len2, 1);
    boolean[][] atilantic = createMatrix(matrix, len1, len2, 2);
    helper(matrix, new boolean[len1][len2], pacific, len1, len2, 1);
    helper(matrix, new boolean[len1][len2], atilantic, len1, len2, 2);
    for(int i = 0; i < len1; i++) {
    for(int j = 0; j < len2; j++) {
    if(pacific[i][j] && atilantic[i][j]) res.add(new int[]{i, j});
    }
    }
    return res;
    }

    private void helper(int[][] matrix, boolean[][] visited, boolean[][] ocean,
    		int len1, int len2, int k) {
    	// TODO Auto-generated method stub
    	for(int i = 0; i < len1; i++) {
    		for(int j = 0; j < len2; j++) {
    			if(ocean[i][j]) bfs(matrix, visited, ocean, i, j, len1, len2, k);
    		}
    	}
    	return;
    }
    
    private void bfs(int[][] matrix, boolean[][] visited, boolean[][] des,
    		int i, int j, int len1, int len2, int k) {
    	// TODO Auto-generated method stub
    	Queue<int[]> queue = new LinkedList<int[]>();
    	queue.add(new int[]{i, j});
    	visited[i][j] = true;
    	while(!queue.isEmpty()) {
    		int[] cor = queue.poll();
    		int x = cor[0], y = cor[1];
    		des[x][y] = true;
    		if(x - 1 > -1 && !visited[x - 1][y] && matrix[x][y] <= matrix[x - 1][y]) {
    			queue.add(new int[]{x - 1, y});
    			visited[x - 1][y] = true;
    		}
    		if(y - 1 > -1 && !visited[x][y - 1] && matrix[x][y] <= matrix[x][y - 1]) {
    			queue.add(new int[]{x, y - 1});
    			visited[x][y - 1] = true;
    		}
    		if(y + 1 < len2 && !visited[x][y + 1] && matrix[x][y] <= matrix[x][y + 1]) {
    			queue.add(new int[]{x, y + 1});
    			visited[x][y + 1] = true;
    		}
    		if(x + 1 < len1 && !visited[x + 1][y] && matrix[x][y] <= matrix[x + 1][y]) {
    			queue.add(new int[]{x + 1, y});
    			visited[x + 1][y] = true;
    		}
    	}
    }
    
    private boolean[][] createMatrix(int[][] matrix, int len1, int len2, int flag) {
    	// TODO Auto-generated method stub
    	boolean[][] res = new boolean[len1][len2];
    	if(flag == 1) {
    		for(int i = 0; i < len1; i++) {
    			for(int j = 0; j < len2; j++) {
    				if(i == 0 || j == 0) res[i][j] = true;
    			}
    		}
    	}
    	else {
    		for(int i = 0; i < len1; i++) {
    			for(int j = 0; j < len2; j++) {
    				if(i == len1 - 1 || j == len2 - 1) res[i][j] = true;
    			}
    		}
    	}
    	return res;
    }   
    

    }
    ...
    Java 28ms DFS
    ...
    public class Solution {
    public List<int[]> pacificAtlantic(int[][] matrix) {
    List<int[]> res = new ArrayList<int[]>();
    int len1 = matrix.length;
    if(len1 == 0) return res;
    int len2 = matrix[0].length;
    boolean[][] pacific = createFlagMatrix(matrix, len1, len2, 1);
    boolean[][] atilantic = createFlagMatrix(matrix, len1, len2, 2);
    helper(matrix, new boolean[len1][len2], pacific, len1, len2, 1);
    helper(matrix, new boolean[len1][len2], atilantic, len1, len2, 2);
    for(int i = 0; i < len1; i++) {
    for(int j = 0; j < len2; j++) {
    if(pacific[i][j] && atilantic[i][j]) res.add(new int[]{i, j});
    }
    }
    return res;
    }

    private void helper(int[][] matrix, boolean[][] visited,
    		boolean[][] ocean, int len1, int len2, int k) {
    	// TODO Auto-generated method stub
    	for(int i = 0; i < len1; i++) {
    		for(int j = 0; j < len2; j++) {
    			if(ocean[i][j]) dfs(matrix, visited, ocean, i, j, len1, len2, k);
    		}
    	}
    }
    
    private void dfs(int[][] matrix, boolean[][] visited, boolean[][] des, int i,
    		int j, int len1, int len2, int k) {
    	// TODO Auto-generated method stub
    	if(visited[i][j]) return;
    	visited[i][j] = true;
    	des[i][j] = true;
    	if(i - 1 > -1 && !visited[i - 1][j] && matrix[i][j] <= matrix[i - 1][j]) {
    		dfs(matrix, visited, des, i - 1, j, len1, len2, k);
    	}
    	if(j - 1 > -1 && !visited[i][j - 1] && matrix[i][j] <= matrix[i][j - 1]) {
    		dfs(matrix, visited, des, i, j - 1, len1, len2, k);
    	}
    	if(j + 1 < len2 && !visited[i][j + 1] && matrix[i][j] <= matrix[i][j + 1]) {
    		dfs(matrix, visited, des, i, j + 1, len1, len2, k);
    	}
    	if(i + 1 < len1 && !visited[i + 1][j] && matrix[i][j] <= matrix[i + 1][j]) {
    		dfs(matrix, visited, des, i + 1, j, len1, len2, k);
    	}
    }
    
    private boolean[][] createFlagMatrix(int[][] matrix, int len1, int len2, int flag) {
    	// TODO Auto-generated method stub
    	boolean[][] res = new boolean[len1][len2];
    	if(flag == 1) {
    		for(int i = 0; i < len1; i++) {
    			for(int j = 0; j < len2; j++) {
    				if(i == 0 || j == 0) res[i][j] = true;
    			}
    		}
    	}
    	else {
    		for(int i = 0; i < len1; i++) {
    			for(int j = 0; j < len2; j++) {
    				if(i == len1 - 1 || j == len2 - 1) res[i][j] = true;
    			}
    		}
    	}
    	return res;
    }
    

    }
    ...


Log in to reply
 

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