Swim in Rising Water

Problem Statement

You are given a square 2-D matrix of distinct integers grid where each integer grid[i][j] represents the elevation at position (i, j).

Rain starts to fall at time = 0, which causes the water level to rise. At time t, the water level across the entire grid is t.

You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time t.

Starting from the top left square (0, 0), return the minimum amount of time it will take until it is possible to reach the bottom right square (n - 1, n - 1).

Example 1:

Input: grid = [[0,1],[2,3]]


Output: 3

Explanation: For a path to exist to the bottom right square grid[1][1] the water elevation must be at least 3. At time t = 3, the water level is 3.

Example 2:

Input: grid = [
  [0,1,2,10],
  [9,14,4,13],
  [12,3,8,15],
  [11,5,7,6]]
]


Output: 8

Explanation: The water level must be at least 8 to reach the bottom right square. The path is [0, 1, 2, 4, 8, 7, 6].

Constraints:

  • grid.length == grid[i].length
  • 1 <= grid.length <= 50
  • 0 <= grid[i][j] < n^2

You should aim for a solution with O(n^2 \log n) time and O(n^2) space, where $n$ is the number of rows or columns of the square matrix.

You should aim for a solution with O(n^2 \log n) time and O(n^2) space, where $n$ is the number of rows or columns of the square matrix.

Hint 1

Think of this problem as a graph where each cell represents a node. You can move from one cell to its adjacent cell if the time is greater than or equal to the adjacent cell’s elevation. Note that swimming does not cost time, but you may need to wait at a cell for the time to reach the required elevation. What do you notice about the path from (0, 0) to (n - 1, n - 1)? Perhaps a greedy approach would be useful here.

Hint 2

We can observe that the maximum elevation value along the path determines the time taken for that path. Therefore, we need to find the path where the maximum elevation is minimized. Can you think of an algorithm to find such a path from the source (0, 0) to the destination (n - 1, n - 1)? Perhaps a shortest path algorithm could be useful here.

Hint 3

We can use Dijkstra’s algorithm. We initialize a Min-heap and a matrix with infinity. We run the algorithm starting from the source (0, 0), and we track the maximum elevation encountered along the paths. This maximum elevation is used as the key for comparison in Dijkstra’s algorithm. If we encounter the destination (n - 1, n - 1), we return the maximum elevation of the path that reached the destination.

Solution

Brute Force

def swim_in_water_brute_force(grid: List[List[int]]) -> int:
    n = len(grid)
    visit = [[False] * n for _ in range(n)]


    def dfs(node, t):
        r, c = node
        if min(r, c) < 0 or max(r, c) >= n or visit[r][c]:
            return 1000000
        if r == (n - 1) and c == (n - 1):
            return max(t, grid[r][c])
        visit[r][c] = True
        t = max(t, grid[r][c])
        res = min(dfs((r + 1, c), t),
                   dfs((r - 1, c), t),
                   dfs((r, c + 1), t),
                   dfs((r, c - 1), t))
        visit[r][c] = False
        return res


    return dfs((0, 0), 0)

Time complexity: O(4^{n^2}) Space complexity: O(n^2)

def swim_in_water_dfs(grid: List[List[int]]) -> int:
    n = len(grid)
    visit = [[False] * n for _ in range(n)]
    min_h = max_h = grid[0][0]
    for row in range(n):
        max_h = max(max_h, max(grid[row]))
        min_h = min(min_h, min(grid[row]))


    def dfs(node, t):
        r, c = node
        if (min(r, c) < 0 or max(r, c) >= n or
            visit[r][c] or grid[r][c] > t):
            return False
        if r == (n - 1) and c == (n - 1):
            return True
        visit[r][c] = True
        return (dfs((r + 1, c), t) or
                dfs((r - 1, c), t) or
                dfs((r, c + 1), t) or
                dfs((r, c - 1), t))


    for t in range(min_h, max_h):
        if dfs((0, 0), t):
            return t
        for r in range(n):
            for c in range(n):
                visit[r][c] = False


    return max_h

Time complexity: O(n^4) Space complexity: O(n^2)

Binary Search + DFS

def swim_in_water_binary_search_dfs(grid: List[List[int]]) -> int:
    n = len(grid)
    visit = [[False] * n for _ in range(n)]
    min_h = max_h = grid[0][0]
    for row in range(n):
        max_h = max(max_h, max(grid[row]))
        min_h = min(min_h, min(grid[row]))


    def dfs(node, t):
        r, c = node
        if (min(r, c) < 0 or max(r, c) >= n or
            visit[r][c] or grid[r][c] > t):
            return False
        if r == (n - 1) and c == (n - 1):
            return True
        visit[r][c] = True
        return (dfs((r + 1, c), t) or
                dfs((r - 1, c), t) or
                dfs((r, c + 1), t) or
                dfs((r, c - 1), t))


    l, r = min_h, max_h
    while l < r:
        m = (l + r) >> 1
        if dfs((0, 0), m):
            r = m
        else:
            l = m + 1
        for row in range(n):
            for col in range(n):
                visit[row][col] = False


    return r

Time complexity: O(n^2 \log n) Space complexity: O(n^2)

Dijkstra’s Algorithm

import heapq


def swim_in_water_dijkstra(grid: List[List[int]]) -> int:
    n = len(grid)
    visit = set()
    min_heap = [[grid[0][0], 0, 0]]  # (time/max-height, r, c)
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]


    visit.add((0, 0))
    while min_heap:
        t, r, c = heapq.heappop(min_heap)
        if r == n - 1 and c == n - 1:
            return t
        for dr, dc in directions:
            nei_r, nei_c = r + dr, c + dc
            if (nei_r < 0 or nei_c < 0 or
                nei_r == n or nei_c == n or
                (nei_r, nei_c) in visit
            ):
                continue
            visit.add((nei_r, nei_c))
            heapq.heappush(min_heap, [max(t, grid[nei_r][nei_c]), nei_r, nei_c])

Time complexity: O(n^2 \log n) Space complexity: O(n^2)

Kruskal’s Algorithm

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)


    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]


    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.parent[pv] = pu
        return True


    def connected(self, u, v):
        return self.find(u) == self.find(v)


def swim_in_water_kruskal(grid: List[List[int]]) -> int:
    n = len(grid)
    dsu = DSU(n * n)
    positions = sorted((grid[r][c], r, c) for r in range(n) for c in range(n))
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]


    for t, r, c in positions:
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] <= t:
                dsu.union(r * n + c, nr * n + nc)
        if dsu.connected(0, n * n - 1):
            return t

Time complexity: O(n^2 \log n) Space complexity: O(n^2)