DSA-100 · FOCUSED PRACTICE
Pacific Atlantic Water Flow
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 44622 deterministic checks. Learner drafts are not executed.
Understand the problem
Return every coordinate from which water can reach both the Pacific and Atlantic oceans, using orthogonal moves to equal or lower heights.
- The outer array is nonnull and rectangular with nonnull rows, at most 100,000 rows and 100,000 cells. Size bounds are preconditions; null outer input throws NullPointerException and null/ragged rows throw IllegalArgumentException. Zero rows or zero columns are allowed.
- Preserve all source cell values and row references; shared input row objects are allowed because coordinates, not row objects, identify vertices. Heights are arbitrary int values, including negative and extreme values; no height subtraction is needed. Pacific touches the top and left edges; Atlantic touches the bottom and right edges.
- Water may move only to an orthogonal neighbor of height <= current height. Return coordinates in row-major order as a fresh mutable outer list with fresh distinct mutable two-int row lists, independent across calls. Empty/zero-column input returns a fresh empty list.
Examples
Input:
[[1,2,2],[3,2,3],[2,4,5]]
Output:[[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]A cell must have a valid downhill route to each ocean, possibly along different paths.
Input:
[[MIN,MAX],[MAX,MIN]]
Output:[[0,1],[1,0]]Each MAX cell touches both oceans; the low opposite-corner cells cannot climb to reach the other ocean.
Input:
[[5,5],[5,5]]
Output:[[0,0],[0,1],[1,0],[1,1]]Equal-height edges permit flow across the plateau.
Before you start
- Directed reachability and reversal of edges
- Separate multi-source traversals and intersection versus union
Recognize the structure
Forward searching from every cell repeats reachability. Reverse the edge relation: if water can flow from high to low, an ocean search can reach the high cell from the low one. One reversed traversal per ocean computes all possible sources simultaneously.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 166/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Can you search from each ocean rather than from every cell?
Hint 2
Reverse every legal downhill edge into an uphill/equal edge.
Hint 3
Run two independent boundary searches and intersect their masks.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Follow downhill paths from each cell
For every coordinate, BFS along <= height edges and record which ocean boundaries are reached. Add the coordinate only after both are seen. This is direct but repeats nearly the whole grid for many starts; two reversed boundary searches reuse that work.
Improve the baseline
Define two source borders
Seed top/left cells for Pacific and bottom/right cells for Atlantic, once per ocean. A corner is not duplicated within one source scan.
Reverse the inequality, not the ocean labels
From a currently reached cell, visit neighbors of greater or equal height. Each such reverse edge certifies a forward downhill step back toward the ocean.
Intersect complete masks
Maintain independent Pacific and Atlantic seen matrices. After both finish, emit only coordinates whose two flags are true, scanning row-major for deterministic order.
Why it is correct
Reversal equivalence
A forward path of nonincreasing heights from cell x to an ocean becomes a reverse path of nondecreasing heights from that ocean boundary to x, and vice versa.
Each ocean mask is exact
Boundary seeds initialize valid zero-move shore reachability. Reverse BFS preserves the path property and eventually discovers every cell with such a reverse path.
Intersection matches the requirement
A cell can reach both oceans exactly when it belongs to both independent masks. Union would include cells with only one ocean route. Row-major emission changes only output order, not membership.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
private static int validate(int[][] heights) {
Objects.requireNonNull(heights,"heights");int columns=heights.length==0?0:heights[0]==null?-1:heights[0].length;
for(int[] row:heights)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular heights");return columns;
}
private static boolean[][] reach(int[][] heights,int columns,boolean pacific) {
boolean[][] seen=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();
for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific?(r==0||c==0):(r==heights.length-1||c==columns-1)){seen[r][c]=true;queue.addLast(new int[]{r,c});}
while(!queue.isEmpty()) {
int[] cell=queue.removeFirst();
for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=heights.length||nc<0||nc>=columns||seen[nr][nc]||heights[nr][nc]<heights[cell[0]][cell[1]])continue;seen[nr][nc]=true;queue.addLast(new int[]{nr,nc});}
}
return seen;
}
public static List<List<Integer>> flow(int[][] heights) {
int columns=validate(heights);boolean[][] pacific=reach(heights,columns,true),atlantic=reach(heights,columns,false);List<List<Integer>> result=new ArrayList<>();
for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific[r][c]&&atlantic[r][c])result.add(new ArrayList<>(Arrays.asList(r,c)));
return result;
}
public static List<List<Integer>> baseline(int[][] heights) {
int columns=validate(heights);List<List<Integer>> result=new ArrayList<>();
for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++) {
boolean[][] visited=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean pacific=false,atlantic=false;
while(!queue.isEmpty()){int[] cell=queue.removeFirst();pacific|=cell[0]==0||cell[1]==0;atlantic|=cell[0]==heights.length-1||cell[1]==columns-1;if(pacific&&atlantic)break;for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<heights.length&&nc>=0&&nc<columns&&!visited[nr][nc]&&heights[nr][nc]<=heights[cell[0]][cell[1]]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}}
if(pacific&&atlantic)result.add(new ArrayList<>(Arrays.asList(r,c)));
}
return result;
}
}
Read the meaningful blocks
Use >= when reversing
Strict > would incorrectly block equal-height plateaus.
Compare directly at integer extremes
Subtracting MIN from MAX can overflow and reverse the ordering.
Keep both masks
One combined visited bit erases whether Pacific, Atlantic, or both certified a cell; separate ownership is essential.
Complexity
Let R be row count, B total cells, and N=R+B, so validation/row allocation still count when rows have zero columns. Main time and auxiliary reachability/frontier storage are O(N). Two ocean traversals are a constant factor; each coordinate is claimed at most once per ocean. Returned Q coordinate lists take O(Q+1) output storage.
The forward-per-cell baseline takes O(N(B+1)) worst-case time and O(N) peak visited/frontier workspace, excluding its O(Q+1) output. Mutable coordinate rows are independent, rather than aliases of one reused pair.
Exact-state walkthroughs
Reveal normal and boundary traces
Two independent reverse-flow searches
Input: [[1,2,2],[3,2,3],[2,4,5]] · Both-ocean coordinates: [[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Step 1 of 28: Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
- (0, 1)
- (0, 2)
- (1, 0)
- (2, 0)
Active ocean: pacific. Reverse edges move to greater or equal heights.
Pacific mask — top or left shore reachable
Atlantic mask — bottom or right shore reachable
Completed intersection coordinates — row-major order
Empty.
✓ = certified reachable; · = not certified in this mask. Each ocean owns its own mask. The output appears after both searches finish; a union would include cells reaching only one shore.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[1,2,2],[3,2,3],[2,4,5]] |
| grid | [[1,2,2],[3,2,3],[2,4,5]] |
| queue | [[0,0],[0,1],[0,2],[1,0],[2,0]] |
| pacific | [[true,true,true],[true,false,false],[true,false,false]] |
| atlantic | [[false,false,false],[false,false,false],[false,false,false]] |
| ocean | "pacific" |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] heights) { 5 Objects.requireNonNull(heights,"heights");int columns=heights.length==0?0:heights[0]==null?-1:heights[0].length; 6 for(int[] row:heights)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular heights");return columns; 7 } 8 private static boolean[][] reach(int[][] heights,int columns,boolean pacific) { 9 boolean[][] seen=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>(); 10 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific?(r==0||c==0):(r==heights.length-1||c==columns-1)){seen[r][c]=true;queue.addLast(new int[]{r,c});} 11 while(!queue.isEmpty()) { 12 int[] cell=queue.removeFirst(); 13 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=heights.length||nc<0||nc>=columns||seen[nr][nc]||heights[nr][nc]<heights[cell[0]][cell[1]])continue;seen[nr][nc]=true;queue.addLast(new int[]{nr,nc});} 14 } 15 return seen; 16 } 17 public static List<List<Integer>> flow(int[][] heights) { 18 int columns=validate(heights);boolean[][] pacific=reach(heights,columns,true),atlantic=reach(heights,columns,false);List<List<Integer>> result=new ArrayList<>(); 19 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific[r][c]&&atlantic[r][c])result.add(new ArrayList<>(Arrays.asList(r,c))); 20 return result; 21 } 22 public static List<List<Integer>> baseline(int[][] heights) { 23 int columns=validate(heights);List<List<Integer>> result=new ArrayList<>(); 24 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++) { 25 boolean[][] visited=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean pacific=false,atlantic=false; 26 while(!queue.isEmpty()){int[] cell=queue.removeFirst();pacific|=cell[0]==0||cell[1]==0;atlantic|=cell[0]==heights.length-1||cell[1]==columns-1;if(pacific&&atlantic)break;for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<heights.length&&nc>=0&&nc<columns&&!visited[nr][nc]&&heights[nr][nc]<=heights[cell[0]][cell[1]]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}} 27 if(pacific&&atlantic)result.add(new ArrayList<>(Arrays.asList(r,c))); 28 } 29 return result; 30 } 31 } 32
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[0,0],[0,1],[0,2],[1,0],[2,0]]- pacific
[[true,true,true],[true,false,false],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[0,1],[0,2],[1,0],[2,0]]- pacific
[[true,true,true],[true,false,false],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[0,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[0,2],[1,0],[2,0]]- pacific
[[true,true,true],[true,false,false],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[0,1]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[0,2],[1,0],[2,0],[1,1]]- pacific
[[true,true,true],[true,true,false],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"claim"- current
[0,1]- claimed
[1,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,0],[2,0],[1,1]]- pacific
[[true,true,true],[true,true,false],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[0,2]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,0],[2,0],[1,1],[1,2]]- pacific
[[true,true,true],[true,true,true],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"claim"- current
[0,2]- claimed
[1,2]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,0],[1,1],[1,2]]- pacific
[[true,true,true],[true,true,true],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[1,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,1],[1,2]]- pacific
[[true,true,true],[true,true,true],[true,false,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[2,0]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,1],[1,2],[2,1]]- pacific
[[true,true,true],[true,true,true],[true,true,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"claim"- current
[2,0]- claimed
[2,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,2],[2,1]]- pacific
[[true,true,true],[true,true,true],[true,true,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[1,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,1]]- pacific
[[true,true,true],[true,true,true],[true,true,false]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[1,2]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,1],[2,2]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"claim"- current
[1,2]- claimed
[2,2]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,2]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[2,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,false,false],[false,false,false],[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[2,2]
- Seed the atlantic boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[0,2],[1,2],[2,0],[2,1],[2,2]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,false,true],[false,false,true],[true,true,true]]- ocean
"atlantic"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,2],[2,0],[2,1],[2,2]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,false,true],[false,false,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,2]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,2],[2,0],[2,1],[2,2],[0,1]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[false,false,true],[true,true,true]]- ocean
"atlantic"- phase
"claim"- current
[0,2]- claimed
[0,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,0],[2,1],[2,2],[0,1]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[false,false,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,2]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,1],[2,2],[0,1]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[false,false,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[2,0]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,1],[2,2],[0,1],[1,0]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,false,true],[true,true,true]]- ocean
"atlantic"- phase
"claim"- current
[2,0]- claimed
[1,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[2,2],[0,1],[1,0]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,false,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[2,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[0,1],[1,0]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,false,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[2,2]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,0]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,false,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,1]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,0],[1,1]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,true,true],[true,true,true]]- ocean
"atlantic"- phase
"claim"- current
[0,1]- claimed
[1,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[[1,1]]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,true,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,true,true],[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,1]
- Intersect the two completed masks in row-major order.
Union would accept cells reaching only one ocean. Java allocates independent mutable coordinate rows.
- source
[[1,2,2],[3,2,3],[2,4,5]]- grid
[[1,2,2],[3,2,3],[2,4,5]]- queue
[]- pacific
[[true,true,true],[true,true,true],[true,true,true]]- atlantic
[[false,true,true],[true,true,true],[true,true,true]]- ocean
"atlantic"- phase
"intersection"- current
null- coordinates
[[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
[[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Direct comparisons at int extremes
Input: [[-2147483648,2147483647],[2147483647,-2147483648]] · Both-ocean coordinates: [[0,1],[1,0]]
Step 1 of 10: Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
Phase: seed.
Unchanged source grid
MIN = −2,147,483,648; MAX = 2,147,483,647. Their meaning follows this problem’s legend.
Coordinate queue — front at left; already claimed
- (0, 0)
- (0, 1)
- (1, 0)
Active ocean: pacific. Reverse edges move to greater or equal heights.
Pacific mask — top or left shore reachable
Atlantic mask — bottom or right shore reachable
Completed intersection coordinates — row-major order
Empty.
✓ = certified reachable; · = not certified in this mask. Each ocean owns its own mask. The output appears after both searches finish; a union would include cells reaching only one shore.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[-2147483648,2147483647],[2147483647,-2147483648]] |
| grid | [[-2147483648,2147483647],[2147483647,-2147483648]] |
| queue | [[0,0],[0,1],[1,0]] |
| pacific | [[true,true],[true,false]] |
| atlantic | [[false,false],[false,false]] |
| ocean | "pacific" |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] heights) { 5 Objects.requireNonNull(heights,"heights");int columns=heights.length==0?0:heights[0]==null?-1:heights[0].length; 6 for(int[] row:heights)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular heights");return columns; 7 } 8 private static boolean[][] reach(int[][] heights,int columns,boolean pacific) { 9 boolean[][] seen=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>(); 10 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific?(r==0||c==0):(r==heights.length-1||c==columns-1)){seen[r][c]=true;queue.addLast(new int[]{r,c});} 11 while(!queue.isEmpty()) { 12 int[] cell=queue.removeFirst(); 13 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=heights.length||nc<0||nc>=columns||seen[nr][nc]||heights[nr][nc]<heights[cell[0]][cell[1]])continue;seen[nr][nc]=true;queue.addLast(new int[]{nr,nc});} 14 } 15 return seen; 16 } 17 public static List<List<Integer>> flow(int[][] heights) { 18 int columns=validate(heights);boolean[][] pacific=reach(heights,columns,true),atlantic=reach(heights,columns,false);List<List<Integer>> result=new ArrayList<>(); 19 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific[r][c]&&atlantic[r][c])result.add(new ArrayList<>(Arrays.asList(r,c))); 20 return result; 21 } 22 public static List<List<Integer>> baseline(int[][] heights) { 23 int columns=validate(heights);List<List<Integer>> result=new ArrayList<>(); 24 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++) { 25 boolean[][] visited=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean pacific=false,atlantic=false; 26 while(!queue.isEmpty()){int[] cell=queue.removeFirst();pacific|=cell[0]==0||cell[1]==0;atlantic|=cell[0]==heights.length-1||cell[1]==columns-1;if(pacific&&atlantic)break;for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<heights.length&&nc>=0&&nc<columns&&!visited[nr][nc]&&heights[nr][nc]<=heights[cell[0]][cell[1]]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}} 27 if(pacific&&atlantic)result.add(new ArrayList<>(Arrays.asList(r,c))); 28 } 29 return result; 30 } 31 } 32
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[[0,0],[0,1],[1,0]]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[[0,1],[1,0]]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[0,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[[1,0]]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[0,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[1,0]
- Seed the atlantic boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[[0,1],[1,0],[1,1]]- pacific
[[true,true],[true,false]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[[1,0],[1,1]]- pacific
[[true,true],[true,false]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[[1,1]]- pacific
[[true,true],[true,false]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[]- pacific
[[true,true],[true,false]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,1]
- Intersect the two completed masks in row-major order.
Union would accept cells reaching only one ocean. Java allocates independent mutable coordinate rows.
- source
[[-2147483648,2147483647],[2147483647,-2147483648]]- grid
[[-2147483648,2147483647],[2147483647,-2147483648]]- queue
[]- pacific
[[true,true],[true,false]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"intersection"- current
null- coordinates
[[0,1],[1,0]]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
[[0,1],[1,0]]
Equal-height plateau drains both ways
Input: [[5,5],[5,5]] · Both-ocean coordinates: [[0,0],[0,1],[1,0],[1,1]]
Step 1 of 14: Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
- (0, 1)
- (1, 0)
Active ocean: pacific. Reverse edges move to greater or equal heights.
Pacific mask — top or left shore reachable
Atlantic mask — bottom or right shore reachable
Completed intersection coordinates — row-major order
Empty.
✓ = certified reachable; · = not certified in this mask. Each ocean owns its own mask. The output appears after both searches finish; a union would include cells reaching only one shore.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[5,5],[5,5]] |
| grid | [[5,5],[5,5]] |
| queue | [[0,0],[0,1],[1,0]] |
| pacific | [[true,true],[true,false]] |
| atlantic | [[false,false],[false,false]] |
| ocean | "pacific" |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] heights) { 5 Objects.requireNonNull(heights,"heights");int columns=heights.length==0?0:heights[0]==null?-1:heights[0].length; 6 for(int[] row:heights)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular heights");return columns; 7 } 8 private static boolean[][] reach(int[][] heights,int columns,boolean pacific) { 9 boolean[][] seen=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>(); 10 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific?(r==0||c==0):(r==heights.length-1||c==columns-1)){seen[r][c]=true;queue.addLast(new int[]{r,c});} 11 while(!queue.isEmpty()) { 12 int[] cell=queue.removeFirst(); 13 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=heights.length||nc<0||nc>=columns||seen[nr][nc]||heights[nr][nc]<heights[cell[0]][cell[1]])continue;seen[nr][nc]=true;queue.addLast(new int[]{nr,nc});} 14 } 15 return seen; 16 } 17 public static List<List<Integer>> flow(int[][] heights) { 18 int columns=validate(heights);boolean[][] pacific=reach(heights,columns,true),atlantic=reach(heights,columns,false);List<List<Integer>> result=new ArrayList<>(); 19 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific[r][c]&&atlantic[r][c])result.add(new ArrayList<>(Arrays.asList(r,c))); 20 return result; 21 } 22 public static List<List<Integer>> baseline(int[][] heights) { 23 int columns=validate(heights);List<List<Integer>> result=new ArrayList<>(); 24 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++) { 25 boolean[][] visited=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean pacific=false,atlantic=false; 26 while(!queue.isEmpty()){int[] cell=queue.removeFirst();pacific|=cell[0]==0||cell[1]==0;atlantic|=cell[0]==heights.length-1||cell[1]==columns-1;if(pacific&&atlantic)break;for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<heights.length&&nc>=0&&nc<columns&&!visited[nr][nc]&&heights[nr][nc]<=heights[cell[0]][cell[1]]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}} 27 if(pacific&&atlantic)result.add(new ArrayList<>(Arrays.asList(r,c))); 28 } 29 return result; 30 } 31 } 32
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[0,0],[0,1],[1,0]]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[0,1],[1,0]]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[0,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[1,0]]- pacific
[[true,true],[true,false]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[0,1]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[1,0],[1,1]]- pacific
[[true,true],[true,true]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"claim"- current
[0,1]- claimed
[1,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[1,1]]- pacific
[[true,true],[true,true]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[1,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[]- pacific
[[true,true],[true,true]]- atlantic
[[false,false],[false,false]]- ocean
"pacific"- phase
"visit"- current
[1,1]
- Seed the atlantic boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[0,1],[1,0],[1,1]]- pacific
[[true,true],[true,true]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[1,0],[1,1]]- pacific
[[true,true],[true,true]]- atlantic
[[false,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,1]
- Reverse a valid nonincreasing water-flow edge.
Equal-height plateaus are traversable. Direct comparisons avoid subtracting int extremes.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[1,0],[1,1],[0,0]]- pacific
[[true,true],[true,true]]- atlantic
[[true,true],[true,true]]- ocean
"atlantic"- phase
"claim"- current
[0,1]- claimed
[0,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[1,1],[0,0]]- pacific
[[true,true],[true,true]]- atlantic
[[true,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[[0,0]]- pacific
[[true,true],[true,true]]- atlantic
[[true,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[1,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[]- pacific
[[true,true],[true,true]]- atlantic
[[true,true],[true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,0]
- Intersect the two completed masks in row-major order.
Union would accept cells reaching only one ocean. Java allocates independent mutable coordinate rows.
- source
[[5,5],[5,5]]- grid
[[5,5],[5,5]]- queue
[]- pacific
[[true,true],[true,true]]- atlantic
[[true,true],[true,true]]- ocean
"atlantic"- phase
"intersection"- current
null- coordinates
[[0,0],[0,1],[1,0],[1,1]]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
[[0,0],[0,1],[1,0],[1,1]]
One row touches both oceans
Input: [[3,1,2]] · Both-ocean coordinates: [[0,0],[0,1],[0,2]]
Step 1 of 10: Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
- (0, 1)
- (0, 2)
Active ocean: pacific. Reverse edges move to greater or equal heights.
Pacific mask — top or left shore reachable
Atlantic mask — bottom or right shore reachable
Completed intersection coordinates — row-major order
Empty.
✓ = certified reachable; · = not certified in this mask. Each ocean owns its own mask. The output appears after both searches finish; a union would include cells reaching only one shore.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[3,1,2]] |
| grid | [[3,1,2]] |
| queue | [[0,0],[0,1],[0,2]] |
| pacific | [[true,true,true]] |
| atlantic | [[false,false,false]] |
| ocean | "pacific" |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] heights) { 5 Objects.requireNonNull(heights,"heights");int columns=heights.length==0?0:heights[0]==null?-1:heights[0].length; 6 for(int[] row:heights)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular heights");return columns; 7 } 8 private static boolean[][] reach(int[][] heights,int columns,boolean pacific) { 9 boolean[][] seen=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>(); 10 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific?(r==0||c==0):(r==heights.length-1||c==columns-1)){seen[r][c]=true;queue.addLast(new int[]{r,c});} 11 while(!queue.isEmpty()) { 12 int[] cell=queue.removeFirst(); 13 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=heights.length||nc<0||nc>=columns||seen[nr][nc]||heights[nr][nc]<heights[cell[0]][cell[1]])continue;seen[nr][nc]=true;queue.addLast(new int[]{nr,nc});} 14 } 15 return seen; 16 } 17 public static List<List<Integer>> flow(int[][] heights) { 18 int columns=validate(heights);boolean[][] pacific=reach(heights,columns,true),atlantic=reach(heights,columns,false);List<List<Integer>> result=new ArrayList<>(); 19 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific[r][c]&&atlantic[r][c])result.add(new ArrayList<>(Arrays.asList(r,c))); 20 return result; 21 } 22 public static List<List<Integer>> baseline(int[][] heights) { 23 int columns=validate(heights);List<List<Integer>> result=new ArrayList<>(); 24 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++) { 25 boolean[][] visited=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean pacific=false,atlantic=false; 26 while(!queue.isEmpty()){int[] cell=queue.removeFirst();pacific|=cell[0]==0||cell[1]==0;atlantic|=cell[0]==heights.length-1||cell[1]==columns-1;if(pacific&&atlantic)break;for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<heights.length&&nc>=0&&nc<columns&&!visited[nr][nc]&&heights[nr][nc]<=heights[cell[0]][cell[1]]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}} 27 if(pacific&&atlantic)result.add(new ArrayList<>(Arrays.asList(r,c))); 28 } 29 return result; 30 } 31 } 32
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[[0,0],[0,1],[0,2]]- pacific
[[true,true,true]]- atlantic
[[false,false,false]]- ocean
"pacific"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[[0,1],[0,2]]- pacific
[[true,true,true]]- atlantic
[[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[0,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[[0,2]]- pacific
[[true,true,true]]- atlantic
[[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[0,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[]- pacific
[[true,true,true]]- atlantic
[[false,false,false]]- ocean
"pacific"- phase
"visit"- current
[0,2]
- Seed the atlantic boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[[0,0],[0,1],[0,2]]- pacific
[[true,true,true]]- atlantic
[[true,true,true]]- ocean
"atlantic"- phase
"seed"- current
null
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[[0,1],[0,2]]- pacific
[[true,true,true]]- atlantic
[[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,0]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[[0,2]]- pacific
[[true,true,true]]- atlantic
[[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,1]
- Expand this ocean’s reverse-flow frontier.
A visited cell can flow forward to this ocean; no assumption is made yet about the other ocean.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[]- pacific
[[true,true,true]]- atlantic
[[true,true,true]]- ocean
"atlantic"- phase
"visit"- current
[0,2]
- Intersect the two completed masks in row-major order.
Union would accept cells reaching only one ocean. Java allocates independent mutable coordinate rows.
- source
[[3,1,2]]- grid
[[3,1,2]]- queue
[]- pacific
[[true,true,true]]- atlantic
[[true,true,true]]- ocean
"atlantic"- phase
"intersection"- current
null- coordinates
[[0,0],[0,1],[0,2]]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
[[0,0],[0,1],[0,2]]
Empty heights
Input: [] · Both-ocean coordinates: []
Step 1 of 4: Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
Phase: seed.
Unchanged source grid
No cells.
Coordinate queue — front at left; already claimed
Empty.
Active ocean: pacific. Reverse edges move to greater or equal heights.
Pacific mask — top or left shore reachable
No cells.
Atlantic mask — bottom or right shore reachable
No cells.
Completed intersection coordinates — row-major order
Empty.
✓ = certified reachable; · = not certified in this mask. Each ocean owns its own mask. The output appears after both searches finish; a union would include cells reaching only one shore.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [] |
| grid | [] |
| queue | [] |
| pacific | [] |
| atlantic | [] |
| ocean | "pacific" |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] heights) { 5 Objects.requireNonNull(heights,"heights");int columns=heights.length==0?0:heights[0]==null?-1:heights[0].length; 6 for(int[] row:heights)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular heights");return columns; 7 } 8 private static boolean[][] reach(int[][] heights,int columns,boolean pacific) { 9 boolean[][] seen=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>(); 10 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific?(r==0||c==0):(r==heights.length-1||c==columns-1)){seen[r][c]=true;queue.addLast(new int[]{r,c});} 11 while(!queue.isEmpty()) { 12 int[] cell=queue.removeFirst(); 13 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=heights.length||nc<0||nc>=columns||seen[nr][nc]||heights[nr][nc]<heights[cell[0]][cell[1]])continue;seen[nr][nc]=true;queue.addLast(new int[]{nr,nc});} 14 } 15 return seen; 16 } 17 public static List<List<Integer>> flow(int[][] heights) { 18 int columns=validate(heights);boolean[][] pacific=reach(heights,columns,true),atlantic=reach(heights,columns,false);List<List<Integer>> result=new ArrayList<>(); 19 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++)if(pacific[r][c]&&atlantic[r][c])result.add(new ArrayList<>(Arrays.asList(r,c))); 20 return result; 21 } 22 public static List<List<Integer>> baseline(int[][] heights) { 23 int columns=validate(heights);List<List<Integer>> result=new ArrayList<>(); 24 for(int r=0;r<heights.length;r++)for(int c=0;c<columns;c++) { 25 boolean[][] visited=new boolean[heights.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean pacific=false,atlantic=false; 26 while(!queue.isEmpty()){int[] cell=queue.removeFirst();pacific|=cell[0]==0||cell[1]==0;atlantic|=cell[0]==heights.length-1||cell[1]==columns-1;if(pacific&&atlantic)break;for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<heights.length&&nc>=0&&nc<columns&&!visited[nr][nc]&&heights[nr][nc]<=heights[cell[0]][cell[1]]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}} 27 if(pacific&&atlantic)result.add(new ArrayList<>(Arrays.asList(r,c))); 28 } 29 return result; 30 } 31 } 32
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the pacific boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[]- grid
[]- queue
[]- pacific
[]- atlantic
[]- ocean
"pacific"- phase
"seed"- current
null
- Seed the atlantic boundary for reverse reachability.
Each ocean owns a separate reachability mask. Reverse traversal goes to greater or equal height, the inverse of legal downhill flow.
- source
[]- grid
[]- queue
[]- pacific
[]- atlantic
[]- ocean
"atlantic"- phase
"seed"- current
null
- Intersect the two completed masks in row-major order.
Union would accept cells reaching only one ocean. Java allocates independent mutable coordinate rows.
- source
[]- grid
[]- queue
[]- pacific
[]- atlantic
[]- ocean
"atlantic"- phase
"intersection"- current
null- coordinates
[]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
[]
Test the contract
Input:
Empty or zero-column grid
Output:[]No source cells.
Input:
Single row/column
Output:all coordinatesEvery cell touches both ocean border definitions.
Input:
Equal-height plateau
Output:all shore-connected plateau cellsEquality is allowed.
Input:
MIN/MAX opposite corners
Output:only the two high cross-corner cellsNo subtraction overflow.
Common mistakes and counterexamples
Use downhill moves from the ocean
Counterexample: That finds cells water could flow into from the shore, not cells that can drain to it.
Reverse to greater/equal neighbors.
Use union of reachability masks
Counterexample: A cell reaching only Pacific is insufficient.
Require both flags.
Forbid equal heights
Counterexample: Flat connected plateaus can drain to both sides.
Allow equality in both forward and reverse flow rules.
Sort by height instead of output coordinates
Counterexample: The contract requests row-major coordinate order, not elevation order.
Scan rows then columns after reachability is complete.
Follow-ups
Return one route to each ocean.
Record reverse-search parents separately for each ocean and follow them from an accepted cell toward its shore. Account for route output size and define tie order.
Require strictly downhill flow.
Reverse with strictly greater heights and change plateau examples. Shore cells still reach their own ocean in zero moves.
Support many different target shores.
One mask per target set costs one traversal each. For many queries consider bitset propagation or a condensed graph, but prove how equal-height cycles are represented.