<p>There is an <code>m x n</code> rectangular island that borders both the <strong>Pacific Ocean</strong> and <strong>Atlantic Ocean</strong>. The <strong>Pacific Ocean</strong> touches the island&#39;s left and top edges, and the <strong>Atlantic Ocean</strong> touches the island&#39;s right and bottom edges.</p>

<p>The island is partitioned into a grid of square cells. You are given an <code>m x n</code> integer matrix <code>heights</code> where <code>heights[r][c]</code> represents the <strong>height above sea level</strong> of the cell at coordinate <code>(r, c)</code>.</p>

<p>The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell&#39;s height is <strong>less than or equal to</strong> the current cell&#39;s height. Water can flow from any cell adjacent to an ocean into the ocean.</p>

<p>Return <em>a <strong>2D list</strong> of grid coordinates </em><code>result</code><em> where </em><code>result[i] = [r<sub>i</sub>, c<sub>i</sub>]</code><em> denotes that rain water can flow from cell </em><code>(r<sub>i</sub>, c<sub>i</sub>)</code><em> to <strong>both</strong> the Pacific and Atlantic oceans</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg" style="width: 400px; height: 400px;" />
<pre>
<strong>Input:</strong> heights = [[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]]
<strong>Output:</strong> [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
<strong>Explanation:</strong> The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -&gt; Pacific Ocean 
&nbsp;      [0,4] -&gt; Atlantic Ocean
[1,3]: [1,3] -&gt; [0,3] -&gt; Pacific Ocean 
&nbsp;      [1,3] -&gt; [1,4] -&gt; Atlantic Ocean
[1,4]: [1,4] -&gt; [1,3] -&gt; [0,3] -&gt; Pacific Ocean 
&nbsp;      [1,4] -&gt; Atlantic Ocean
[2,2]: [2,2] -&gt; [1,2] -&gt; [0,2] -&gt; Pacific Ocean 
&nbsp;      [2,2] -&gt; [2,3] -&gt; [2,4] -&gt; Atlantic Ocean
[3,0]: [3,0] -&gt; Pacific Ocean 
&nbsp;      [3,0] -&gt; [4,0] -&gt; Atlantic Ocean
[3,1]: [3,1] -&gt; [3,0] -&gt; Pacific Ocean 
&nbsp;      [3,1] -&gt; [4,1] -&gt; Atlantic Ocean
[4,0]: [4,0] -&gt; Pacific Ocean 
       [4,0] -&gt; Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> heights = [[1]]
<strong>Output:</strong> [[0,0]]
<strong>Explanation:</strong> The water can flow from the only cell to the Pacific and Atlantic oceans.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == heights.length</code></li>
	<li><code>n == heights[r].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= heights[r][c] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        final_answers = []
        answers = []
        pacific_seen = set()
        atlantic_seen = set()
        pacific_queue = []
        atlantic_queue = []
        for i in range(len(heights)):
            row = []
            for j in range(len(heights[i])):
                row.append([False, False])
            answers.append(row)
        
        # Borders Pacific
        for i in range(len(answers[0])):
            answers[0][i][0] = True
            pacific_seen.add((0,i))
            pacific_queue.append((0,i))
        for i in range(len(answers)):
            answers[i][0][0] = True
            pacific_seen.add((i,0))
            pacific_queue.append((i,0))
        # Borders Atlantic
        for i in range(len(answers[-1])):
            answers[-1][i][1] = True
            atlantic_seen.add((len(answers)-1, i))
            atlantic_queue.append((len(answers)-1, i))
        for i in range(len(answers)):
            answers[i][-1][1] = True
            atlantic_seen.add((i, len(answers[0])-1))
            atlantic_queue.append((i, len(answers[0])-1))
        
        while pacific_queue:
            row, col = pacific_queue.pop(0)
            if row +1 < len(heights) and (row+1, col) not in pacific_seen and heights[row][col] <= heights[row+1][col]:
                answers[row+1][col][0] = True
                pacific_seen.add((row+1, col))
                pacific_queue.append((row+1, col))
            if row -1 >= 0 and (row-1, col) not in pacific_seen and heights[row][col] <= heights[row-1][col]:
                answers[row-1][col][0] = True
                pacific_seen.add((row-1, col))
                pacific_queue.append((row-1, col))
            if col +1 < len(heights[0]) and (row, col+1) not in pacific_seen and heights[row][col] <= heights[row][col+1]:
                answers[row][col+1][0] = True
                pacific_seen.add((row, col+1))
                pacific_queue.append((row, col+1))
            if col -1 >= 0 and (row, col-1) not in pacific_seen and heights[row][col] <= heights[row][col-1]:
                answers[row][col-1][0] = True
                pacific_seen.add((row, col-1))
                pacific_queue.append((row, col-1))
        while atlantic_queue:
            row, col = atlantic_queue.pop(0)
            if row +1 < len(heights) and (row+1, col) not in atlantic_seen and heights[row][col] <= heights[row+1][col]:
                answers[row+1][col][1] = True
                atlantic_seen.add((row+1, col))
                atlantic_queue.append((row+1, col))
            if row -1 >= 0 and (row-1, col) not in atlantic_seen and heights[row][col] <= heights[row-1][col]:
                answers[row-1][col][1] = True
                atlantic_seen.add((row-1, col))
                atlantic_queue.append((row-1, col))
            if col +1 < len(heights[0]) and (row, col+1) not in atlantic_seen and heights[row][col] <= heights[row][col+1]:
                answers[row][col+1][1] = True
                atlantic_seen.add((row, col+1))
                atlantic_queue.append((row, col+1))
            if col -1 >= 0 and (row, col-1) not in atlantic_seen and heights[row][col] <= heights[row][col-1]:
                answers[row][col-1][1] = True
                atlantic_seen.add((row, col-1))
                atlantic_queue.append((row, col-1))

        for i in range(len(answers)):
            for j in range(len(answers[i])):
                if answers[i][j][0] and answers[i][j][1]:
                    final_answers.append([i,j])
        return final_answers

18700