Helpful DFS JavaScript solution
If you\'re like me, this may be the first DFS problem you\'ve ever come across. I looked at some answers, they broke my brain, and I had to leave and learn abou
If you\'re like me, this may be the first DFS problem you\'ve ever come across. I looked at some answers, they broke my brain, and I had to leave and learn about DFS and come back (which is a bit more difficult if JavaScript is your primary language). I\'d recommend doing that. But here is the solution I wish had existed.\n\nIn a nutshell, Depth First Search takes a starting point (node or vertex, in this problem one of the squares in the matrix) and checks to see if it can find a path*. It goes all along a path until it\'s reached the end (in contrast to BFS, which checks one next node around it at a time before moving on). If the function has visited a node, it marks it off its list and moves on, storing the result in an adjacency matrix (used here) or adjacency list.  This is the best explanation of the concept I\'ve seen: [https://xkcd.com/761/](http://)\n\n\\* *In this case, we\'ll write a dfs function to check if water can flow from a node adjacent to the ocean up to a high point--if that high point is found from both the pacific and atlantic oceans, it goes into our result. (Despite the problem statement of finding downhill flow, we must understand that the best approach to this problem is the opposite: starting at downhill points and working uphill.)*\n\nDFS can be implemented in several ways. Here we use recursion to check neighboring nodes. Stacks are also commonly used. \n\nThe fastest solution uses dynamic programming; you can find that solution in someone else\'s post on the discussion board. The solution here is currently the most comfortable for me, and I am confident that at my current level I could explain it at interview, but if that changes I will update this. It currently beats about 70%. \n\n```\nconst pacificAtlantic = (matrix) => {\n  if (!matrix.length) return [];\n  \n  let numRows = matrix.length;\n  let numCols = matrix[0].length;\n  \n  //create two adjacency matrices for results of atlantic and pacific dfs\n  //(if a node can reach an ocean, it goes in that matrix)\n  const pacific = new Array(numRows).fill().map(() => Array(numCols).fill(false))\n  const atlantic = new Array(numRows).fill().map(() => Array(numCols).fill(false))\n  \n  /*KEY POINT: dfs will be run from the ocean inwards, not vice versa\n  (from the ocean-adjacent nodes to the highest point(s))*/\n  \n  //dfs works by marking successfully visited squares in matrix as true\n  //remember we\'re going from ocean inland\n  const dfs = (r, c, current, ocean) =>{ //r=row c=column ocean=pacific/atlantic current=the node we\'re checking\n    //base case: return if out of bounds\n    if (r < 0 || c < 0 || r >= numRows || c >= numCols) return;\n    //base case: return if our current node is larger than the surrounding nodes, because we are only marking node as true if it is larger than the next...remember we are working upwards to the highest point. This is a bit confusing, but look at the inputs: when we run this recursively, below, if N, S, E, or W are less than the current node, we\'ll return, because they need to be HIGHER to work upwards.\n    if (matrix[r][c] < current) return;\n    //base case: return if this node already marked (in ocean), thus already visited\n    if (ocean[r][c]) return;\n    //if we\'re here it means the conditions have been successfully met and thus we can reach the ocean, so we mark this node true (water can flow here) in that ocean\n    ocean[r][c] = true;\n    //call dfs recursively on each of the surrounding cells (ie N,S,E,W)\n    dfs(r+1, c, matrix[r][c], ocean);\n    dfs(r-1, c, matrix[r][c], ocean);\n    dfs(r, c+1, matrix[r][c], ocean);\n    dfs(r, c-1, matrix[r][c], ocean);\n  };\n  \n  /*the pacfic touches the top and left sides of the matrix (N & E)\n  and the atlantic touches the right and bottom sides (W & S)\n  thus...*/\n  //we run DFS for the top and bottom rows\n  for (let col=0; col < numCols; col++){\n   dfs(0, col, Number.MIN_SAFE_INTEGER, pacific);\n   dfs(numRows-1, col, Number.MIN_SAFE_INTEGER, atlantic);\n  }\n  //and for the first and last columns\n  for (let row = 0; row < numRows; row++){\n    dfs(row, 0, Number.MIN_SAFE_INTEGER, pacific)\n    dfs(row, numCols-1, Number.MIN_SAFE_INTEGER, atlantic)\n  }\n\n  //add to result if exists in both pacific and atlantic\n  let result = [];\n  for (let i=0; i < numRows; i++){\n    for (let j=0; j < numCols; j++){\n      if (atlantic[i][j] && pacific[i][j]){\n        result.push([i, j]);\n      }\n    }\n  }\n  return result;\n};\n```
['JavaScript']