Practice/Meta/Leetcode 778. Swim in Rising Water

Leetcode 778. Swim in Rising Water

CodingMust

Problem

You are given an n × n grid where each cell contains a unique elevation value from 0 to n² - 1. Imagine water gradually rising over time, starting at level 0. At time t, you can walk on any cell with elevation at most t.

You start at the top-left corner (0, 0) and want to reach the bottom-right corner (n-1, n-1). You can move in four directions: up, down, left, or right.

Find the minimum time t at which there exists a valid path from the starting position to the destination, where every cell along the path has elevation at most t.

Requirements

1. Return the minimum time value that allows a path from top-left to bottom-right
2. Movement is restricted to 4-directional (no diagonal movement)
3. At time t, only cells with elevation ≤ t are accessible
4. The answer is the minimum value of t for which a valid path exists

Constraints

• n == grid.length
• n == grid[i].length
• 1 ≤ n ≤ 50
• 0 ≤ grid[i][j] < n²
• Each value grid[i][j] is unique

Examples

Example 1:

Input: grid = [[0, 2], [1, 3]] Output: 3 Explanation: At time 3, we can walk through cells with elevation ≤ 3. Path: (0,0) → (0,1) → (1,1) with elevations [0, 2, 3] Or: (0,0) → (1,0) → (1,1) with elevations [0, 1, 3] Both paths require time 3 (the maximum elevation encountered).

Example 2:

Input: grid = [[0, 1, 2], [8, 7, 3], [6, 5, 4]] Output: 4 Explanation: The optimal path is 0 → 1 → 2 → 3 → 4. The maximum elevation along this path is 4.

Example 3:

Input: grid = [[0]] Output: 0 Explanation: Already at the destination.