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;
PriorityQueue pq = 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_depthvar 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())
{
Tuple tuple = 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;
}
} 