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 uniq

Try it yourself

Try solving this question here: