Swim in Rising Water
You are given an n × n grid where:
grid[i][j]
represents the elevation of the cell at position (i, j).
At time t, you can enter a cell only if:
grid[i][j] <= t
You start at:
(0, 0)
and need to reach:
(n - 1, n - 1)
You can move:
up
down
left
right
Return the minimum time at which you can reach the destination.
Example
grid =
[
[0, 2],
[1, 3]
]
A possible path is:
0 → 1 → 3
The highest elevation along this path is:
3
Therefore, the minimum required time is:
3
Main Idea
This is a Graph + Heap + Dijkstra problem.
Treat every cell as a graph node.
Moving between adjacent cells has a cost determined by the maximum elevation encountered so far.
For a path:
0 → 1 → 3
the required time is:
max(0, 1, 3) = 3
So instead of minimizing the sum of edge weights, we minimize the maximum value on the path.
Dijkstra Approach
For each cell, maintain the minimum possible time required to reach it.
When moving from:
(r, c)
to:
(nr, nc)
the new time is:
max(currentTime, grid[nr][nc])
Always process the cell with the smallest current time using a min-heap.
The first time we reach the bottom-right cell, we have the minimum answer.
Example 1
Input
2 0 2 1 3
Output
3
Explanation
Possible path:
(0,0) → (1,0) → (1,1)
Elevations:
0 → 1 → 3
The required time is:
max(0, 1, 3) = 3
Therefore:
3
Example 2
Input
5 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
An optimal path is:
0 → 1 → 2 → 3 → 4 → 5
↓
24 23 22 21 5
↓
12 13 14 15 16
The highest elevation encountered is:
16
Therefore, the minimum time is:
16
Constraints
Hints:
Hint 1
Think of every cell as a node in a graph.
Hint 2
The cost of a path is not the sum of elevations.
It is the maximum elevation encountered along the path.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 16, 2026
Last updated
Aug 17, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output