Loading 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). The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim. Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).
Example 1
Input: grid = [[0,2],[1,3]]
Output: 3
Explanation: The bottom-right square itself has elevation 3, so you cannot stand on it until t = 3. At t = 3, the path 0 → 1 → 3 is open.
Example 2
Input: grid = [[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: The cheapest route follows the top row (0-4), goes down to 5, cuts left through the middle row (16, 15, 14, 13, 12), goes down the left side (11, 10) and right along the bottom (9, 8, 7, 6). The highest square on it is 16, so t = 16.
Example 3
Input: grid = [[0]]
Output: 0
Explanation: You start on the target square, so no waiting is needed: t = 0.
The time to reach the end along a path is the maximum elevation on that path. Dijkstra with a min-heap always expands the cell reachable at the smallest such maximum, so the first time we pop the target is the answer.
Run checks all cases above. Submit evaluates all test cases.