Problem Statement

You are given a 2D grid of size n x n containing integers, 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, and 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.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left corner (0,0) to the bottom-right corner (n-1, m-1).

Examples

Example 1

• Input:

grid = 
 [[0, 8, 2],
  [6, 7, 5],
  [4, 3, 1]]

• Expected Output: 6
• Explanation: Wait until time 6. So, 0 and 6 will be connected. After that, you can travel 0 -> 6 -> 4 -> 3 -> 1 in 0 time.

Example 2

• Input:

grid = 
 [[1, 3, 0],
  [6, 5, 4],
  [7, 2, 8]]

• Expected Output: 8
• Explanation: You need to wait until time 8. So, water depth becomes 8 and you can travel from top to bottom corner in 0 time.

Example 3

• Input:

grid = 
 [[1, 2, 3, 4],
  [0, 5, 6, 7],
  [15, 8, 9, 10],
  [14, 11, 12, 13]]

• Expected Output: 13
• Explanation: Wait until time 13. After that, you can travel 1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 13 in 0 time.

Constraints:

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

Solution

To solve this problem, we can use a modified version of Dijkstra's algorithm. Instead of finding the shortest path in terms of distance, we will find the path with the minimum maximum effort. This is done by maintaining a priority queue that always expands the node with the least effort. By continually updating the efforts and pushing neighboring cells into the queue, we can ensure that the first time we reach the bottom-right cell, we have done so with the minimum possible effort.

This approach is effective because Dijkstra's algorithm is designed to find the shortest path in weighted graphs, which aligns well with our goal of finding the path with the minimum maximum effort. By leveraging the priority queue, we can efficiently manage the exploration of cells and ensure optimal effort calculations.

Step-by-Step Algorithm

1. Initialize variables:

   • Get the size of the grid n.
   • Create a 2D array effort to store the minimum effort needed to reach each cell, initialized to infinity.
   • Create a priority queue pq to process cells based on the minimum effort required to reach them.

2. Set the initial conditions:

   • Set effort[0][0] to grid[0][0].
   • Add the initial cell (grid[0][0], 0, 0) to the priority queue.

3. Define movement directions:

   • Create a list of possible movement directions: down, right, up, and left.

4. Process cells from the priority queue:

   • While the priority queue is not empty:
     • Remove the cell with the minimum effort from the priority queue.
     • If this cell is the bottom-right cell (n-1, n-1), return the current effort.
     • For each possible movement direction:
       • Calculate the new cell coordinates.
       • If the new cell is within grid boundaries:
         • Calculate the effort required to move to this new cell.
         • If this new effort is less than the recorded effort for the new cell:
           • Update the effort for the new cell.
           • Add the new cell and its effort to the priority queue.

5. Return -1 if the bottom-right cell is not reachable (this should never happen with valid input).

Algorithm Walkthrough

Let's go through the algorithm step-by-step using the given input:

grid = [
  [0, 8, 2],
  [6, 7, 5],
  [4, 3, 1]
]

1. Initialize variables:

   • n = 3
   • effort array:

     [
       [0, ∞, ∞],
       [∞, ∞, ∞],
       [∞, ∞, ∞]
     ]
     

   • pq initialized with [(0, 0, 0)].

2. Set initial conditions:

   • effort[0][0] = 0
   • Priority queue pq contains [(0, 0, 0)].

3. Process cells from the priority queue:

   • Dequeue (0, 0, 0):

     • Current effort 0, coordinates (0, 0).
     • Possible directions to move: down (1, 0), right (0, 1), up (-1, 0), left (0, -1).

   • Move to (1, 0):

     • Calculate effort: max(0, 6) = 6.
     • Update effort[1][0] = 6.
     • Add (6, 1, 0) to pq.
     • pq contains [(6, 1, 0)].

   • Move to (0, 1):

     • Calculate effort: max(0, 8) = 8.
     • Update effort[0][1] = 8.
     • Add (8, 0, 1) to pq.
     • pq contains [(6, 1, 0), (8, 0, 1)].

   • Dequeue (6, 1, 0):

     • Current effort 6, coordinates (1, 0).
     • Possible directions to move: down (2, 0), right (1, 1), up (0, 0), left (1, -1).

   • Move to (2, 0):

     • Calculate effort: max(6, 4) = 6.
     • Update effort[2][0] = 6.
     • Add (6, 2, 0) to pq.
     • pq contains [(6, 2, 0), (8, 0, 1)].

   • Move to (1, 1):

     • Calculate effort: max(6, 7) = 7.
     • Update effort[1][1] = 7.
     • Add (7, 1, 1) to pq.
     • pq contains [(6, 2, 0), (8, 0, 1), (7, 1, 1)].

   • Dequeue (6, 2, 0):

     • Current effort 6, coordinates (2, 0).
     • Possible directions to move: down (3, 0), right (2, 1), up (1, 0), left (2, -1).

   • Move to (2, 1):

     • Calculate effort: max(6, 3) = 6.
     • Update effort[2][1] = 6.
     • Add (6, 2, 1) to pq.
     • pq contains [(6, 2, 1), (8, 0, 1), (7, 1, 1)].

   • Dequeue (6, 2, 1):

     • Current effort 6, coordinates (2, 1).
     • Possible directions to move: down (3, 1), right (2, 2), up (1, 1), left (2, 0).

   • Move to (2, 2):

     • Calculate effort: max(6, 1) = 6.
     • Update effort[2][2] = 6.
     • Add (6, 2, 2) to pq.
     • pq contains [(6, 2, 2), (8, 0, 1), (7, 1, 1)].

   • Dequeue (6, 2, 2):

     • Current effort 6, coordinates (2, 2).
     • This is the bottom-right cell, return 6.

The final minimum effort required to reach the bottom-right cell is 6.

Code