How do you solve Swim in Rising Water on LeetCode?

Swim in Rising Water (LeetCode #778) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n² log n) time complexity and O(n²) space complexity. Key insight: Using a priority queue allows us to efficiently explore the grid based on elevation.

What is the brute force solution for Swim in Rising Water?

The brute force approach for Swim in Rising Water is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible time 't' to see if we can reach the bottom-right corner from the top-left corner. This is done by simulating the swimming process for each time until we find the minimum time needed. The optimal Optimal Solution approach improves this to O(n² log n).

What are the interview tips for Swim in Rising Water?

Explain your thought process clearly while coding. Discuss the trade-offs of different approaches before diving into the code. Practice writing clean and efficient code, as readability matters.

What are common mistakes when solving Swim in Rising Water?

Not considering the boundaries of the grid when moving to adjacent cells. Forgetting to mark cells as visited, leading to infinite loops.

#778

Swim in Rising Water

Hard

ArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixPriority QueueGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n² log n)
Space	O(1)	O(n²)

💡

Intuition

Time O(n² log n)Space O(n²)

The optimal solution uses a priority queue (min-heap) to explore the grid based on the elevation of the cells. This allows us to efficiently find the minimum time required to reach the bottom-right corner by always expanding the least elevation cell first.

⚙️

Algorithm

4 steps

1Step 1: Initialize a priority queue and push the starting cell (0, 0) with its elevation.
2Step 2: While the queue is not empty, pop the cell with the smallest elevation.
3Step 3: If this cell is the bottom-right corner, return its elevation as the minimum time.
4Step 4: For each adjacent cell, if it hasn't been visited and its elevation is less than or equal to the current elevation, push it onto the queue.

solution.py16 lines

1import heapq
2
3def swimInWater(grid):
4    n = len(grid)
5    pq = [(grid[0][0], 0, 0)]
6    visited = set()
7    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
8    while pq:
9        elevation, x, y = heapq.heappop(pq)
10        if (x, y) == (n - 1, n - 1):
11            return elevation
12        visited.add((x, y))
13        for dx, dy in directions:
14            nx, ny = x + dx, y + dy
15            if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited:
16                heapq.heappush(pq, (max(elevation, grid[nx][ny]), nx, ny))

ℹ

Complexity note: The time complexity is O(n² log n) due to the priority queue operations, where we may push and pop from the queue for each cell, and the space complexity is O(n²) for the visited array.

1Using a priority queue allows us to efficiently explore the grid based on elevation.
2The problem can be visualized as finding the shortest path in a weighted graph where weights are the elevations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.