class Solution {
    /**
    * Key Observation: Water can flow from cell A → B if: height[B] ≤ height[A]
    * Instead of simulating water from every cell to the ocean (very expensive), we reverse the flow:
    * We move from ocean → inside and only go to cells with equal or greater height.
        height[next] >= height[current] - This tells us which cells can reach the ocean.
    * We maintain two visited matrices:
        pacific[n][m]   -> cells that can reach Pacific
        atlantic[n][m]  -> cells that can reach Atlantic
    * Start DFS From Ocean Borders
        Pacific Ocean touches:
            Top row
            Left column
        So run DFS from: (i,0)  for all rows (0,j)  for all columns
        Mark all reachable cells in pacific.
        Atlantic Ocean touches:
            Last row
            Right column
        So run DFS from: (n-1,j)  for all rows (i,m-1)  for all columns
        Mark all reachable cells in Atlantic.
    * DFS moves to neighbors only if height is increasing or equal.
        Condition preventing DFS:
        1. Out of bounds
        2. Already visited
        3. Next height < previous height
    * Explore All 4 Directions
        From every cell we visit:
        down   -> (i+1, j)
        right  -> (i, j+1)
        left   -> (i, j-1)
        up     -> (i-1, j)
    
    Find Cells That Reach Both Oceans
        Finally iterate the grid:
            if(pacific[i][j] && atlantic[i][j])
                add to result
    */
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();

        int n = heights.length;
        int m = heights[0].length;
        boolean[][] pacific = new boolean[n][m];
        boolean[][] atlantic = new boolean[n][m];

        for(int i=0; i<n ;i++)
        {
            // 0th column
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, pacific, i, 0, -1, -1, n, m);

            // last column
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, atlantic, i, m-1, -1, -1, n, m);
        }

        for(int j=0; j<m ;j++)
        {
            // 0th row
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, pacific, 0, j, -1, -1, n, m);

            // last row
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, atlantic, n-1, j, -1, -1, n, m);
        }

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(pacific[i][j] == true && atlantic[i][j] == true)
                {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    if(!res.contains(temp))
                        res.add(temp);
                }
            }
        }
        return res;
    }

    public void markCells(int[][] heights, boolean[][] visited, int i, int j, int oldi, int oldj, int n, int m)
    {
        // if the current height is less than or equal to the old cell's height then water can't flow
        if(i < 0 || j < 0 || i >= n || j >= m || visited[i][j] == true || 
            (oldi >=0 && oldj >=0 && heights[oldi][oldj] > heights[i][j]))
            return;
        
        visited[i][j] = true;
        // visiting in all 4-directions
        markCells(heights, visited, i+1, j, i, j, n, m);
        markCells(heights, visited, i, j+1, i, j, n, m);
        markCells(heights, visited, i, j-1, i, j, n, m);
        markCells(heights, visited, i-1, j, i, j, n, m);
    }
}