[Python] 3 Approaches (brute-force, flood-fill) with explanations
----------------------------------\nApproach 1: Brute-force\nTLE : 111 / 113 test cases passed.\n----------------------------------\n---------------------------
----------------------------------\nApproach 1: Brute-force\nTLE : 111 / 113 test cases passed.\n----------------------------------\n----------------------------------\n\n**Idea:**\n\n- For each cell:\n\t- see if I can reach pacific \n\t- see if I can reach atlantic\n\t- if the answer is True for both -> add to result\n\n\n- Time: \n\t- main function : `O(m*n) `\n\t- helper : `O(E+V) `\n\t- Overall => `O(E^2 + V)` => `O((M*N)^2)`\n\t- Iterating over cells and trigger 2 bfs searchs on each cell. We could do better!\n\n\n```\ndef pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n    \n        # bfs helper 1:\n        def reachPacific(x,y): # - O(E+V)\n            if x == 0 or y == 0:\n                return True\n            \n            from collections import deque\n            q = deque()\n            q.append((x,y))\n            dirs = [(1,0), (0,1), (-1,0), (0,-1)]\n            visited = set()\n            while q:\n                for i in range(len(q)):\n                    x, y = q.popleft()\n                    if x == 0 or y == 0:\n                        return True # found my way to \n                    visited.add((x,y))\n                    \n                    for dir in dirs: # must only add nei that have less height - so that water falls to them\n                        newX, newY = x+dir[0], y+dir[1]\n                        if newX >= 0 and newX <= len(grid)-1 and newY >= 0 and newY <= len(grid[0])-1:   \n                            if (newX, newY) not in visited:\n                                if grid[newX][newY] <= grid[x][y]: # water can flow\n                                    q.append((newX, newY))\n            return False \n        \n\t\t# bfs helper 2:\n        def reachAtlantic(x,y): # - O(E+V)\n            grid = heights\n            \n            if x == len(grid)-1 or y == len(grid[0])-1:\n                return True\n            \n            from collections import deque\n            q = deque()\n            q.append((x,y))\n            dirs = [(1,0), (0,1), (-1,0), (0,-1)]\n            visited = set()\n            while q:\n                for i in range(len(q)):\n                    x, y = q.popleft()\n                    if x == len(grid)-1 or y == len(grid[0])-1:\n                        return True # found my way to \n                    visited.add((x,y))\n                    \n                    for dir in dirs: # must only add nei that have less height - so that water falls to them\n                        newX, newY = x+dir[0], y+dir[1]\n                        if newX >= 0 and newX <= len(grid)-1 and newY >= 0 and newY <= len(grid[0])-1:   \n                            if (newX, newY) not in visited:\n                                if grid[newX][newY] <= grid[x][y]: # water can flow\n                                    q.append((newX, newY))\n            return False \n        \n        # main:\n        grid = heights\n        res = []\n        for r in range(len(grid)): # - O(V) or O(M*N)\n            for c in range(len(grid[0])):\n                if reachPacific(r,c) and reachAtlantic(r,c):\n                    res.append([r,c])\n        return res\n\n```    \n\n----------------------------------------------\nApproach 2: Enhanced BFS (aka Flood-fill style BFS)\n----------------------------------\n----------------------------------\n\n**Idea:**\n1- flood-fill-style, simaltanous BFS from all pacific ocean cells\n2- flood-fill-style, simaltanous BFS from all atlantic ocean cells\n\n- start with 2 qeue : one for each ocean/cost\n- In order for a cell to flush its share of rain into the ocean, the cell has to have a higher altitude.\n- Hence, if a cell is higher than ocean cell -> include in ocean cell\nperform intersect between atlantic cells and pacific cells\n\n- Time: \n\t-  `O(M*N)`\n\n```        \n\ndef pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        \n\tgrid = heights\n    \n        # helper 1:\n        def findPacificCells(grid):\n            from collections import deque\n            q = deque()\n            visited = set()\n            \n            # num_rows, num_cols\n            numRows, numCols = len(grid), len(grid[0])\n        \n            # add all pacific cells\n            for i in range(numCols): # top row\n                q.append((0,i))\n                visited.add((0,i))\n            \n            for i in range(numRows): # left most col\n                q.append((i,0))\n                visited.add((i,0))\n            \n            dirs = [(1,0), (0,1), (-1,0), (0,-1)]\n            while q:\n                for i in range(len(q)):\n                    x, y = q.popleft()\n                    visited.add((x,y))\n                    \n                    for dir in dirs:\n                        newX, newY = x+dir[0], y+dir[1]\n                        if newX >= 0 and newX <= len(grid)-1 and newY >= 0 and newY <= len(grid[0])-1:\n                            if grid[newX][newY] >= grid[x][y]: # -- note [1]\n                                if (newX, newY) not in visited:\n                                    q.append((newX, newY))\n                    \n            # note [1]\n            # if new cell is higher -> means rain can flow from it to pacific -> hence include new cell in pacific\n            return visited\n            \n        # helper 2\n        def findAtlanticCells(grid):\n            \n            from collections import deque\n            q = deque()\n            visited = set()\n            \n            # num_rows, num_cols\n            numRows, numCols = len(grid), len(grid[0])\n            \n            # add all atlantic cells\n            for i in range(numCols): # bottom row\n                q.append((numRows-1,i))\n                visited.add((numRows-1,i))\n            \n            for i in range(len(grid)): # right most col\n                q.append((i,numCols-1))\n                visited.add((i,numCols-1))\n            \n            dirs = [(1,0), (0,1), (-1,0), (0,-1)]\n            while q:\n                for i in range(len(q)):\n                    x, y = q.popleft()\n                    visited.add((x,y))\n                    \n                    for dir in dirs:\n                        newX, newY = x+dir[0], y+dir[1]\n                        if newX >= 0 and newX <= len(grid)-1 and newY >= 0 and newY <= len(grid[0])-1:\n                            if grid[newX][newY] >= grid[x][y]: # -- note [1]\n                                if (newX, newY) not in visited:\n                                    q.append((newX, newY))\n                    \n            # note [1]\n            # if new cell is higher -> means rain can flow from it to pacific -> hence include new cell in pacific\n            return visited\n            \n        # main:\n        pacific = findPacificCells(grid)\n        atlantic = findAtlanticCells(grid)\n        mutual = pacific.intersection(atlantic)\n        \n        return list(mutual)\n```    \n    \n--------------------------------------------\nApproach 3 : Enhanced Flood-fill BFS\n--------------------------------------------\n--------------------------------------------\n- Instead of having 2 seperate functions: `findPacificCells` and `findAtlanticCells`\n- Use one bfs helper function on 2 different queues\n- Time: \n\t-  `O(M*N)`\n        \n```        \n def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n \n        # bfs helper\n        def bfs(q):\n            dirs = [(1,0), (0,1), (-1,0), (0,-1)]\n            visited = set()\n            while q:\n                for i in range(len(q)):\n                    x, y = q.popleft()\n                    visited.add((x,y))\n                    \n                    # expand to nei cell if nei cell is higher in atltitude\n                    for dir in dirs:\n                        newX, newY = x+dir[0], y+dir[1]\n                        if newX >= 0 and newX <= len(grid)-1 and newY >= 0 and newY <= len(grid[0])-1:\n                            if (newX, newY) not in visited:\n                                if grid[newX][newY] >= grid[x][y]: # water can flow from nei to x,y to ocean\n                                    q.append((newX, newY))\n            return visited\n                    \n        \n        # main\n        # initial queues - one for each cost/ocean\n        from collections import deque\n        qp = deque()\n        qa = deque()\n        \n        grid = heights\n        \n        # num_rows, num_cols\n        numRows, numCols = len(grid), len(grid[0])\n        \n        # 1) pacific:\n        for i in range(numCols): # top row\n            qp.append((0,i))\n        \n        for i in range(numRows): # left most col\n            qp.append((i,0))\n        \n        # 2) atlantic\n        for i in range(numRows): # right most col\n            qa.append((i,numCols-1))\n            \n        for i in range(numCols): # bottom row\n            qa.append((numRows-1, i))\n        \n        pacific = bfs(qp)\n        atlantic = bfs(qa)\n        mutual = pacific.intersection(atlantic)\n        return mutual\n```
['Python']