Learn and practice Tries, Graphs, Cyclic Sort, and Topological Sort patterns to solve coding interview problems.

Grokking the Blind 75 Problems in Java

In this module, we'll explore some advanced data structures and sorting techniques to help us solve challenging coding interview questions. We'll start by mastering two advanced data structures: graphs and tries. Graphs are versatile data structures that tackle complex interconnected problems, while tries offer an elegant solution for scenarios where standard data structures fall short. Next, we’ll explore two advanced sorting algorithms: Cyclic Sort and Topological Sort. Cyclic Sort is used when specific constraints on the input are met, making it the most efficient sorting algorithm in such cases. Topological Sort leverages graph-based algorithms to handle partially ordered elements. We’ll learn to recognize when these advanced sorting techniques are applicable and how to leverage them effectively to solve complex problems. By completing this module, you’ll enhance your problem-solving toolkit and solidify your status as a standout candidate in technical interviews.

Advanced Data Structures and Sorting Techniques

#
## Statement

Imagine an island with a rectangular shape that touches both the Pacific and Atlantic oceans. The northern and western sides meet the Pacific, while the southern and eastern sides touch the Atlantic. This island is divided into square cells.

To depict the height above sea level of each cell, we use an integer matrix, `heights`, of size $(m \times n)$. Here, `heights[r][c]` represents the elevation of the cell at coordinate $(r, c)$.

When heavy rain pours down on the island every few months, water flows from the island to both the Pacific and Atlantic oceans. The path of flow depends on the heights of the cells. 

Consider a cell with a height of $9$ that's higher than or equal to its neighboring cells to the north, east, west, and south. This indicates that water can flow from this cell to adjacent ones. Similarly, this process is repeated until the flow of water either reaches the Pacific or Atlantic border or a cell that can not flow water to any of its neighbors.  If the flow of water starting from a cell can direct water to both the Pacific and Atlantic Ocean borders, we include it in the output.

> **Note:** Any cell adjacent to an ocean can channel water into the ocean.

With this information, your task is to return a 2-D array of coordinates. Each entry $(r_i, c_i)$ in this array indicates that rainwater can flow from the cell at coordinate $(r_i, c_i)$ to both the Pacific and Atlantic oceans.

**Constraints:**

* $m ==$ `heights.length`

* $n ==$ `heights[r].length`, where $0 \leq r \leq m$

* $1 \leq m$, $n \leq 200$

* $0 \leq$ `heights[r][c]` $\leq 10^5$

## Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

### Naive approach

A naive approach to this problem involves performing depth-first search (DFS) from each cell in the matrix to determine whether it can flow water to both the Pacific and Atlantic oceans. It starts with the first cell in the matrix and performs DFS to find all the cells that can be reached from it. If the path of water can reach both the Pacific and Atlantic oceans, the cell is marked as a solution. Then, the algorithm repeats this process for each cell to find all cells that can flow water to both oceans.

The time complexity of this approach is $O(n^2 \times m^2)$ since, in the worst case, the entire matrix would be traversed for each cell.

The space complexity of this approach is $O(1)$ since a constant number of additional variables are used.

### Optimized approach using Graphs

The idea stems from the observation that water flows downhill, seeking the lowest possible path. By starting the exploration from the ocean edges and traversing cells that are equal to or higher in elevation, we can identify regions where water can reach both the Pacific and Atlantic Oceans. The depth-first search (DFS) algorithm is chosen, since it naturally emulates the flow of water, exploring cells in a recursive manner and marking those that are reachable. The approach focuses on identifying cells that can be reached from both ocean edges, implying that water can flow in both directions and by finding the intersection of the sets of reachable cells from each ocean, the algorithm effectively pinpoints locations where water can flow to both oceans.

Here's how the algorithm works:

- We initialize the following variables to assist us in performing DFS:

   - `numRows`: This is the total number of rows in the matrix.

   - `numCols`: This is the total number of columns in the matrix.

   - `pacificReach`: This is a hash set that will contain the coordinates of the cells that can be reached from the Pacific ocean.

   - `atlanticReach`: This is a hash set that will contain the coordinates of the cells that can be reached from the Atlantic ocean.

- The `dfs` function has the following parameters:

   - `row`, `col`: The coordinates of the initial cell where DFS will begin.

   - `reach`: The hash set of the respective ocean for which DFS is called.

- Here's how the `dfs` function works:

   - The very first cell passed to the function will always be reachable since this cell is from the border of the matrix pertaining to the respective ocean. Therefore, the coordinates of this cell are added to `reach`.

   - For the cell above that has been added to `reach`, we perform DFS by exploring all four directions (top, bottom, left, right) from the cell. This is achieved through the use of a loop that adds the following coordinates to the current `(row, col)`:

      - `(1,0)`: The cell to the immediate top of the current cell is explored.

     - `(0,1)`: The cell to the immediate bottom of the current cell is explored.

      - `(-1,0)`: The cell to the immediate left of the current cell is explored.

      - `(0,-1)`: The cell to the immediate right of the current cell is explored.

   - The following conditions are checked for each cell that is explored:

      - If the cell is out of bounds, it is skipped since it doesn't exist in the matrix.


     - If the cell is already in `reach`, it is skipped since it has already been visited.

     - If the cell contains a height that is greater than the height of the previous cell, it is skipped since the previous cell can not be reached from this cell.

   - If the three conditions above are not satisfied, this means that the current cell is a valid cell on which we can continue DFS. So the `dfs` function is called again for this cell, where it is added to `reach`, and then its neighbors are explored again.

- The `dfs` function is then called for each cell of the Pacific and Atlantic border in the matrix, which populates `pacificReach` and `atlanticReach` with the coordinates of the cells that can flow water to the respective oceans.

- Finally, we determine the common coordinates in both `pacificReach` and `atlanticReach` and store them in the output array. These cells can flow water to both oceans, so we return the output array containing them.

The slides below illustrate how the algorithm runs:

Let's solve the Pacific Atlantic Water Flow problem using the Graphs pattern.

Solution: Pacific Atlantic Water Flow

Statement