## Sunday, October 9, 2016

### LeetCode 417 - Pacific Atlantic Water Flow

https://leetcode.com/problems/pacific-atlantic-water-flow/
Given an `m x n` matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.
Example:

```Given the following 5x5 matrix:

Pacific ~   ~   ~   ~   ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
```
X. BFS
https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean
``````    int[][]dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new LinkedList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int n = matrix.length, m = matrix[0].length;
//One visited map for each ocean
boolean[][] pacific = new boolean[n][m];
boolean[][] atlantic = new boolean[n][m];
Queue<int[]> pQueue = new LinkedList<>();
Queue<int[]> aQueue = new LinkedList<>();
for(int i=0; i<n; i++){ //Vertical border
pQueue.offer(new int[]{i, 0});
aQueue.offer(new int[]{i, m-1});
pacific[i][0] = true;
atlantic[i][m-1] = true;
}
for(int i=0; i<m; i++){ //Horizontal border
pQueue.offer(new int[]{0, i});
aQueue.offer(new int[]{n-1, i});
pacific[0][i] = true;
atlantic[n-1][i] = true;
}
bfs(matrix, pQueue, pacific);
bfs(matrix, aQueue, atlantic);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(pacific[i][j] && atlantic[i][j])
res.add(new int[]{i,j});
}
}
return res;
}
public void bfs(int[][]matrix, Queue<int[]> queue, boolean[][]visited){
int n = matrix.length, m = matrix[0].length;
while(!queue.isEmpty()){
int[] cur = queue.poll();
for(int[] d:dir){
int x = cur[0]+d[0];
int y = cur[1]+d[1];
if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]){
continue;
}
visited[x][y] = true;
queue.offer(new int[]{x, y});
}
}
}``````

http://bookshadow.com/weblog/2016/10/09/leetcode-pacific-atlantic-water-flow/
BFS（广度优先搜索）

def pacificAtlantic(self, matrix): """ :type matrix: List[List[int]] :rtype: List[List[int]] """ m = len(matrix) n = len(matrix[0]) if m else 0 if m * n == 0: return [] topEdge = [(0, y) for y in range(n)] leftEdge = [(x, 0) for x in range(m)] pacific = set(topEdge + leftEdge) bottomEdge = [(m - 1, y) for y in range(n)] rightEdge = [(x, n - 1) for x in range(m)] atlantic = set(bottomEdge + rightEdge) def bfs(vset): dz = zip((1, 0, -1, 0), (0, 1, 0, -1)) queue = list(vset) while queue: hx, hy = queue.pop(0) for dx, dy in dz: nx, ny = hx + dx, hy + dy if 0 <= nx < m and 0 <= ny < n: if matrix[nx][ny] >= matrix[hx][hy]: if (nx, ny) not in vset: queue.append((nx, ny)) vset.add((nx, ny)) bfs(pacific) bfs(atlantic) result = pacific & atlantic return map(list, result)

X. DFS
https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean
``````    public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new LinkedList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int n = matrix.length, m = matrix[0].length;
boolean[][]pacific = new boolean[n][m];
boolean[][]atlantic = new boolean[n][m];
for(int i=0; i<n; i++){
dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);
}
for(int i=0; i<m; i++){
dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (pacific[i][j] && atlantic[i][j])
res.add(new int[] {i, j});
return res;
}

int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};

public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){
int n = matrix.length, m = matrix[0].length;
if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
return;
visited[x][y] = true;
for(int[]d:dir){
dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);
}
}``````
https://discuss.leetcode.com/topic/62306/java-dfs-solution
http://www.itdadao.com/articles/c15a557475p0.html
1、分别处理每个海洋，从海洋边缘（每个海洋两条边）开始，一步步的搜索，即从连接海洋的地方还是搜索，哪些节点的高度高于等于自身（反过来就是可以从那里流到自己），如果是，就标记为true，就这样不断搜索下去。最后所有标记为true的位置就是可以流到对应的海洋。
2、找这两个矩阵，同为true的输出，就是都能流到两个海洋的位置
```    int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
//判断一个节点能否流通到海洋
private void flow(boolean visited[][],int matrix[][],int x,int y,int n,int m ){
visited[x][y] = true;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<m){
//一个节点是只能留到不高于自己高度的节点，但是我们这里是反过来找能从nxny留到xy的节点，所以这里注意下
if(visited[nx][ny]==false && matrix[nx][ny]>=matrix[x][y])
flow(visited,matrix,nx,ny,n,m);
}
}
}
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new ArrayList();
int n = matrix.length;
if(n==0) return res;
int m = matrix[0].length;
boolean PV[][] = new boolean[n][m];
boolean AV[][] = new boolean[n][m];
// 这里从所有临海的地方到这回去判断某个节点是否能流到对应的地方
for(int i=0;i<n;i++){
flow(PV,matrix,i,0,n,m);
flow(AV,matrix,i,m-1,n,m);
}
for(int i=0;i<m;i++){
flow(PV,matrix,0,i,n,m);
flow(AV,matrix,n-1,i,n,m);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(PV[i][j] && AV[i][j])
res.add(new int[] {i,j});
}
}
return res;

}```
https://discuss.leetcode.com/topic/62415/reverse-flow-technique-clean-java-solution-using-dfs-and-state-machine
1. DFS from first row and first column and mark all the reachable nodes (reverse comparison) as `1`.
If cell is marked as `1` or `3` already, break DFS
If cell is marked as `2` already, mark it `3`
2. DFS from last row and last column and mark all the reachable nodes (reverse comparison) as `2`.
If cell is marked as `2` or `3` already, break DFS
If cell is marked as `1` already, mark it `3`
• Space complexity: `O(n)`
• Time complexity: `O(n^3)`
I guess we can argue that it is `O(n^2)` since we don't visit all the `n^2`cells for the `4n` DFSes
``````    int m;
int n;

public List<int[]> pacificAtlantic(int[][] matrix) {

List<int[]> res = new ArrayList<>();
m = matrix.length;

if (m == 0) return res;

n = matrix[0].length;

if (n == 0) return res;

// 0 not visited
// 1 pacific
// 2 atlantic
// 3 both
int[][] touchdown = new int[m][n];

for (int i = 0; i < m; ++i) {
dfs(matrix, touchdown, i, 0, 1, res);
dfs(matrix, touchdown, i, n - 1, 2, res);
}

for (int j = 0; j < n; ++j) {
dfs(matrix, touchdown, 0, j, 1, res);
dfs(matrix, touchdown, m - 1, j, 2, res);
}

return res;
}

private void dfs(int[][] matrix, int[][] touchdown, int i, int j, int toState, List<int[]> res) {

if (i < 0 || j < 0 || i >= m || j >= n) return;

if (!updateState(touchdown, i, j, toState, res)) {
return;
}

if (i + 1 < m && matrix[i][j] <= matrix[i + 1][j]) {
dfs(matrix, touchdown, i + 1, j, toState, res);
}
if (j + 1 < n && matrix[i][j] <= matrix[i][j + 1]) {
dfs(matrix, touchdown, i, j + 1, toState, res);
}
if (i - 1 >= 0 && matrix[i][j] <= matrix[i - 1][j]) {
dfs(matrix, touchdown, i - 1, j, toState, res);
}
if (j - 1 >= 0 && matrix[i][j] <= matrix[i][j - 1]) {
dfs(matrix, touchdown, i, j - 1, toState, res);
}
}

private boolean updateState(int[][] touchdown, int i, int j, int toState, List<int[]> res) {
int currState = touchdown[i][j];
if (currState == 3 || currState == toState) return false;
if (currState == 0) {
touchdown[i][j] = toState;
} else {
touchdown[i][j] = 3;
res.add(new int[]{i, j});
}
return true;
}``````

## Labels

GeeksforGeeks (1109) LeetCode (1095) Review (846) Algorithm (795) to-do (633) LeetCode - Review (574) Classic Algorithm (324) Dynamic Programming (294) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Bit Algorithms (120) Different Solutions (120) Lintcode (113) Smart Algorithm (109) Math (108) HackerRank (89) Binary Search (83) Binary Tree (82) Graph Algorithm (76) Greedy Algorithm (73) DFS (71) Stack (65) Interview Corner (61) List (58) BFS (54) Codility (54) ComProGuide (52) Trie (49) USACO (46) Interval (45) LeetCode Hard (42) ACM-ICPC (41) Data Structure (40) Knapsack (40) Jobdu (39) Matrix (39) String Algorithm (38) Union-Find (37) Backtracking (36) Codeforces (36) Must Known (36) Sort (35) Array (33) Segment Tree (33) Sliding Window (33) prismoskills (33) HDU (31) Priority Queue (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Palindrome (28) to-do-must (28) Graph (27) Random (27) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) Time Complexity (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) DFS + Review (21) Two Pointers (21) Brain Teaser (20) CareerCup (20) LeetCode - DP (20) Merge Sort (20) O(N) (20) Follow Up (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) KMP (14) LeetCode - DFS (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) Majority (13) Reverse Thinking (13) mitbbs (13) Combination (12) Modify Tree (12) Reconstruct Tree (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Graph DFS (11) LCA (11) Miscs (11) Princeton (11) Proof (11) Rolling Hash (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) DFS+Cache (10) HackerRank Easy (10) O(1) Space (10) SPOJ (10) Theory (10) TreeMap (10) Tutorialhorizon (10) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stock (9) Use XOR (9) Book Notes (8) Bottom-Up (8) DFS+BFS (8) Linked List (8) Prime (8) Suffix Tree (8) Tech-Queries (8) 穷竭搜索 (8) Expression (7) Game Nim (7) Graph BFS (7) Hackerearth (7) Inversion (7) Quick Select (7) Radix Sort (7) TreeSet (7) n00tc0d3r (7) 蓝桥杯 (7) DFS+DP (6) DP - Tree (6) Dijkstra (6) Dutch Flag (6) How To (6) Manacher (6) One Pass (6) Pruning (6) Rabin-Karp (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) Xpost (6) reddit (6) AI (5) Big Data (5) Brute Force (5) Code Kata (5) Coding (5) Convex Hull (5) Crazyforcode (5) Cycle (5) Find Rule (5) Graph Cycle (5) Immutability (5) Java (5) Maze (5) Pre-Sum (5) Quadtrees (5) Quora (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Chess Game (4) Distributed (4) Flood fill (4) Histogram (4) MST (4) MinMax (4) N Queens (4) Probability (4) Programcreek (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) B Tree (3) Coins (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Github (3) GoLang (3) Joseph (3) Jump Game (3) K (3) LogN (3) Minesweeper (3) NP Hard (3) O(N) Hard (3) Parser (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Subtree (3) Trie + DFS (3) Word Ladder (3) bookkeeping (3) codebytes (3) Array Merge (2) BOJ (2) Bellman Ford (2) Bit Counting (2) Bit Mask (2) Bloom Filter (2) Clock (2) Codesays (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-i-k-j (2) DP-树形 (2) Factor (2) GoHired (2) Graham Scan (2) Huffman Tree (2) Invariant (2) Islands (2) Lucene-Solr (2) Matrix Power (2) Median (2) Parentheses (2) Peak (2) Programming (2) Robot (2) Rosettacode (2) Search (2) SimHash (2) Summary (2) TV (2) Tile (2) Tree Sum (2) Word Break (2) Word Graph (2) Word Trie (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Big Integer (1) Big Number (1) Binary (1) Bipartite (1) BitMap (1) BitMap index (1) BitSet (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Chinese (1) Clean Code (1) Cloest (1) Clone (1) Code Quality (1) Company-Epic (1) Company-Yelp (1) Concise (1) Concurrency (1) Custom Sort (1) DFS-Matrix (1) DP-Difficult (1) DP-Graph (1) DP-MaxMin (1) Database (1) Diagonal (1) Domino (1) Dr Dobb's (1) Duplicate (1) FST (1) Fraction (1) Funny (1) Game (1) Generation (1) GeoHash (1) Google APAC (1) Gray Code (1) HOJ (1) Hanoi (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Interview (1) Isomorphic (1) JDK8 (1) Knight (1) Kruskal (1) Kth Element (1) Linkedin (1) Local MinMax (1) Matrix BFS (1) Matrix Graph (1) Matrix+DP (1) MinHash (1) MinMax Heap (1) Monto Carlo (1) Multiple DFS (1) Next Element (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Persistent (1) Power Set (1) PreProcess (1) Python (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Region (1) Resources (1) Robin (1) Selection (1) Similarity (1) Square (1) String DP (1) SubMatrix (1) Subsequence (1) TSP (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tree Rotate (1) Trie vs Hash (1) Triplet (1) Two Stacks (1) Two-End-BFS (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) javabeat (1) jum (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)