778. Swim in Rising Water - Solution

Q: Is Swim in Rising Water easy or hard?

Swim in Rising Water is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that the grid traversal must minimize the maximum elevation along the path, which requires algorithms like Dijkstra, binary search with DFS, or Union Find.

Q: How to solve Swim in Rising Water in O(n)?

An O(n) solution is not possible because the grid contains n^2 cells and at least most of them must be examined. The best known solutions run in O(n^2 log n) using a priority queue (Dijkstra) or binary search combined with DFS/BFS reachability checks.

Q: Swim in Rising Water Python or Java solution?

The problem is commonly implemented using a priority queue in Python (heapq) or Java (PriorityQueue). Both implementations follow the same idea: push grid cells into a min-heap and track the maximum elevation seen along the path until the destination is reached.

Q: What is the best approach for Swim in Rising Water?

Dijkstra's algorithm with a min-heap is the most common optimal approach. Treat each grid cell as a node and always expand the cell with the smallest elevation using a priority queue. The first time you reach the bottom-right cell, the maximum elevation along that path is the minimum time required. This runs in O(n^2 log n) time.

Q: What data structure is used in Swim in Rising Water?

The primary data structure is a min-heap (priority queue) used in Dijkstra's algorithm to process cells in increasing elevation order. Other supporting structures include a visited matrix and optionally DFS/BFS stacks or queues when using the binary search approach.

Q: What is the time complexity of Swim in Rising Water?

The optimal solutions typically run in O(n^2 log n) time for an n x n grid. Dijkstra's algorithm performs heap operations for up to n^2 cells, while Binary Search with DFS checks reachability in O(n^2) time across O(log n) iterations.

Q: Is Swim in Rising Water asked at Google or Amazon interviews?

Swim in Rising Water is a well-known hard grid and graph problem that appears in high-level technical interviews. Variants involving priority queues, grid traversal, or minimum maximum path problems are commonly asked at companies like Google, Amazon, and Meta.

The problem

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Example 1:

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n²
Each value grid[i][j] is unique.

Approach overview

Problem Overview: You are given an array-based n x n grid where each cell represents the elevation of the land. Water rises over time, and at time t you can only enter cells with elevation ≤ t. The goal is to reach the bottom-right cell from the top-left as early as possible.

Approach 1: Dijkstra's Algorithm with Min-Heap (Time: O(n² log n), Space: O(n²))

This problem behaves like a shortest-path problem where the "cost" of a path is the maximum elevation encountered along the route. Use a min-heap (priority queue) to always expand the cell with the smallest elevation seen so far. Start from (0,0), push it into the heap, and repeatedly pop the lowest elevation cell. From each cell, explore its four neighbors and push them into the heap if they haven't been visited. The key insight: the moment you pop the destination cell, the maximum elevation along that path is the minimum time required. This works because Dijkstra always processes the smallest possible "time" first.

The running time is dominated by heap operations across at most n^2 cells, giving O(n^2 log n). A visited matrix tracks processed cells, requiring O(n^2) space.

Approach 2: Binary Search with DFS (Time: O(n² log n), Space: O(n²))

Another perspective: instead of constructing the path directly, search for the minimum time t that makes the destination reachable. Use binary search over the time range from grid[0][0] to n^2 - 1. For each candidate time, run a DFS (or BFS) starting at (0,0) and only move to cells whose elevation is ≤ t. If the destination becomes reachable, reduce the search range; otherwise increase it.

The DFS explores at most n^2 cells per check. Binary search runs about log(n^2) iterations, producing overall complexity of O(n^2 log n). This approach is conceptually simple because it separates "reachability" from "time optimization".

Recommended for interviews: Dijkstra with a min-heap is the most commonly expected solution. It demonstrates understanding of priority queues and shortest-path reasoning on grids. Binary search + DFS is also strong because it shows problem transformation skills—turning a path problem into a monotonic feasibility check. Explaining both approaches clearly signals strong algorithmic thinking.

Approach 1: Approach 1: Dijkstra's Algorithm with Min-Heap

This approach uses Dijkstra's algorithm with a priority queue (min-heap) to find the shortest increasing path to the destination. Each cell in the grid can be thought of as a node, with the elevation as the cost of reaching that node. The priority in the queue is determined by the maximum elevation encountered on the path to that cell. We continuously pick the cell with the lowest elevation cost that can be reached, update the costs of its neighbors and repeat the process until we reach the target cell (n-1, n-1).

Python

import heapq

def swimInWater(grid):
    n = len(grid)
    pq = [(grid[0][0], 0, 0)]
    visited = [[False] * n for _ in range(n)]
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while pq:
        t, x, y = heapq.heappop(pq)
        if x == n - 1 and y == n - 1:
            return t
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = True
                heapq.heappush(pq, (max(t, grid[nx][ny]), nx, ny))

    return -1

Java

import java.util.PriorityQueue;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        boolean[][] visited = new boolean[n][n];
        pq.offer(new int[]{0, 0, grid[0][0]});

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            int x = cell[0], y = cell[1], t = cell[2];

            if (x == n - 1 && y == n - 1) {
                return t;
            }

            for (int[] d : directions) {
                int newX = x + d[0], newY = y + d[1];
                if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    pq.offer(new int[]{newX, newY, Math.max(t, grid[newX][newY])});
                }
            }
        }

        return -1;
    }
}

C++

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int swimInWater(vector<vector<int>>& grid) {
    int n = grid.size();
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    pq.push({grid[0][0], {0, 0}});
    visited[0][0] = true;

    while (!pq.empty()) {
        auto [t, pos] = pq.top();
        pq.pop();
        int x = pos.first, y = pos.second;

        if (x == n-1 && y == n-1) return t;

        for (auto& d : directions) {
            int nx = x + d[0];
            int ny = y + d[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
                visited[nx][ny] = true;
                pq.push({max(t, grid[nx][ny]), {nx, ny}});
            }
        }
    }
    return -1;
}

JavaScript

var swimInWater = function(grid) {
    const n = grid.length;
    const visited = Array.from({ length: n }, () => Array(n).fill(false));
    const pq = new MinPriorityQueue({ priority: x => x[2] });
    
    pq.enqueue([0, 0, grid[0][0]]);
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    visited[0][0] = true;
    
    while (!pq.isEmpty()) {
        const [x, y, t] = pq.dequeue().element;

        if (x === n - 1 && y === n - 1) return t;

        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
                visited[nx][ny] = true;
                pq.enqueue([nx, ny, Math.max(t, grid[nx][ny])]);
            }
        }
    }
    return -1;
};

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_N 50

typedef struct {
    int x, y, elevation;
} Point;

int cmp(const void *a, const void *b) {
    return ((Point *)a)->elevation - ((Point *)b)->elevation;
}

bool isSafe(int x, int y, int n) {
    return x >= 0 && y >= 0 && x < n && y < n;
}

int swimInWater(int grid[MAX_N][MAX_N], int n) {
    int visited[MAX_N][MAX_N] = {0};
    int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    Point pq[MAX_N * MAX_N];
    int pqSize = 0;

    pq[pqSize++] = (Point){0, 0, grid[0][0]};
    visited[0][0] = 1;

    while (pqSize) {
        qsort(pq, pqSize, sizeof(Point), cmp);
        Point current = pq[--pqSize];
        int currElevation = current.elevation;

        if (current.x == n - 1 && current.y == n - 1) {
            return currElevation;
        }

        for (int i = 0; i < 4; i++) {
            int newX = current.x + directions[i][0];
            int newY = current.y + directions[i][1];

            if (isSafe(newX, newY, n) && !visited[newX][newY]) {
                visited[newX][newY] = 1;
                pq[pqSize++] = (Point){newX, newY, (currElevation > grid[newX][newY]) ? currElevation : grid[newX][newY]};
            }
        }
    }
    return -1;
}

int main() {
    int grid[MAX_N][MAX_N] = {
        {0, 2},
        {1, 3}
    };
    printf("%d\n", swimInWater(grid, 2));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int SwimInWater(int[][] grid) {
        int n = grid.Length;
        var pq = new SortedSet<(int t, int x, int y)> { (grid[0][0], 0, 0) };
        bool[][] visited = new bool[n][];
        for (int i = 0; i < n; i++) { visited[i] = new bool[n]; }
        visited[0][0] = true;

        int[][] directions = { new[] { 1, 0 }, new[] { -1, 0 }, new[] { 0, 1 }, new[] { 0, -1 } };

        while (pq.Count > 0) {
            var (t, x, y) = pq.Min;
            pq.Remove(pq.Min);

            if (x == n - 1 && y == n - 1) {
                return t;
            }

            foreach (var dir in directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    pq.Add((Math.Max(t, grid[newX][newY]), newX, newY));
                }
            }
        }

        return -1;
    }
}

This Python solution uses the heapq module to operate as a min-heap, keeping track of the least water elevation mandatorily needed to traverse to each cell. By always expanding the cell with the minimal maximum path weight, it provides the correct path through the grid with the minimal possible maximum elevation on its path.

Complexity

Time Complexity: O(n^2 log n), since we manage a heap across a number of operations linear to grid nodes size.
Space Complexity: O(n^2), used for the visited array and priority queue management.

Try this approach in the editor

Approach 2: Approach 2: Binary Search with DFS

This approach leverages binary search in union with a Depth-First Search (optimized traversal) to find the minimal elevation at which it is possible to traverse from the start to the end point. By evaluating the middling water level and checking the feasibility of reaching the destination, the search efficiently pinpoints the boundary condition: the smallest time 't' needed to connect the top-left and bottom-right corners without breaking elevation conditions.

Python

def canSwim(grid, visited, mid, x, y):
    n = len(grid)
    if x < 0 or y < 0 or x >= n or y >= n or visited[x][y] or grid[x][y] > mid:
        return False
    if x == n - 1 and y == n - 1:
        return True
    
    visited[x][y] = True
    
    return (canSwim(grid, visited, mid, x + 1, y) or
            canSwim(grid, visited, mid, x - 1, y) or
            canSwim(grid, visited, mid, x, y + 1) or
            canSwim(grid, visited, mid, x, y - 1))


def swimInWater(grid):
    n = len(grid)
    left, right = grid[0][0], n * n - 1

    while left < right:
        mid = (left + right) // 2
        visited = [[False] * n for _ in range(n)]

        if canSwim(grid, visited, mid, 0, 0):
            right = mid
        else:
            left = mid + 1

    return left

Java

class Solution {
    private boolean canSwim(int[][] grid, boolean[][] visited, int mid, int x, int y) {
        int n = grid.length;
        if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || grid[x][y] > mid) return false;
        if (x == n - 1 && y == n - 1) return true;
        visited[x][y] = true;

        boolean result = canSwim(grid, visited, mid, x + 1, y) || canSwim(grid, visited, mid, x - 1, y) ||
                         canSwim(grid, visited, mid, x, y + 1) || canSwim(grid, visited, mid, x, y - 1);
        return result;
    }

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int left = grid[0][0], right = n * n - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            boolean[][] visited = new boolean[n][n];

            if (canSwim(grid, visited, mid, 0, 0)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

C++

#include <vector>
using namespace std;

bool canSwim(vector<vector<int>>& grid, vector<vector<bool>>& visited, int mid, int x, int y) {
    int n = grid.size();
    if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || grid[x][y] > mid) return false;
    if (x == n - 1 && y == n - 1) return true;
    visited[x][y] = true;
    return canSwim(grid, visited, mid, x+1, y) || canSwim(grid, visited, mid, x-1, y) ||
           canSwim(grid, visited, mid, x, y+1) || canSwim(grid, visited, mid, x, y-1);
}

int swimInWater(vector<vector<int>>& grid) {
    int n = grid.size();
    int left = grid[0][0], right = n * n - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        vector<vector<bool>> visited(n, vector<bool>(n, false));

        if (canSwim(grid, visited, mid, 0, 0)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

JavaScript

const swimInWater = (grid) => {
    const n = grid.length;
    
    const canSwim = (visited, mid, x, y) => {
        if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || grid[x][y] > mid) return false;
        if (x === n - 1 && y === n - 1) return true;
        visited[x][y] = true;

        return canSwim(visited, mid, x + 1, y) ||
               canSwim(visited, mid, x - 1, y) ||
               canSwim(visited, mid, x, y + 1) ||
               canSwim(visited, mid, x, y - 1);
    };

    let left = grid[0][0], right = n * n - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const visited = Array.from({ length: n }, () => Array(n).fill(false));

        if (canSwim(visited, mid, 0, 0)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#define MAX_N 50

bool dfs(int grid[MAX_N][MAX_N], int visited[MAX_N][MAX_N], int n, int x, int y, int T) {
    if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || grid[x][y] > T) return false;
    if (x == n - 1 && y == n - 1) return true;

    visited[x][y] = 1;
    bool res = dfs(grid, visited, n, x + 1, y, T) || dfs(grid, visited, n, x - 1, y, T) ||
               dfs(grid, visited, n, x, y + 1, T) || dfs(grid, visited, n, x, y - 1, T);
    return res;
}

int swimInWater(int grid[MAX_N][MAX_N], int n) {
    int left = grid[0][0], right = n * n - 1, mid;

    while (left < right) {
        mid = left + (right - left) / 2;
        int visited[MAX_N][MAX_N] = {0};
        if (dfs(grid, visited, n, 0, 0, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int grid[MAX_N][MAX_N] = {
        {0, 2},
        {1, 3}
    };
    printf("%d\n", swimInWater(grid, 2));
    return 0;
}

public class Solution {
    private bool CanSwim(int[][] grid, bool[][] visited, int mid, int x, int y) {
        int n = grid.Length;
        if (x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || grid[x][y] > mid) return false;
        if (x == n - 1 && y == n - 1) return true;
        
        visited[x][y] = true;
        
        return CanSwim(grid, visited, mid, x + 1, y) ||
               CanSwim(grid, visited, mid, x - 1, y) ||
               CanSwim(grid, visited, mid, x, y + 1) ||
               CanSwim(grid, visited, mid, x, y - 1);
    }

    public int SwimInWater(int[][] grid) {
        int n = grid.Length;
        int left = grid[0][0], right = n * n - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            var visited = new bool[n][];
            for (int i = 0; i < n; i++) visited[i] = new bool[n];

            if (CanSwim(grid, visited, mid, 0, 0)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

This Python solution applies binary search methodology allied with a depth-first search function to find the least elevation time to traverse grid's extremes. By incrementally hypothesizing water levels, it analytically draws borders optimizing pathing.

Complexity

Time Complexity: O(n^2 log n), involving binary search inversions optimized using a flat DFS layout.
Space Complexity: O(n^2), attributively establishing pattern matrices and recursion landscapes.

Try this approach in the editor

Approach 3: Union Find

We can map each position (i, j) to an ID id = i times n + j, and use a union-find data structure to maintain connected components.

First, we use a one-dimensional array hi to record the position ID corresponding to each height, i.e., hi[h] represents the position ID with height h.

Then we traverse from height 0 to height n^2 - 1. For each height t, we merge position hi[t] with its four adjacent positions that have heights not exceeding t. If after merging, position 0 and position n^2 - 1 are connected, then we have found the minimum time t, and we return t.

The time complexity is O(n^2 times log n) and the space complexity is O(n^2), where n is the side length of the matrix.

TypeScript

function swimInWater(grid: number[][]): number {
    const n = grid.length;
    const m = n * n;
    const p = Array.from({ length: m }, (_, i) => i);
    const hi = new Array<number>(m);
    const find = (x: number): number => (p[x] === x ? x : (p[x] = find(p[x])));

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            hi[grid[i][j]] = i * n + j;
        }
    }

    const dirs = [-1, 0, 1, 0, -1];

    for (let t = 0; t < m; ++t) {
        const id = hi[t];
        const x = Math.floor(id / n);
        const y = id % n;

        for (let k = 0; k < 4; ++k) {
            const nx = x + dirs[k];
            const ny = y + dirs[k + 1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] <= t) {
                p[find(x * n + y)] = find(nx * n + ny);
            }
        }
        if (find(0) === find(m - 1)) {
            return t;
        }
    }

    return 0;
}

func swimInWater(grid [][]int) int {
	n := len(grid)
	m := n * n
	p := make([]int, m)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	hi := make([]int, m)
	for i := range grid {
		for j, h := range grid[i] {
			hi[h] = i*n + j
		}
	}
	dirs := []int{-1, 0, 1, 0, -1}
	for t := 0; t < m; t++ {
		id := hi[t]
		x, y := id/n, id%n
		for k := 0; k < 4; k++ {
			nx, ny := x+dirs[k], y+dirs[k+1]
			if nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] <= t {
				a := find(x*n + y)
				b := find(nx*n + ny)
				p[a] = b
			}
		}
		if find(0) == find(m-1) {
			return t
		}
	}
	return 0
}

Rust

impl Solution {
    pub fn swim_in_water(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = n * n;
        let mut p: Vec<usize> = (0..m).collect();
        let mut hi = vec![0usize; m];

        for i in 0..n {
            for j in 0..n {
                hi[grid[i][j] as usize] = i * n + j;
            }
        }

        fn find(x: usize, p: &mut Vec<usize>) -> usize {
            if p[x] != x {
                p[x] = find(p[x], p);
            }
            p[x]
        }

        let dirs = [-1isize, 0, 1, 0, -1];

        for t in 0..m {
            let id = hi[t];
            let x = id / n;
            let y = id % n;

            for k in 0..4 {
                let nx = x as isize + dirs[k];
                let ny = y as isize + dirs[k + 1];
                if nx >= 0 && nx < n as isize && ny >= 0 && ny < n as isize {
                    let nx = nx as usize;
                    let ny = ny as usize;
                    if grid[nx][ny] as usize <= t {
                        let a = find(x * n + y, &mut p);
                        let b = find(nx * n + ny, &mut p);
                        p[a] = b;
                    }
                }
            }

            if find(0, &mut p) == find(m - 1, &mut p) {
                return t as i32;
            }
        }

        0
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Dijkstra's Algorithm with Min-Heap	Time Complexity: O(n^2 log n), since we manage a heap across a number of operations linear to grid nodes size. Space Complexity: O(n^2), used for the visited array and priority queue management.
Approach 2: Binary Search with DFS	Time Complexity: O(n^2 log n), involving binary search inversions optimized using a flat DFS layout. Space Complexity: O(n^2), attributively establishing pattern matrices and recursion landscapes.
Union Find	–

Complexity analysis

Approach	Time	Space	When to Use
Dijkstra's Algorithm with Min-Heap	O(n^2 log n)	O(n^2)	Best general solution for grid path problems with weighted constraints
Binary Search + DFS/BFS	O(n^2 log n)	O(n^2)	When the answer is monotonic and can be validated via reachability
Union Find (Disjoint Set)	O(n^2 log n)	O(n^2)	Useful when processing cells in increasing elevation order and merging components

Frequently asked questions

Is Swim in Rising Water easy or hard?

Swim in Rising Water is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that the grid traversal must minimize the maximum elevation along the path, which requires algorithms like Dijkstra, binary search with DFS, or Union Find.

How to solve Swim in Rising Water in O(n)?

An O(n) solution is not possible because the grid contains n^2 cells and at least most of them must be examined. The best known solutions run in O(n^2 log n) using a priority queue (Dijkstra) or binary search combined with DFS/BFS reachability checks.

Swim in Rising Water Python or Java solution?

The problem is commonly implemented using a priority queue in Python (heapq) or Java (PriorityQueue). Both implementations follow the same idea: push grid cells into a min-heap and track the maximum elevation seen along the path until the destination is reached.

What is the best approach for Swim in Rising Water?

Dijkstra's algorithm with a min-heap is the most common optimal approach. Treat each grid cell as a node and always expand the cell with the smallest elevation using a priority queue. The first time you reach the bottom-right cell, the maximum elevation along that path is the minimum time required. This runs in O(n^2 log n) time.

What data structure is used in Swim in Rising Water?

The primary data structure is a min-heap (priority queue) used in Dijkstra's algorithm to process cells in increasing elevation order. Other supporting structures include a visited matrix and optionally DFS/BFS stacks or queues when using the binary search approach.

What is the time complexity of Swim in Rising Water?

The optimal solutions typically run in O(n^2 log n) time for an n x n grid. Dijkstra's algorithm performs heap operations for up to n^2 cells, while Binary Search with DFS checks reachability in O(n^2) time across O(log n) iterations.

Is Swim in Rising Water asked at Google or Amazon interviews?

Swim in Rising Water is a well-known hard grid and graph problem that appears in high-level technical interviews. Variants involving priority queues, grid traversal, or minimum maximum path problems are commonly asked at companies like Google, Amazon, and Meta.

Swim in Rising Water solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dijkstra's Algorithm with Min-Heap

Approach 2: Approach 2: Binary Search with DFS

Approach 3: Union Find

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Swim in Rising Water solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dijkstra's Algorithm with Min-Heap

Approach 2: Approach 2: Binary Search with DFS

Approach 3: Union Find

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems