Why we reverse? Intuition from brute-force to optimized
Going through discussion tab and youtube folks found that a lot of people start an explanation like this:\n\n"Let us reverse logic in this problem."\n"It should
Going through discussion tab and youtube folks found that a lot of people start an explanation like this:\n\n"Let us **reverse logic** in this problem."\n"It should be **obvious** from the start that we\'ll need to solve this problem **in reverse**."\n\nThose all are smart folks and for them "it\'s quite **obvious** what to do", but for me it was not and I had to scratch the back of my head a bit. I\'ll write down how I ended up with the same solution.\n\nThis is the first thing that came to my mind.\n\n**1. Brute-force**\n\nAs I want to find **the shortest path** to an ocean from a [row,col] cell I picked BFS graph traversal.\nAccording to the problem statement the water from the [row,col] cell should **end up in both Pacific and Atlantic** oceans. So we will need 2 sets to track this requirements.\n\nWe go from a "land" cell to out of boundaries `row < 0 or row > ROWS or col < 0 or col > COLS`\n\n**Observation #1**: The first observation that I got is that as soon as we reach a border cell (marked with pink on the pic) - we definitely end up in an ocean. Think about an ocean cell as the one with height = 0.\n\n**Observation #2**: Bottom-left and top-right land cells end up in both oceans. They have the same coordinates adjacent to both oceans\n\n![image](https://assets.leetcode.com/users/images/f016131b-80ab-41fa-b96e-a6938d7a3f5c_1662242543.9600108.png)\n\nI start a BFS traversal for every possible [row,col] combination and when I am on a "border cell" I store *traversal_starting_position* in a *reached_X_ocean* set. This is how I check a "border cell" position\n```\nif r == 0 or c == 0:\n    reached_pacific_ocean.add(traversal_starting_position)\nif r == ROWS - 1 or c == COLS - 1:\n    reached_atlantic_ocean.add(traversal_starting_position)\n```\n\nWhen I am done with the traversals I check which cells ended up in both oceans and return them.\n\nThis approach will work, but will be slow - `O(ROWS*COLS)^2)`\n\n![image](https://assets.leetcode.com/users/images/6105af16-7f4d-4ed8-adae-95659f95fc4e_1662234754.5888665.png)\n\nSource code for the approach:\n```\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        def bfs(traversal_starting_position):\n            queue = deque([traversal_starting_position])\n            visited = set()\n            \n            while queue:\n                r,c = queue.popleft()\n                \n                if r == 0 or c == 0:\n\t\t\t\t    reached_pacific_ocean.add(traversal_starting_position)\n                if r == ROWS - 1 or c == COLS - 1:\n\t\t\t\t    reached_atlantic_ocean.add(traversal_starting_position)\n                \n                if traversal_starting_position in reached_atlantic_ocean and traversal_starting_position in reached_pacific_ocean:\n                    return\n                \n                for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:\n                    nr,nc = r + dr, c + dc\n                    \n                    if 0 <= nr < ROWS and 0 <= nc < COLS and heights[nr][nc] <= heights[r][c] \\\n                        and (nr,nc) not in visited:\n                        queue.append((nr,nc))\n                        visited.add((nr,nc))\n        \n        ROWS,COLS = len(heights), len(heights[0])\n        \n        reached_atlantic_ocean = set()\n        reached_pacific_ocean = set()\n        \n        for traversal_starting_position in product(range(ROWS), range(COLS)):\n            bfs(traversal_starting_position)\n        \n        return reached_atlantic_ocean & reached_pacific_ocean\n```\n\n**2. Optimizing brute-force**\n\nBy now we know a few things:\n* water flows top to bottom (physics 101)\n* If we got to a border cell, we are in the ocean\n* we used 2 sets to identify if a cell landed in both oceans\n* brute-forcing every [row.col] **is slow**\n\nLet\'s start from the last item from the list.\n\n**How can we speed it up?**\n\nIn order to speed it up we need to reduce number of *traversal_starting_position* checks, but how?\n\nLet\'s look at the example:\n\n```\n11112\n10001\n10401\n10001\n21111\n```\n\nIn our case no matter what we do, `4` will not reach any ocean. The same we can say about any of `0`. So it does not make any sence to check them. C\u0336r\u0336o\u0336s\u0336s\u0336i\u0336n\u0336g\u0336 \u0336o\u0336u\u0336t\u0336\n\n**How do we know which land cells can reach an ocean?**\n\nFrom the bruce-force approach\'s observation #1 and #2 we know that any border cell can reach an ocean and at least 2 border cells can reach both oceans.\n\nBased on the above information we need somehow to reach the border land cells. How?\n\nThe only 2 ways to reach a border cell:\n1) start from it \n2) **Observation #3**: arrive from a heigher (or equal) land cell adjacent to the border cell.\n\n![image](https://assets.leetcode.com/users/images/0b7e100f-4244-4c89-a2a8-3d6a561cc815_1662242903.9839532.png)\n\nIf we repeat the process again and again (looks like peeling an onion ring by ring) we will end up with land cells that we are stuck on and cannot go higher anymore.\n\nThis way we drop land cells that can\'t guide us to a possible solution as soon as possible.\n\n---\n\nThis is what we do in **Top-Down** approaches: you have your target (big goal) and you build a way to get there from smaller targets.\n\n---\n\nSo we need to track which land cells end up in which ocean and find intersecting coordinates in both atlantic and pacific sets and we are done.\n\n**How do we do it?**\n\nNow that we know what we need, left to figure out how to achive it.\n\n**1. We start from border cells**.\nWe split border cells in 2 groups: the ones that are adjacent to Pacific ocean and another one for Atlantic ocean. We need to know which border cell ended up in which ocean.\n\n**2. We start BFS traversion on those border cells**\nHow do we determine how to expand the BFS search space???\n\nOriginal state transition from the problem description:\n...*water can flow ... if the neighboring cell\'s height* \\*<=\\* *current cell\'s height..*\n\nBut we are going **from the bottom to the top**, so this needs to be **reversed** \n...*water can flow ... if the neighboring cell\'s height* \\*>=\\* *current cell\'s height..*\n\n**3. We got land cells that we cannot move heigher anymore**\nWe intersect such cells from both oceans and that\'s our result.\n\n**But it is still not optimized!!!**\n\nIn order to speed up the current approach we need somehow to run **in parallel** our BFS traversals for multiple starting coordinates. But good old BFS runs only sequentially for each starting point???\n\nLuckly for us there is (if you did not know, now you know) **multi-source BFS** (aka MS BFS, click [here](https://www.vldb.org/pvldb/vol8/p449-then.pdf) if you like papers).\n\nEach time you see that you need to **run BFS on MULTIPLE SOURCES at the SAME TIME** - it\'s 99.99% MS BFS (the other 0.01 is DP, but that\'s another problem). The same one is used in "Rotting Oranges" (amazon\'s fav), "Map of Highest Peak", "As Far from Land as Possible", "Pacific Atlantic Water Flow", "Wall and Gates" and others.\n\n---\n\nMore about similar problems and how to apply it I posted for another problem [here](https://leetcode.com/problems/as-far-from-land-as-possible/discuss/2515617/how-to-solve-multi-source-bfs-problems-intuition)\n\n---\n\nNow left to apply MS BFS to our problem and we are done.\n\n**Optimization with MS BFS**\n\nAs we need to start **in parallel** we need to prepare our "BFS queue" with the border land cells (sources) in advance. So we have to find all the border land cells and place them in the queue before staring the typical "BFS loop". This way we traverse multiple starting points **in parallel**.\n\nI like the idea of a "virtual start node" aka dummy on the pic: You virtually connect all the "land" cells to a virtual node and then do a classic BFS on the virtual node. Except this is the mental model. In the code you just find the "starting" source nodes and dump them in the queue and run a bfs on the queue.\n\n![image](https://assets.leetcode.com/users/images/4e361cdd-25d6-4bf7-8f1a-670a119ca8d3_1662245696.096896.png)\n*The pic as always taken from the Internet.*\n\nAs a result of running 2 BFS for both oceans we are going to have 2 **visited** sets, that contain all "reachable" land cells from border cells. We intersect the cell coordinates and return them.\n\n---\n\nSo, hopefully, by now we know why we need to **reverse the logic** and why it\'s **obvious**.\nThis is the same problem with solutions that provide tabular DP. You got 5 lines of code and no idea how they ended up there.\n\n---\n\nSource code for the approach:\n```\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        def bfs(queue):\n            visited = set(queue)\n            while queue:\n                r,c = queue.popleft()\n                \n                for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:\n                    nr,nc = r + dr, c + dc\n                    \n                    if 0 <= nr < ROWS and 0 <= nc < COLS and \\\n                        heights[r][c] <= heights[nr][nc] and (nr,nc) not in visited:\n                        visited.add((nr,nc))\n                        queue.append((nr,nc))\n            \n            return visited\n        \n        atlantic_ocean_queue = deque()\n        pacific_ocean_queue = deque()\n        \n        ROWS,COLS = len(heights),len(heights[0])\n        \n        for r in range(ROWS):\n            atlantic_ocean_queue.append((r, COLS - 1))\n            pacific_ocean_queue.append((r, 0))\n            \n        for c in range(COLS):\n            atlantic_ocean_queue.append((ROWS - 1, c))\n            pacific_ocean_queue.append((0, c))\n        \n        reached_atlantic_ocean = bfs(atlantic_ocean_queue)\n        reached_pacific_ocean = bfs(pacific_ocean_queue)\n        \n        return reached_atlantic_ocean & reached_pacific_ocean\n```\n\nTC: `O(ROWS*COLS)`\nSC: `O(ROWS*COLS)`\n\nIt can also be solved with DFS. The same core logic, different traversal, recursion (stack) and ...\n\n... did you know that you can optimize/solve the problem with DP? \n\n( \u25D1\u203F\u25D1)\u0254\u250F\uD83C\uDF5F--\uD83C\uDF54\u2511\u0669(^\u25E1^ )\n\n**If you liked the read, upvote so the other people can see it too.**
['Python']