Swim in Rising Water — LeetCode 778 Python Solution
HardDepth-First SearchBreadth-First SearchUnion FindArrayBinary SearchMatrixHeap (Priority Queue)
- Problem
- #778
- Pattern
- Union-Find
- Reading time
- 4 min
- Source
- leetcode.com
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). It starts raining, and water gradually rises over time.
Example
- Input
- grid = [[0,2],[1,3]]
- Output
- 3
- Explanation
- At time 0, you are in grid location (0, 0).
Python solution
Python
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(grid)
m = n * n
p = list(range(m))
hi = [0] * m
for i, row in enumerate(grid):
for j, h in enumerate(row):
hi[h] = i * n + j
dirs = (-1, 0, 1, 0, -1)
for t in range(m):
x, y = divmod(hi[t], n)
for dx, dy in pairwise(dirs):
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] <= t:
p[find(x * n + y)] = find(nx * n + ny)
if find(0) == find(m - 1):
return t
return 0Complexity
| Measure | Complexity |
|---|---|
| Time | O(n^2 \times \log n) |
| Space | O(n^2), where n is the side length of the matrix auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 778. Swim in Rising Water is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
LeetCode 1631Path With Minimum EffortMediumLeetCode 1970Last Day Where You Can Still CrossHardLeetCode 2812Find the Safest Path in a GridMediumLeetCode 378Kth Smallest Element in a Sorted MatrixMediumLeetCode 1337The K Weakest Rows in a MatrixEasyLeetCode 1439Find the Kth Smallest Sum of a Matrix With Sorted RowsHard
On a study list
This problem is on NeetCode 150.
Frequently asked questions
- How hard is LeetCode 778. Swim in Rising Water?
- LeetCode 778. Swim in Rising Water is rated Hard on LeetCode.
- What is the time complexity of LeetCode 778. Swim in Rising Water?
- The Python solution on this page runs in O(n^2 \times \log n).
- What is the space complexity of LeetCode 778. Swim in Rising Water?
- The Python solution on this page uses O(n^2), where n is the side length of the matrix auxiliary space.
- What topics does LeetCode 778. Swim in Rising Water cover?
- LeetCode 778. Swim in Rising Water is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Binary Search, Matrix and Heap (Priority Queue) on LeetCode.