Swim in Rising Water

🎯

Swim in Rising Water

hardGRAPHGoogleAmazon

Imagine you are trapped in a flooded grid where water levels rise over time, and you need to find the earliest time you can swim from the top-left to the bottom-right cell.

💡 This problem combines graph traversal with a tricky constraint on movement based on water levels. Beginners often struggle because it requires understanding how to model the problem as a connectivity or path problem with a dynamic threshold, which is not straightforward.

📋

Problem Statement

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j). Initially, the water level is at 0 and rises by 1 unit per time step. You can swim from a cell to any adjacent cell (up, down, left, right) if and only if the water level is at least the elevation of both cells. Return the minimum time required to reach the bottom-right cell (n-1, n-1) starting from the top-left cell (0, 0).

1 ≤ n ≤ 500 ≤ grid[i][j] < n*nAll grid[i][j] are unique

💡

Example

Input"[[0,2],[1,3]]"

Output3

At time 3, water level is 3, allowing movement from (0,0) to (1,1) through (1,0).

• n = 1 → output is grid[0][0]
• Grid with strictly increasing elevations along the path → output equals max elevation on path
• Grid where start or end cell has very high elevation → output equals that elevation
• Grid with isolated high elevation cells blocking direct path → requires detour

⚠️

Common Mistakes

Not checking if start cell is submerged before DFS

DFS fails immediately or returns incorrect result

✅ Add condition to ensure grid[0][0] ≤ current water level before DFS

Using DFS without visited set leading to infinite recursion

Stack overflow or TLE due to revisiting cells

✅ Maintain a visited set or array to track visited cells

Incorrect union-find parent or rank updates

Union-find fails to merge sets correctly, causing wrong connectivity checks

✅ Implement path compression and union by rank properly

Not sorting cells by elevation before union operations

Union-find merges cells in wrong order, leading to incorrect earliest connection time

✅ Sort all cells by elevation ascending before processing

Binary search boundaries not set correctly

Algorithm may miss correct answer or infinite loop

✅ Initialize low as grid[0][0] and high as max elevation in grid

🧠

Brute Force (DFS with Increasing Time Simulation)

💡 This approach tries all possible times from 0 upwards and attempts to find a path by DFS at each time. It is very slow but helps understand the problem constraints and the role of water level.

Intuition

At each time t, check if a path exists from start to end where all visited cells have elevation ≤ t. Increase t until such a path is found.

Algorithm

1. Initialize time t = 0.
2. While true:
3. Perform DFS from (0,0) visiting only cells with elevation ≤ t.
4. If (n-1, n-1) is reachable, return t; else increment t.

💡 The main difficulty is realizing that you can simulate time and check connectivity repeatedly, which is conceptually simple but inefficient.

</>

Code

from typing import List

def swimInWater(grid: List[List[int]]) -> int:
    n = len(grid)
    def dfs(x, y, t, visited):
        if x == n - 1 and y == n - 1:
            return True
        visited.add((x, y))
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited and grid[nx][ny] <= t:
                if dfs(nx, ny, t, visited):
                    return True
        return False

    t = 0
    max_elevation = max(max(row) for row in grid)
    while t <= max_elevation:
        visited = set()
        if grid[0][0] <= t and dfs(0, 0, t, visited):
            return t
        t += 1

# Driver code
if __name__ == '__main__':
    grid = [[0,2],[1,3]]
    print(swimInWater(grid))  # Expected output: 3

Line Notes

def dfs(x, y, t, visited):Defines a helper function to explore reachable cells at time t, enabling path search under water level constraints.

if x == n - 1 and y == n - 1:Checks if destination is reached to terminate DFS early and confirm path existence.

visited.add((x, y))Marks current cell as visited to avoid cycles and repeated exploration.

if grid[nx][ny] <= t:Ensures movement only to cells submerged by water at current time t, respecting problem constraints.

while t <= max_elevation:Simulates increasing water level from 0 up to the maximum elevation in the grid.

if grid[0][0] <= t and dfs(0, 0, t, visited):Starts DFS only if the start cell is submerged at time t, ensuring valid traversal.

import java.util.*;

public class SwimInRisingWater {
    private int n;
    private int[][] grid;
    private boolean[][] visited;

    public boolean dfs(int x, int y, int t) {
        if (x == n - 1 && y == n - 1) return true;
        visited[x][y] = true;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t) {
                if (dfs(nx, ny, t)) return true;
            }
        }
        return false;
    }

    public int swimInWater(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        int maxElevation = 0;
        for (int[] row : grid) {
            for (int val : row) {
                maxElevation = Math.max(maxElevation, val);
            }
        }
        for (int t = 0; t <= maxElevation; t++) {
            visited = new boolean[n][n];
            if (grid[0][0] <= t && dfs(0, 0, t)) return t;
        }
        return -1;
    }

    public static void main(String[] args) {
        SwimInRisingWater sol = new SwimInRisingWater();
        int[][] grid = {{0, 2}, {1, 3}};
        System.out.println(sol.swimInWater(grid)); // Expected: 3
    }
}

Line Notes

public boolean dfs(int x, int y, int t)Recursive DFS to check reachability at time t, exploring valid adjacent cells.

if (x == n - 1 && y == n - 1) return true;Base case: reached destination, so path exists.

visited = new boolean[n][n];Reset visited array for each time t to ensure fresh traversal.

if (grid[0][0] <= t && dfs(0, 0, t)) return t;Start DFS only if start cell is submerged, ensuring valid starting point.

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

class Solution {
    int n;
    vector<vector<int>> grid;
    vector<vector<bool>> visited;
    bool dfs(int x, int y, int t) {
        if (x == n - 1 && y == n - 1) return true;
        visited[x][y] = true;
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t) {
                if (dfs(nx, ny, t)) return true;
            }
        }
        return false;
    }
public:
    int swimInWater(vector<vector<int>>& grid) {
        this->grid = grid;
        n = grid.size();
        int maxElevation = 0;
        for (auto &row : grid) {
            for (int val : row) maxElevation = max(maxElevation, val);
        }
        for (int t = 0; t <= maxElevation; t++) {
            visited.assign(n, vector<bool>(n, false));
            if (grid[0][0] <= t && dfs(0, 0, t)) return t;
        }
        return -1;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0, 2}, {1, 3}};
    cout << sol.swimInWater(grid) << endl; // Expected: 3
    return 0;
}

Line Notes

bool dfs(int x, int y, int t)DFS helper to check if destination reachable at time t by exploring valid neighbors.

if (x == n - 1 && y == n - 1) return true;Reached bottom-right cell, confirming path existence.

visited.assign(n, vector<bool>(n, false));Reset visited before each DFS attempt to avoid stale state.

if (grid[0][0] <= t && dfs(0, 0, t)) return t;Start DFS only if start cell is submerged at current time.

function swimInWater(grid) {
    const n = grid.length;
    function dfs(x, y, t, visited) {
        if (x === n - 1 && y === n - 1) return true;
        visited.add(`${x},${y}`);
        const directions = [[1,0],[-1,0],[0,1],[0,-1]];
        for (const [dx, dy] of directions) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited.has(`${nx},${ny}`) && grid[nx][ny] <= t) {
                if (dfs(nx, ny, t, visited)) return true;
            }
        }
        return false;
    }

    let maxElevation = 0;
    for (const row of grid) {
        for (const val of row) {
            maxElevation = Math.max(maxElevation, val);
        }
    }

    for (let t = 0; t <= maxElevation; t++) {
        const visited = new Set();
        if (grid[0][0] <= t && dfs(0, 0, t, visited)) return t;
    }
    return -1;
}

// Test
console.log(swimInWater([[0,2],[1,3]])); // Expected: 3

Line Notes

function dfs(x, y, t, visited)DFS to explore reachable cells at time t, ensuring path validity under water constraints.

if (x === n - 1 && y === n - 1) return true;Check if destination reached to confirm path existence.

visited.add(`${x},${y}`);Mark current cell visited to avoid revisiting and infinite loops.

if (grid[0][0] <= t && dfs(0, 0, t, visited)) return t;Start DFS only if start cell is submerged at current water level.

⏱

Complexity

TimeO(n^2 * maxElevation)

SpaceO(n^2)

For each time t up to max elevation, DFS explores up to n^2 cells, leading to O(n^2 * maxElevation) time.

💡 For n=50 and maxElevation ~2500, this means roughly 6 million DFS calls, which is too slow for interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

🧠

Binary Search + DFS

💡 This approach uses binary search on the answer (time) combined with DFS to check feasibility, drastically reducing the search space.

Intuition

Instead of checking every time from 0 to max elevation, use binary search to guess the minimum time and verify if a path exists at that time.

Algorithm

1. Set low = grid[0][0], high = max elevation in grid.
2. While low < high:
3. mid = (low + high) // 2
4. Use DFS to check if path exists with water level mid.
5. If path exists, high = mid; else low = mid + 1.
6. Return low.

💡 The key insight is that the problem is monotonic in time: if you can swim at time t, you can swim at any time > t.

</>

Code

from typing import List

def swimInWater(grid: List[List[int]]) -> int:
    n = len(grid)
    max_elevation = max(max(row) for row in grid)

    def can_swim(t):
        visited = set()
        def dfs(x, y):
            if x == n - 1 and y == n - 1:
                return True
            visited.add((x, y))
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited and grid[nx][ny] <= t:
                    if dfs(nx, ny):
                        return True
            return False
        return grid[0][0] <= t and dfs(0, 0)

    low, high = grid[0][0], max_elevation
    while low < high:
        mid = (low + high) // 2
        if can_swim(mid):
            high = mid
        else:
            low = mid + 1
    return low

# Driver code
if __name__ == '__main__':
    grid = [[0,2],[1,3]]
    print(swimInWater(grid))  # Expected output: 3

Line Notes

def can_swim(t):Helper to check if a path exists at water level t, enabling binary search feasibility check.

visited = set()Track visited cells to avoid cycles during DFS traversal.

if grid[nx][ny] <= t:Only move to cells submerged at time t, respecting problem constraints.

while low < high:Binary search loop to narrow down the minimum feasible time efficiently.

if can_swim(mid):If path exists at mid, try to find a smaller feasible time.

else:If no path at mid, increase lower bound to search higher times.

import java.util.*;

public class SwimInRisingWater {
    private int n;
    private int[][] grid;
    private boolean[][] visited;

    public boolean dfs(int x, int y, int t) {
        if (x == n - 1 && y == n - 1) return true;
        visited[x][y] = true;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t) {
                if (dfs(nx, ny, t)) return true;
            }
        }
        return false;
    }

    public int swimInWater(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        int maxElevation = 0;
        for (int[] row : grid) {
            for (int val : row) {
                maxElevation = Math.max(maxElevation, val);
            }
        }
        int low = grid[0][0], high = maxElevation;
        while (low < high) {
            int mid = (low + high) / 2;
            visited = new boolean[n][n];
            if (grid[0][0] <= mid && dfs(0, 0, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        SwimInRisingWater sol = new SwimInRisingWater();
        int[][] grid = {{0, 2}, {1, 3}};
        System.out.println(sol.swimInWater(grid)); // Expected: 3
    }
}

Line Notes

public boolean dfs(int x, int y, int t)DFS to check reachability at water level t, used in binary search feasibility check.

visited = new boolean[n][n];Reset visited before each DFS to ensure fresh traversal state.

if (grid[0][0] <= mid && dfs(0, 0, mid))Check if start cell submerged and path exists at mid water level.

while (low < high)Binary search loop to find minimal feasible time efficiently.

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

class Solution {
    int n;
    vector<vector<int>> grid;
    vector<vector<bool>> visited;
    bool dfs(int x, int y, int t) {
        if (x == n - 1 && y == n - 1) return true;
        visited[x][y] = true;
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] <= t) {
                if (dfs(nx, ny, t)) return true;
            }
        }
        return false;
    }
public:
    int swimInWater(vector<vector<int>>& grid) {
        this->grid = grid;
        n = grid.size();
        int maxElevation = 0;
        for (auto &row : grid) {
            for (int val : row) maxElevation = max(maxElevation, val);
        }
        int low = grid[0][0], high = maxElevation;
        while (low < high) {
            visited.assign(n, vector<bool>(n, false));
            int mid = (low + high) / 2;
            if (grid[0][0] <= mid && dfs(0, 0, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{0, 2}, {1, 3}};
    cout << sol.swimInWater(grid) << endl; // Expected: 3
    return 0;
}

Line Notes

bool dfs(int x, int y, int t)DFS helper to check path feasibility at time t during binary search.

visited.assign(n, vector<bool>(n, false));Reset visited before each DFS call to avoid stale state.

if (grid[0][0] <= mid && dfs(0, 0, mid))Check if start cell submerged and path exists at mid water level.

while (low < high)Binary search loop to find minimal feasible time efficiently.

function swimInWater(grid) {
    const n = grid.length;
    function canSwim(t) {
        const visited = new Set();
        function dfs(x, y) {
            if (x === n - 1 && y === n - 1) return true;
            visited.add(`${x},${y}`);
            const directions = [[1,0],[-1,0],[0,1],[0,-1]];
            for (const [dx, dy] of directions) {
                const nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited.has(`${nx},${ny}`) && grid[nx][ny] <= t) {
                    if (dfs(nx, ny)) return true;
                }
            }
            return false;
        }
        return grid[0][0] <= t && dfs(0, 0);
    }

    let maxElevation = 0;
    for (const row of grid) {
        for (const val of row) {
            maxElevation = Math.max(maxElevation, val);
        }
    }

    let low = grid[0][0], high = maxElevation;
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (canSwim(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

// Test
console.log(swimInWater([[0,2],[1,3]])); // Expected: 3

Line Notes

function canSwim(t)Checks if path exists at water level t using DFS, enabling binary search feasibility check.

visited.add(`${x},${y}`);Mark cell visited to prevent cycles and repeated exploration.

if (grid[0][0] <= t && dfs(0, 0))Start DFS only if start cell submerged at current water level.

while (low < high)Binary search loop to efficiently find minimal feasible time.

⏱

Complexity

TimeO(n^2 * log(maxElevation))

SpaceO(n^2)

Binary search reduces time steps to log(maxElevation), each DFS takes O(n^2).

💡 For n=50 and maxElevation ~2500, this reduces to about 50*50*12 = 30,000 operations, which is efficient.

Interview Verdict: Accepted

This approach is efficient and acceptable in interviews, demonstrating binary search on answer combined with DFS.

🧠

Union-Find (Disjoint Set) with Sorting Cells by Elevation

💡 This approach uses union-find to dynamically connect cells as water rises, efficiently checking when start and end become connected.

Intuition

Sort all cells by elevation. Starting from the lowest elevation, union adjacent cells as water level rises. The earliest time when start and end are connected is the answer.

Algorithm

1. Create a list of all cells with their elevations.
2. Sort the list by elevation ascending.
3. Initialize union-find data structure for all cells.
4. Iterate over cells in sorted order, union with adjacent cells already processed.
5. After each union, check if start and end are connected; if yes, return current elevation.

💡 The key is to realize that connectivity changes only when water level reaches a cell's elevation, so processing in sorted order is optimal.

</>

Code

from typing import List

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True


def swimInWater(grid: List[List[int]]) -> int:
    n = len(grid)
    uf = UnionFind(n * n)
    cells = [(grid[i][j], i, j) for i in range(n) for j in range(n)]
    cells.sort()
    visited = [[False]*n for _ in range(n)]

    def index(x, y):
        return x * n + y

    directions = [(1,0), (-1,0), (0,1), (0,-1)]

    for elevation, x, y in cells:
        visited[x][y] = True
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny]:
                uf.union(index(x,y), index(nx, ny))
        if uf.find(0) == uf.find(n*n - 1):
            return elevation

# Driver code
if __name__ == '__main__':
    grid = [[0,2],[1,3]]
    print(swimInWater(grid))  # Expected output: 3

Line Notes

class UnionFind:Defines union-find data structure for efficient connectivity tracking among cells.

cells.sort()Sort cells by elevation to simulate water rising in ascending order.

visited[x][y] = TrueMark cell as flooded at current elevation, enabling union with neighbors.

if uf.find(0) == uf.find(n*n - 1):Check if start and end cells are connected, indicating path availability.

import java.util.*;

public class SwimInRisingWater {
    static class UnionFind {
        int[] parent, rank;
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        public int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        public boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;
            if (rank[rx] < rank[ry]) parent[rx] = ry;
            else if (rank[ry] < rank[rx]) parent[ry] = rx;
            else {
                parent[ry] = rx;
                rank[rx]++;
            }
            return true;
        }
    }

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        UnionFind uf = new UnionFind(n * n);
        int[][] cells = new int[n * n][3];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cells[idx++] = new int[]{grid[i][j], i, j};
            }
        }
        Arrays.sort(cells, Comparator.comparingInt(a -> a[0]));
        boolean[][] visited = new boolean[n][n];
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};

        for (int[] cell : cells) {
            int elevation = cell[0], x = cell[1], y = cell[2];
            visited[x][y] = true;
            for (int[] d : directions) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && visited[nx][ny]) {
                    uf.union(x * n + y, nx * n + ny);
                }
            }
            if (uf.find(0) == uf.find(n * n - 1)) return elevation;
        }
        return -1;
    }

    public static void main(String[] args) {
        SwimInRisingWater sol = new SwimInRisingWater();
        int[][] grid = {{0, 2}, {1, 3}};
        System.out.println(sol.swimInWater(grid)); // Expected: 3
    }
}

Line Notes

class UnionFindUnion-find data structure to track connectivity efficiently among grid cells.

Arrays.sort(cells, Comparator.comparingInt(a -> a[0]));Sort cells by elevation ascending to simulate water rising order.

visited[x][y] = true;Mark cell flooded at current elevation to enable union with neighbors.

if (uf.find(0) == uf.find(n * n - 1)) return elevation;Check if start and end are connected, indicating path availability.

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

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unionSet(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else {
            parent[ry] = rx;
            rank[rx]++;
        }
        return true;
    }
};

int swimInWater(vector<vector<int>>& grid) {
    int n = grid.size();
    UnionFind uf(n * n);
    vector<tuple<int,int,int>> cells;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cells.emplace_back(grid[i][j], i, j);
        }
    }
    sort(cells.begin(), cells.end());
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

    for (auto& [elevation, x, y] : cells) {
        visited[x][y] = true;
        for (auto& d : directions) {
            int nx = x + d[0], ny = y + d[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && visited[nx][ny]) {
                uf.unionSet(x * n + y, nx * n + ny);
            }
        }
        if (uf.find(0) == uf.find(n * n - 1)) return elevation;
    }
    return -1;
}

int main() {
    vector<vector<int>> grid = {{0, 2}, {1, 3}};
    cout << swimInWater(grid) << endl; // Expected: 3
    return 0;
}

Line Notes

UnionFind uf(n * n);Initialize union-find for all cells to track connectivity.

sort(cells.begin(), cells.end());Sort cells by elevation ascending to simulate water rising order.

visited[x][y] = true;Mark cell flooded at current elevation to enable union with neighbors.

if (uf.find(0) == uf.find(n * n - 1)) return elevation;Check connectivity of start and end cells to determine earliest swim time.

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
    }
    find(x) {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    union(x, y) {
        let rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[ry] < this.rank[rx]) this.parent[ry] = rx;
        else {
            this.parent[ry] = rx;
            this.rank[rx]++;
        }
        return true;
    }
}

function swimInWater(grid) {
    const n = grid.length;
    const uf = new UnionFind(n * n);
    const cells = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            cells.push([grid[i][j], i, j]);
        }
    }
    cells.sort((a,b) => a[0] - b[0]);
    const visited = Array.from({length: n}, () => Array(n).fill(false));
    const directions = [[1,0],[-1,0],[0,1],[0,-1]];

    for (const [elevation, x, y] of cells) {
        visited[x][y] = true;
        for (const [dx, dy] of directions) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && visited[nx][ny]) {
                uf.union(x * n + y, nx * n + ny);
            }
        }
        if (uf.find(0) === uf.find(n * n - 1)) return elevation;
    }
    return -1;
}

// Test
console.log(swimInWater([[0,2],[1,3]])); // Expected: 3

Line Notes

class UnionFindUnion-find data structure for connectivity tracking among grid cells.

cells.sort((a,b) => a[0] - b[0]);Sort cells by elevation ascending to simulate water rising order.

visited[x][y] = true;Mark cell flooded at current elevation to enable union with neighbors.

if (uf.find(0) === uf.find(n * n - 1)) return elevation;Check if start and end cells are connected, indicating path availability.

⏱

Complexity

TimeO(n^2 log n^2) = O(n^2 log n)

SpaceO(n^2)

Sorting all n^2 cells takes O(n^2 log n^2), union-find operations are almost O(1) amortized.

💡 For n=50, sorting 2500 cells is efficient, and union-find operations are very fast, making this approach optimal.

Interview Verdict: Accepted

This is the optimal approach using union-find, often preferred in interviews for its elegance and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Union-Find approach is optimal and preferred in interviews; binary search + DFS is a good fallback; brute force is only for understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with Increasing Time Simulation)	O(n^2 * maxElevation)	O(n^2)	Yes (deep recursion)	N/A	Mention only - never code
2. Binary Search + DFS	O(n^2 * log(maxElevation))	O(n^2)	Yes (DFS recursion)	N/A	Good approach to code if union-find not known
3. Union-Find with Sorting Cells	O(n^2 log n)	O(n^2)	No	Yes (connectivity info)	Optimal approach to code and explain

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and ask about input size.Explain brute force approach to show understanding of problem.Introduce binary search + DFS as a better approach.Present union-find approach as optimal solution.Discuss time and space complexities and tradeoffs.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Brute Force: 5min → Binary Search + DFS: 8min → Union-Find: 10min → Testing & Discussion: 5min. Total ~30min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize brute force, knowledge of binary search on answer, and mastery of union-find data structure.

Common Follow-ups

• What if diagonal moves were allowed? → Adjust adjacency checks accordingly.
• Can you solve using Dijkstra's algorithm? → Yes, treat elevations as edge weights and find min max elevation path.

💡 These follow-ups test your flexibility in adapting the solution and knowledge of alternative graph algorithms.

🔍

Pattern Recognition

When to Use

1) Problem involves connectivity or path in grid/graph with constraints; 2) Constraints depend on a threshold (like water level); 3) Need to minimize maximum value on path; 4) Can sort or binary search on answer.

Signature Phrases

minimum time to reachwater level risesadjacent cells reachable if elevation ≤ timeminimize the maximum elevation on path

NOT This Pattern When

Problems that require shortest path sum or fixed edge weights without threshold constraints

Similar Problems

Path With Minimum Effort - similar minimize max edge weight problemMinimum Cost to Connect All Points - uses union-find for connectivityNetwork Delay Time - shortest path with delays, alternative approach

Practice

1. Consider the following Python code implementing Kruskal's MST with union by size and path compression. Given the input graph with edges [(0,1,1), (1,2,2), (0,2,3)] and n=3, what is the value of mst_weight after processing all edges?

easy

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (0,1,1), (1,2,2), (0,2,3)

2. Step 2: Process edges and union sets

   Union(0,1) succeeds, mst_weight=1; Union(1,2) succeeds, mst_weight=3; Union(0,2) fails (already connected).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of edges in MST is 1+2=3 [OK]

Hint: Sum weights of first n-1 edges that connect components [OK]

Common Mistakes:

• Adding all edges regardless of cycle
• Off-by-one in edges_used count
• Misordering edges before union

2. Consider the following Python code implementing the optimal solution for the problem. Given the input n = 4 and edges = [[3,1,2],[3,2,3],[1,1,3],[2,3,4]], what is the final return value of max_num_edges_to_remove_sorted(n, edges)?

easy

A. 3

B. 2

C. 1

D. -1

Solution

1. Step 1: Sort edges by type descending

   Edges sorted: type 3 edges first: [3,1,2], [3,2,3], then type 1: [1,1,3], then type 2: [2,3,4].

2. Step 2: Process edges with union-find

   Type 3 edges connect nodes 0-1 and 1-2 for both Alice and Bob, used=2. Type 1 edge connects 0-2 for Alice, but already connected, so no increment. Type 2 edge connects 2-3 for Bob, used=3 total. Both have count=1 (fully connected). Edges used=3, total edges=4, so removable=1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Used edges=3, removable=4-3=1 -> careful: used=3, removable=1 [OK]

Hint: Count used edges after union-find merges [OK]

Common Mistakes:

• Off-by-one in indexing nodes
• Ignoring type 3 edges first
• Counting used edges incorrectly

3. What is the time complexity of the optimized Union-Find solution with path compression and union by rank for the Number of Operations to Make Network Connected problem, given n nodes and connections.length = m?

medium

A. O(n * m) due to nested loops over nodes and connections

B. O(m log n) due to union by rank tree height

C. O(m + n^2) because union operations can degrade to quadratic

D. O(m * α(n)) where α(n) is the inverse Ackermann function, nearly constant

Solution

1. Step 1: Analyze union-find operations

   Each union/find operation runs in amortized O(α(n)) time with path compression and union by rank.

2. Step 2: Multiply by number of connections

   We perform m union operations, so total time is O(m * α(n)), which is almost linear.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Union-Find with optimizations is near-linear, not quadratic or log-linear [OK]

Hint: Inverse Ackermann function α(n) is almost constant [OK]

Common Mistakes:

• Assuming union-find is O(m log n)
• Confusing n and m in complexity
• Thinking union-find degrades to O(n*m)

4. The following code attempts to find a redundant connection using union-find but contains a subtle bug. Identify the line causing incorrect behavior.

medium

A. Line setting parent[i] = i in the for loop

B. Line incrementing rank[rootA] after union

C. Line checking if rootA == rootB in union function

D. Line initializing parent with zeros: parent = [0]*(n+1)

Solution

1. Step 1: Analyze parent array initialization

   Initializing parent with zeros causes all nodes to initially point to 0, which is incorrect for 1-based nodes.

2. Step 2: Check for correct parent assignment

   The for loop tries to fix this, but if n=0, loop may not run properly or indexing may be off; better to initialize parent as list(range(n+1)) directly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect parent initialization leads to wrong find results [OK]

Hint: Parent array must be initialized to self indices [OK]

Common Mistakes:

• Forgetting to initialize parent properly
• Assuming zeros are valid parents
• Misindexing parent array

5. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order