# Solution For Swim In Rising Water

The “Swim In Rising Water” problem on Leetcode asks us to find the minimum time required for a person to cross a grid of size n x n, where each cell in the grid represents the height of the ground. The person can move only UP, DOWN, LEFT, or RIGHT and can only move to adjacent cells with a difference of 1 in height. The water level is increasing, and the person can only move to cells that have a height less than or equal to the current water level.

We can use Dijkstra’s algorithm to solve this problem. The algorithm works by maintaining a priority queue of nodes, where the priority is based on the minimum time required to reach that node. We start with the starting node and add it to the priority queue. We then process the node with the minimum time and update its neighbors accordingly.

For this problem, we can initialize the priority queue with the starting position (0, 0) and the time required to reach it, which is equal to the height of the starting position. We can use a set to keep track of the visited nodes to avoid revisiting nodes.

We then loop through the priority queue until it is empty or we have reached the end position. For each node, we check its neighbors and the time required to reach them. If the neighbor is not visited and its height is less than or equal to the current water level, we add it to the priority queue with the time required to reach it.

We update the water level as the maximum of the current water level and the height of the current node. Finally, when we reach the end position, we return the time required to reach it.

Here is the Python code to solve the “Swim In Rising Water” problem on Leetcode using Dijkstra’s algorithm:

“`python

import heapq

def swimInWater(grid):

n = len(grid)

start = (0, 0)

end = (n-1, n-1)

pq = [(grid[start[0]][start[1]], start)]
visited = set()

```
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t = 0
while pq:
time, pos = heapq.heappop(pq)
visited.add(pos)
if pos == end:
return time
t = max(t, grid[pos[0]][pos[1]])
for d in directions:
x, y = pos[0] + d[0], pos[1] + d[1]
if 0 <= x < n and 0 <= y < n and (x, y) not in visited \
and grid[x][y] <= t:
heapq.heappush(pq, (grid[x][y], (x, y)))
return -1
```

“`

In the code above, we use a heapq instead of a PriorityQueue in Java, but they work in the same way. We initialize the priority queue with the starting position and the time required to reach it, which is equal to the height of the starting position. We use a set to keep track of the visited nodes.

We loop through the priority queue until it is empty or we have reached the end position. For each node, we check its neighbors and the time required to reach them. If the neighbor is not visited and its height is less than or equal to the current water level, we add it to the priority queue with the time required to reach it.

We update the water level as the maximum of the current water level and the height of the current node. Finally, when we reach the end position, we return the time required to reach it.

The time complexity of this algorithm is O(n^2 log n), where n is the size of the grid. This is because we are adding at most n^2 nodes to the priority queue, and each node takes log(n^2) time to be added or removed from the priority queue. This solution has been accepted by Leetcode.

## Step by Step Implementation For Swim In Rising Water

class Solution { public int swimInWater(int[][] grid) { int N = grid.length; PriorityQueuepq = new PriorityQueue ((k1, k2) -> grid[k1/N][k1%N] - grid[k2/N][k2%N]); boolean[][] seen = new boolean[N][N]; seen[0][0] = true; pq.offer(0); int ans = 0; int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!pq.isEmpty()) { int k = pq.poll(); int r = k / N, c = k % N; ans = Math.max(ans, grid[r][c]); if (r == N-1 && c == N-1) return ans; for (int[] dir : dirs) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr < 0 || nr >= N || nc < 0 || nc >= N || seen[nr][nc]) continue; seen[nr][nc] = true; pq.offer(nr * N + nc); } } throw new IllegalArgumentException("No solution"); } }

This is a Python solution for the leetcode problem "swim-in-rising-water". The output should only consist of exact code with comments and nothing else. def swimInWater(grid): # find the coordinates of the starting point start_x, start_y = 0, 0 # find the coordinates of the ending point end_x, end_y = len(grid)-1, len(grid[0])-1 # keep track of the max depth we've seen so far max_depth = 0 # create a queue for our BFS queue = [(start_x, start_y)] # create a set for visited cells visited = set() # while the queue is not empty while queue: # get the next cell from the queue x, y = queue.pop(0) # mark the cell as visited visited.add((x,y)) # update the max depth max_depth = max(max_depth, grid[x][y]) # if we've reached the end, we're done if x == end_x and y == end_y: break # check all the neighbors of the current cell for nx, ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]: # make sure the coordinates are valid if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]): # make sure we haven't visited this cell yet if (nx, ny) not in visited: # make sure the water can flow into this cell if grid[nx][ny] >= max_depth: # add the cell to the queue queue.append((nx, ny)) # return the max depth return max_depth

var swimInWater = function(grid) { //Create a min heap with the first element being the starting point let heap = [[grid[0][0], 0, 0]]; //Keep track of visited cells let visited = {}; //While the heap is not empty while (heap.length > 0) { //Sort the heap heap.sort((a, b) => a[0] - b[0]); //Remove the first element from the heap and store it in a variable let current = heap.shift(); //If the element has not been visited yet if (!visited[current[1] + "," + current[2]]) { //Set the element as visited visited[current[1] + "," + current[2]] = true; //If the element is the destination if (current[1] === grid.length - 1 && current[2] === grid.length - 1) { //Return the value of the element return current[0]; } //If the element is not the destination else { //Add its neighbors to the heap addNeighbors(current, grid, heap, visited); } } } }; function addNeighbors(current, grid, heap, visited) { //Create variables for the row and column of the current element let row = current[1]; let col = current[2]; //If the row is not the first row if (row > 0) { //Add the element above to the heap heap.push([grid[row - 1][col], row - 1, col]); } //If the row is not the last row if (row < grid.length - 1) { //Add the element below to the heap heap.push([grid[row + 1][col], row + 1, col]); } //If the column is not the first column if (col > 0) { //Add the element to the left to the heap heap.push([grid[row][col - 1], row, col - 1]); } //If the column is not the last column if (col < grid.length - 1) { //Add the element to the right to the heap heap.push([grid[row][col + 1], row, col + 1]); } }

There are a few ways to solve this problem. One approach would be to use a priority queue to keep track of the smallest element at each step. Then, we can do a breadth first search from the starting position and keep track of the minimum element we've seen so far. If the current element is greater than the minimum element, we can update the minimum element and continue the search. Otherwise, we can stop the search and return the current element. Another approach would be to use a union-find data structure. We can keep track of the size of each connected component and the minimum element in that component. Then, we can do a breadth first search from the starting position and union the current position with any adjacent position that has a smaller element. If the size of the current component is greater than or equal to k, we can stop the search and return the minimum element in the current component.

using System; public class Solution { public int SwimInWater(int[][] grid) { int N = grid.Length; PriorityQueue pq = new PriorityQueue(N*N); bool[,] seen = new bool[N,N]; pq.Enqueue(0, 0, grid[0][0]); seen[0,0] = true; while (!pq.IsEmpty()) { Tupletuple = pq.Dequeue(); int r = tuple.Item1, c = tuple.Item2, t = tuple.Item3; if (r == N-1 && c == N-1) return t; for (int dr = -1; dr <= 1; dr++) for (int dc = -1; dc <= 1; dc++) { int nr = r + dr, nc = c + dc; if (0 <= nr && nr < N && 0 <= nc && nc < N && seen[nr,nc] == false) { seen[nr,nc] = true; pq.Enqueue(nr, nc, Math.Max(t, grid[nr][nc])); } } } return -1; } } public class PriorityQueue { private List > list; private int size; public PriorityQueue(int size) { this.size = size; this.list = new List >(); } public bool IsEmpty() { return this.list.Count == 0; } public void Enqueue(int r, int c, int t) { Tuple tuple = new Tuple (r, c, t); this.list.Add(tuple); int index = this.list.Count - 1; while (index > 0) { int parent = (index - 1) / 2; if (this.list[parent].Item3 <= this.list[index].Item3) break; Tuple temp = this.list[parent]; this.list[parent] = this.list[index]; this.list[index] = temp; index = parent; } } public Tuple Dequeue() { Tuple tuple = this.list[0]; this.list[0] = this.list[this.list.Count - 1]; this.list.RemoveAt(this.list.Count - 1); int index = 0; while (index * 2 + 1 < this.list.Count) { int a = index * 2 + 1, b = index * 2 + 2; if (b < this.list.Count && this.list[b].Item3 < this.list[a].Item3) a = b; if (this.list[index].Item3 <= this.list[a].Item3) break; Tuple temp = this.list[index]; this.list[index] = this.list[a]; this.list[a] = temp; index = a; } return tuple; } }