You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.
Example 1:
heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explaination: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Your Task:
You don't need to read input or print anything. Your task is to complete the function MinimumEffort() which takes the array height  and Returns the minimum effort required to travel from the top-left cell to the bottom-right cell.
Constraints
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^{6}
 
Expected Time Complexity: O(Elog(V))
Expected Space Complexity: O(N,M)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Starter code: #User function Template for python3



class Solution:

        

    def MinimumEffort(self, a):

        #code here

Solutions:
import heapq

class Solution:

	def MinimumEffort(self, heights):
		row = len(heights)
		col = len(heights[0])
		dis = []
		for i in range(row):
			temp = []
			for j in range(col):
				temp.append(float('inf'))
			dis.append(temp)
		dis[0][0] = 0
		row_dir = [-1, 0, 1, 0]
		col_dir = [0, -1, 0, 1]
		heap = []
		heapq.heappush(heap, [0, 0, 0])
		while len(heap) > 0:
			cur = heapq.heappop(heap)
			cur_dis = cur[0]
			cur_row = cur[1]
			cur_col = cur[2]
			for d in range(4):
				x = cur_row + row_dir[d]
				y = cur_col + col_dir[d]
				if x >= 0 and x < row and (y >= 0) and (y < col):
					new_wt = max(abs(heights[cur_row][cur_col] - heights[x][y]), cur_dis)
					if new_wt < dis[x][y]:
						dis[x][y] = new_wt
						heapq.heappush(heap, [new_wt, x, y])
		return dis[-1][-1]


import heapq

class Solution:

	def MinimumEffort(self, a):
		di = (0, 1, 0, -1)
		dj = (1, 0, -1, 0)
		(m, n) = (len(a), len(a[0]))
		visited = [[False] * n for _ in range(m)]
		h = [(0, 0, 0)]
		while h:
			(effort, i, j) = heapq.heappop(h)
			if visited[i][j]:
				continue
			visited[i][j] = True
			if i + 1 == m and j + 1 == n:
				return effort
			for k in range(4):
				(ii, jj) = (i + di[k], j + dj[k])
				if 0 <= ii < m and 0 <= jj < n and (not visited[ii][jj]):
					newEffort = max(effort, abs(a[i][j] - a[ii][jj]))
					heapq.heappush(h, (newEffort, ii, jj))
		return


import heapq

class Solution:

	def MinimumEffort(self, a):
		ROWS = len(a)
		COLS = len(a[0])
		distances = [[float('inf') for j in range(COLS)] for i in range(ROWS)]
		distances[0][0] = 0
		heap = [(0, 0, 0)]
		heapq.heapify(heap)
		while heap:
			(diff, ri, ci) = heapq.heappop(heap)
			directions = [(ri + 1, ci), (ri - 1, ci), (ri, ci + 1), (ri, ci - 1)]
			for (x, y) in directions:
				if 0 <= x < ROWS and 0 <= y < COLS:
					abs_diff = max(abs(a[ri][ci] - a[x][y]), diff)
					if abs_diff < distances[x][y]:
						distances[x][y] = abs_diff
						heapq.heappush(heap, (abs_diff, x, y))
		return distances[ROWS - 1][COLS - 1]


from queue import PriorityQueue

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		q = PriorityQueue()
		neighbors = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		q.put([0, 0, 0])
		dist = [[10000000] * m for _ in range(n)]
		dist[0][0] = 0
		while not q.empty():
			node = q.get()
			x = node[1]
			y = node[2]
			curr = node[0]
			for i in neighbors:
				try:
					if x - i[0] >= 0 and y - i[1] >= 0:
						val = max(abs(a[x][y] - a[x - i[0]][y - i[1]]), dist[x][y])
						if dist[x - i[0]][y - i[1]] > val:
							dist[x - i[0]][y - i[1]] = val
							q.put([val, x - i[0], y - i[1]])
				except:
					pass
		return dist[n - 1][m - 1]


import heapq as hq

class Solution:

	def MinimumEffort(self, a):
		heights = a
		(n, m) = (len(heights), len(heights[0]))
		maxn = int(1000000000.0)
		dist = [[maxn for x in range(m)] for x in range(n)]
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		q = []
		q.append((0, 0, 0))
		dist[0][0] = 0
		while len(q):
			(dis, x, y) = hq.heappop(q)
			if x == n - 1 and y == m - 1:
				return dis
			for i in range(4):
				newx = x + dr[i]
				newy = y + dc[i]
				if newx >= 0 and newy >= 0 and (newx < n) and (newy < m):
					newdis = max(abs(heights[newx][newy] - heights[x][y]), dis)
					if newdis < dist[newx][newy]:
						dist[newx][newy] = newdis
						hq.heappush(q, (newdis, newx, newy))
		return 0


import heapq

class Solution:

	def MinimumEffort(self, a):
		ROWS = len(a)
		COLS = len(a[0])
		visited = [[False for _ in range(COLS)] for _ in range(ROWS)]
		dis = [[-1 for _ in range(COLS)] for _ in range(ROWS)]
		p = [[0, 0, 0]]
		while p:
			(d, x, y) = heapq.heappop(p)
			if visited[x][y] == True:
				continue
			visited[x][y] = True
			dis[x][y] = d
			if x == ROWS - 1 and y == COLS - 1:
				return d
			for (k, l) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
				if 0 <= x + k < ROWS and 0 <= y + l < COLS and (not visited[x + k][y + l] == True):
					heapq.heappush(p, [max(d, abs(a[x][y] - a[x + k][y + l])), x + k, y + l])
		return -1


from collections import defaultdict
import sys
from heapq import *

class Solution:

	def MinimumEffort(self, a):
		m = len(a)
		n = len(a[0])
		dist = [[sys.maxsize for i in range(n)] for j in range(m)]
		dist[0][0] = 0
		minheap = []
		heappush(minheap, (0, 0, 0))
		while minheap:
			(dis, i, j) = heappop(minheap)
			if i == m - 1 and j == n - 1:
				return dis
			drow = [-1, 0, 1, 0]
			dcol = [0, 1, 0, -1]
			for k in range(4):
				nrow = i + drow[k]
				ncol = j + dcol[k]
				if nrow >= 0 and nrow < m and (ncol >= 0) and (ncol < n):
					maxDiff = max(abs(a[nrow][ncol] - a[i][j]), dis)
					if maxDiff < dist[nrow][ncol]:
						dist[nrow][ncol] = maxDiff
						heappush(minheap, (dist[nrow][ncol], nrow, ncol))
		return -1


from queue import PriorityQueue

class Solution:

	def MinimumEffort(self, heights):
		n = len(heights)
		m = len(heights[0])
		dist = [[999999999 for j in range(m)] for i in range(n)]
		dist[0][0] = 0
		d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		q = PriorityQueue()
		q.put((0, 0, 0))
		while not q.empty():
			temp = q.get()
			diff = temp[0]
			r = temp[1]
			c = temp[2]
			if r == n - 1 and c == m - 1:
				return diff
			for (dr, dc) in d:
				row = r + dr
				col = c + dc
				if row >= 0 and row < n and (col >= 0) and (col < m):
					effort = max(abs(heights[r][c] - heights[row][col]), diff)
					if effort < dist[row][col]:
						dist[row][col] = effort
						q.put((effort, row, col))
		return 0


import heapq

class Solution:

	def MinimumEffort(self, a):
		pq = []
		heapq.heappush(pq, (0, 0, 0))
		n = len(a)
		m = len(a[0])
		dist = [[-1 for _ in range(m)] for _ in range(n)]
		dx = [-1, 0, 0, 1]
		dy = [0, -1, 1, 0]
		dist[0][0] = 0
		while len(pq) > 0:
			(curr_d, x, y) = heapq.heappop(pq)
			for k in range(4):
				nx = x + dx[k]
				ny = y + dy[k]
				if nx >= 0 and nx < n and (ny >= 0) and (ny < m) and (dist[nx][ny] == -1 or max(curr_d, abs(a[nx][ny] - a[x][y])) < dist[nx][ny]):
					dist[nx][ny] = max(curr_d, abs(a[nx][ny] - a[x][y]))
					heapq.heappush(pq, (dist[nx][ny], nx, ny))
		return dist[n - 1][m - 1]


import heapq

class Solution:

	def MinimumEffort(self, grid):
		dist = []
		for i in range(len(grid)):
			arr = []
			for j in range(len(grid[0])):
				arr.append(99999999)
			dist.append(arr)
		q = [(0, [0, 0])]
		dist[0][0] = 0
		while len(q) != 0:
			node = heapq.heappop(q)
			i = node[1][0]
			j = node[1][1]
			if i == len(grid) - 1 and j == len(grid[0]) - 1:
				return node[0]
			if grid[i][j] == -1:
				continue
			if i - 1 >= 0:
				a = dist[i - 1][j]
				dist[i - 1][j] = max(node[0], abs(grid[i][j] - grid[i - 1][j]))
				if a != dist[i - 1][j] and grid[i - 1][j] != -1:
					heapq.heappush(q, (dist[i - 1][j], [i - 1, j]))
			if i + 1 < len(grid):
				a = dist[i + 1][j]
				dist[i + 1][j] = max(node[0], abs(grid[i][j] - grid[i + 1][j]))
				if a != dist[i + 1][j] and grid[i + 1][j] != -1:
					heapq.heappush(q, (dist[i + 1][j], [i + 1, j]))
			if j - 1 >= 0:
				a = dist[i][j - 1]
				dist[i][j - 1] = max(node[0], abs(grid[i][j] - grid[i][j - 1]))
				if a != dist[i][j - 1] and grid[i][j - 1] != -1:
					heapq.heappush(q, (dist[i][j - 1], [i, j - 1]))
			if j + 1 < len(grid[0]):
				a = dist[i][j + 1]
				dist[i][j + 1] = max(node[0], abs(grid[i][j] - grid[i][j + 1]))
				if a != dist[i][j + 1] and grid[i][j + 1] != -1:
					heapq.heappush(q, (dist[i][j + 1], [i, j + 1]))
			grid[i][j] = -1


import heapq

class Solution:

	def MinimumEffort(self, heights):
		(r, c) = (len(heights), len(heights[0]))
		q = [(0, 0, 0)]
		while q:
			cur = heapq.heappop(q)
			c_eff = cur[0]
			x = cur[1]
			y = cur[2]
			if x == r - 1 and y == c - 1:
				return c_eff
			if heights[x][y] == '':
				continue
			for (dx, dy) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
				newx = x + dx
				newy = y + dy
				if 0 <= newx < r and 0 <= newy < c and (heights[newx][newy] != ''):
					eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
					heapq.heappush(q, (eff, newx, newy))
			heights[x][y] = ''


import heapq

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		new_a = [[999999 for j in range(m)] for i in range(n)]
		hp = []
		heapq.heappush(hp, [0, 0, 0])
		dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while hp:
			p = heapq.heappop(hp)
			if new_a[p[1]][p[2]] > p[0]:
				new_a[p[1]][p[2]] = p[0]
				for (d1, d2) in dir:
					x = d1 + p[1]
					y = d2 + p[2]
					if x >= n or x < 0 or y >= m or (y < 0):
						continue
					abslt = max(p[0], abs(a[x][y] - a[p[1]][p[2]]))
					heapq.heappush(hp, [abslt, x, y])
		return new_a[n - 1][m - 1]


import heapq
from collections import deque

class Solution:

	def MinimumEffort(self, a):
		ans = 0
		(n, m, pq) = (len(a), len(a[0]), [])
		dist = [[0] * m for _ in range(n)]
		dr = [0, -1, 0, 1, 0]
		heapq.heappush(pq, (0, 0, 0))
		while len(pq) > 0:
			(d, x, y) = heapq.heappop(pq)
			ans = max(ans, d)
			dist[x][y] = 1
			if x == n - 1 and y == m - 1:
				return ans
			for i in range(4):
				dx = x + dr[i]
				dy = y + dr[i + 1]
				if dx >= 0 and dy >= 0 and (dx < n) and (dy < m) and (dist[dx][dy] == 0):
					heapq.heappush(pq, (abs(a[x][y] - a[dx][dy]), dx, dy))
		return ans


import math
from heapq import *

class Solution:

	def MinimumEffort(self, a):
		m = len(a)
		n = len(a[0])
		dist = [[math.inf for j in range(n)] for i in range(m)]
		dist[0][0] = 0
		min_heap = []
		heappush(min_heap, (0, 0, 0))
		dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while min_heap:
			(diff, row, col) = heappop(min_heap)
			if row == m - 1 and col == n - 1:
				return diff
			for dr in dirs:
				new_row = row + dr[0]
				new_col = col + dr[1]
				if new_row >= 0 and new_row < m and (new_col >= 0) and (new_col < n):
					new_effort = max(abs(a[new_row][new_col] - a[row][col]), diff)
					if new_effort < dist[new_row][new_col]:
						dist[new_row][new_col] = new_effort
						heappush(min_heap, (new_effort, new_row, new_col))
		return -1


from heapq import *

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		minheap = []
		dis = [[float('inf') for i in range(m)] for j in range(n)]
		dis[0][0] = 0
		heappush(minheap, [0, [0, 0]])
		d = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		while minheap:
			x = heappop(minheap)
			dif = x[0]
			r = x[1][0]
			c = x[1][1]
			if r == n - 1 and c == m - 1:
				return dif
			for (i, j) in d:
				(newr, newc) = (r + i, c + j)
				if newr >= 0 and newr < n and (newc >= 0) and (newc < m):
					temp = max(abs(a[r][c] - a[newr][newc]), dif)
					if temp < dis[newr][newc]:
						dis[newr][newc] = temp
						heappush(minheap, [temp, [newr, newc]])
		return 0


import heapq as h

class Solution:

	def MinimumEffort(self, a):
		(m, n) = (len(a), len(a[0]))
		dist = [[float('inf') for j in range(n)] for i in range(m)]
		dist[0][0] = 0
		pq = [(0, 0, 0)]
		h.heapify(pq)
		while pq:
			(d, i, j) = h.heappop(pq)
			if i == m - 1 and j == n - 1:
				return dist[m - 1][n - 1]
			for (r, c) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= r < m and 0 <= c < n:
					t = max(abs(a[i][j] - a[r][c]), d)
					if dist[r][c] > t:
						dist[r][c] = t
						h.heappush(pq, (dist[r][c], r, c))


import heapq

class Solution:

	def MinimumEffort(self, a):
		heights = a
		pq = []
		heapq.heappush(pq, (0, 0, 0))
		n = len(heights)
		m = len(heights[0])
		dist = [[float('inf')] * m for _ in range(n)]
		dist[0][0] = 0
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		while pq:
			(diff, row, col) = heapq.heappop(pq)
			if row == n - 1 and col == m - 1:
				return diff
			for i in range(4):
				newr = row + dr[i]
				newc = col + dc[i]
				if 0 <= newr < n and 0 <= newc < m:
					new_effort = max(abs(heights[row][col] - heights[newr][newc]), diff)
					if new_effort < dist[newr][newc]:
						dist[newr][newc] = new_effort
						heapq.heappush(pq, (new_effort, newr, newc))
		return 0


from collections import deque
from heapq import *

class Solution:

	def MinimumEffort(self, a):
		d = [[float('inf')] * len(a[0]) for i in range(len(a))]
		q = []
		q.append([0, [0, 0]])
		d[0][0] = 0
		while q:
			s = heappop(q)
			dist = s[0]
			row = s[1][0]
			col = s[1][1]
			if row == len(a) - 1 and col == len(a[0]) - 1:
				return dist
			for i in [[-1, 0], [0, 1], [1, 0], [0, -1]]:
				srow = row + i[0]
				scol = col + i[1]
				if 0 <= srow < len(a) and 0 <= scol < len(a[0]):
					newdiff = max(dist, abs(a[row][col] - a[srow][scol]))
					if newdiff < d[srow][scol]:
						d[srow][scol] = newdiff
						heappush(q, [newdiff, [srow, scol]])


import heapq

class Solution:

	def MinimumEffort(self, arr):
		n = len(arr)
		m = len(arr[0])
		dist = [[float('inf')] * m for i in range(n)]
		dist[0][0] = 0
		pq = []
		pq.append((0, (0, 0)))
		heapq.heapify(pq)
		while pq:
			it = heapq.heappop(pq)
			dis = it[0]
			r = it[1][0]
			c = it[1][1]
			if r == n - 1 and c == m - 1:
				return dis
			dz = [-1, 0, 1, 0, -1]
			for i in range(4):
				nr = r + dz[i]
				nc = c + dz[i + 1]
				if nr >= 0 and nr < n and (nc >= 0) and (nc < m):
					neweffort = max(dis, abs(arr[r][c] - arr[nr][nc]))
					if neweffort < dist[nr][nc]:
						dist[nr][nc] = neweffort
						heapq.heappush(pq, (neweffort, (nr, nc)))
		return 0


import heapq

class Solution:

	def MinimumEffort(self, grid):
		(n, m) = (len(grid), len(grid[0]))
		DIR = [0, 1, 0, -1, 0]

		def isValid(r, c):
			if r >= 0 and c >= 0 and (r < n) and (c < m):
				return True
			return False
		dis = [[float('inf') for _ in range(m)] for _ in range(n)]
		dis[0][0] = 0
		queue = [(0, 0, 0)]
		while queue:
			(diff, row, col) = heapq.heappop(queue)
			if row == n - 1 and col == m - 1:
				return diff
			for i in range(4):
				(nrow, ncol) = (row + DIR[i], col + DIR[i + 1])
				if isValid(nrow, ncol):
					newEffort = max(abs(grid[row][col] - grid[nrow][ncol]), diff)
					if newEffort < dis[nrow][ncol]:
						dis[nrow][ncol] = newEffort
						heapq.heappush(queue, (newEffort, nrow, ncol))
		return -1


from heapq import heappush, heappop

class Solution:

	def MinimumEffort(self, heights):
		(n, m) = (len(heights), len(heights[0]))
		temp_heights = [[float('inf') for _ in range(m)] for __ in range(n)]
		temp_heights[0][0] = 0
		heap = []
		heappush(heap, [0, 0, 0])
		while heap:
			(curr, r, c) = heappop(heap)
			if r == n - 1 and c == m - 1:
				return curr
			for (nr, nc) in [[-1 + r, c], [1 + r, c], [r, -1 + c], [r, 1 + c]]:
				if nr < 0 or nr >= n or nc < 0 or (nc >= m):
					continue
				newEffort = max(curr, abs(heights[r][c] - heights[nr][nc]))
				if newEffort < temp_heights[nr][nc]:
					temp_heights[nr][nc] = newEffort
					heappush(heap, [newEffort, nr, nc])


from heapq import *

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		heap = []
		dist = [[1000000000.0 for i in range(m)] for i in range(n)]
		dist[0][0] = 0
		heappush(heap, (0, 0, 0))
		mini = 1000000000.0
		while len(heap) != 0:
			(d, row, col) = heappop(heap)
			if row == n - 1 and col == m - 1:
				mini = min(mini, d)
				continue
			delrow = (-1, 0, 1, 0)
			delcol = (0, 1, 0, -1)
			for i in range(4):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m):
					if dist[nrow][ncol] > max(d, abs(a[row][col] - a[nrow][ncol])):
						dist[nrow][ncol] = max(d, abs(a[row][col] - a[nrow][ncol]))
						heappush(heap, (dist[nrow][ncol], nrow, ncol))
		return mini


from heapq import heappush, heappop
from math import inf
inf = float('inf')

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		dis = [[inf for _ in range(m)] for _ in range(n)]
		q = []
		dis[0][0] = 0
		heappush(q, ((0, 0), 0))
		while q:
			item = heappop(q)
			(i, j) = (item[0][0], item[0][1])
			diff = item[1]
			if i == n - 1 and j == m - 1:
				return diff
			dir = [[1, 0], [0, 1], [0, -1], [-1, 0]]
			for (dr, dc) in dir:
				dr += i
				dc += j
				if 0 <= dr < n and 0 <= dc < m:
					new_diff = max(diff, abs(a[i][j] - a[dr][dc]))
					if new_diff < dis[dr][dc]:
						dis[dr][dc] = new_diff
						heappush(q, ((dr, dc), new_diff))


from heapq import *

class Solution:

	def MinimumEffort(self, grid):
		n = len(grid)
		m = len(grid[0])
		dist = [[float('inf')] * m for i in range(n)]
		dist[0][0] = 0
		path = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		heap = [(0, 0, 0)]
		while heap:
			(value, i, j) = heappop(heap)
			for (di, dj) in path:
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < n and 0 <= nj < m:
					cost = abs(grid[i][j] - grid[ni][nj])
					if max(cost, value) < dist[ni][nj]:
						dist[ni][nj] = max(cost, value)
						heappush(heap, (dist[ni][nj], ni, nj))
		return dist[n - 1][m - 1]


import collections
import heapq

class Solution:

	def MinimumEffort(self, a):
		if not a:
			return
		ROWS = len(a)
		COLS = len(a[0])
		q = collections.deque()
		q.append((0, 0, 0))
		q = []
		heapq.heappush(q, (0, 0, 0))
		dist = [[float('inf') for j in range(COLS)] for i in range(ROWS)]
		dist[0][0] = 0
		while q:
			(e, r, c) = heapq.heappop(q)
			for (dr, dc) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				newr = dr + r
				newc = dc + c
				if 0 <= newr < ROWS and 0 <= newc < COLS:
					newEffort = max(abs(a[newr][newc] - a[r][c]), e)
					if newEffort < dist[newr][newc]:
						dist[newr][newc] = newEffort
						heapq.heappush(q, (newEffort, newr, newc))
		return dist[ROWS - 1][COLS - 1]


from heapq import heapify, heappush, heappop

class Solution:

	def MinimumEffort(self, arr):
		q = []
		n = len(arr)
		m = len(arr[0])
		heapify(q)
		heappush(q, (0, (0, 0)))
		dist = [[float('inf') for i in range(m)] for i in range(n)]
		dist[0][0] = 0
		drow = [-1, 0, +1, 0]
		dcol = [0, 1, 0, -1]
		while q:
			item = heappop(q)
			km = item[0]
			row = item[1][0]
			col = item[1][1]
			for i in range(4):
				r = row + drow[i]
				c = col + dcol[i]
				if r >= 0 and r < n and (c >= 0) and (c < m):
					diff = abs(arr[r][c] - arr[row][col])
					curr = max(diff, km)
					if curr < dist[r][c]:
						dist[r][c] = curr
						heappush(q, (curr, (r, c)))
		return dist[n - 1][m - 1]


import heapq

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		dis = [[float('inf') for j in range(m)] for i in range(n)]
		dis[0][0] = 0
		heap = []
		heapq.heappush(heap, [0, [0, 0]])
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		while len(heap) != 0:
			popped = heapq.heappop(heap)
			diff = popped[0]
			row = popped[1][0]
			col = popped[1][1]
			if row == n - 1 and col == m - 1:
				return diff
			for k in range(len(dr)):
				nr = row + dr[k]
				nc = col + dc[k]
				if 0 <= nr < n and 0 <= nc < m:
					newEffort = max(abs(a[nr][nc] - a[row][col]), diff)
					if newEffort < dis[nr][nc]:
						dis[nr][nc] = newEffort
						heapq.heappush(heap, [newEffort, [nr, nc]])
		return 0


import heapq

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		dist = [[99999 for j in range(m)] for i in range(n)]
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		dist[0][0] = 0
		pq = [(0, 0, 0)]
		while len(pq) > 0:
			(dmax, r, c) = heapq.heappop(pq)
			if r == n - 1 and c == m - 1:
				return dmax
			for i in range(4):
				dr = r + drow[i]
				dc = c + dcol[i]
				if dr >= 0 and dr < n and (dc >= 0) and (dc < m):
					dn = max(abs(a[dr][dc] - a[r][c]), dmax)
					if dn < dist[dr][dc]:
						dist[dr][dc] = dn
						heapq.heappush(pq, (dn, dr, dc))


from queue import PriorityQueue

class Solution:

	def MinimumEffort(self, heights):
		dist = [[float('infinity') for _ in range(len(heights[0]))] for _ in range(len(heights))]
		p = PriorityQueue()
		p.put((0, [0, 0], 0))
		dist[0][0] = 0
		while not p.empty():
			dt = p.get()
			(wt, row, col) = (dt[0], dt[1][0], dt[1][1])
			if row == len(heights) - 1 and col == len(heights[0]) - 1:
				return wt
			dltRow = [-1, 0, 1, 0]
			dltCol = [0, 1, 0, -1]
			for i in range(len(dltRow)):
				(newRow, newCol) = (row + dltRow[i], col + dltCol[i])
				if newRow >= 0 and newRow < len(heights) and (newCol >= 0) and (newCol < len(heights[0])) and (max(abs(heights[newRow][newCol] - heights[row][col]), wt) < dist[newRow][newCol]):
					dist[newRow][newCol] = max(abs(heights[newRow][newCol] - heights[row][col]), wt)
					p.put((dist[newRow][newCol], [newRow, newCol]))


from queue import PriorityQueue

class Solution:

	def MinimumEffort(self, a):
		(n, m) = (len(a), len(a[0]))
		dis = [[1000000000.0] * m for i in range(n)]
		q = PriorityQueue()
		q.put((0, 0, 0))
		dis[0][0] = 0
		row = [0, -1, 0, 1]
		col = [-1, 0, 1, 0]
		while not q.empty():
			(dif, r, c) = q.get()
			for k in range(4):
				ro = row[k] + r
				co = col[k] + c
				if r == n - 1 and c == m - 1:
					return dif
				if ro >= 0 and co >= 0 and (ro < n) and (co < m):
					nd = max(abs(a[r][c] - a[ro][co]), dif)
					if nd < dis[ro][co]:
						dis[ro][co] = nd
						q.put((nd, ro, co))
		return 0


class Solution:

	def MinimumEffort(self, a):
		(m, n) = (len(a), len(a[0]))
		X = [0, 1, 0, -1]
		Y = [1, 0, -1, 0]
		dist = [[float('inf')] * n for _r in range(m)]
		q = [(0, 0)]
		dist[0][0] = 0
		while q:
			(x, y) = q.pop(0)
			for _ in range(4):
				_x = X[_] + x
				_y = Y[_] + y
				if 0 <= _x < m and 0 <= _y < n:
					if dist[_x][_y] > max(dist[x][y], abs(a[_x][_y] - a[x][y])):
						dist[_x][_y] = max(dist[x][y], abs(a[_x][_y] - a[x][y]))
						q.append((_x, _y))
		return dist[m - 1][n - 1]


import heapq as pq

class Solution:
	_dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

	def MinimumEffort(self, heights):
		if not heights or len(heights) == 0:
			return 0
		if len(heights) == 1 and len(heights[0]) == 1:
			return 0
		(N, M) = (len(heights), len(heights[0]))
		queue = []
		pq.heappush(queue, (0, 0, 0))
		elevations = [[float('inf')] * M for _ in range(N)]
		elevations[0][0] = 0
		result = float('inf')
		while queue:
			(height, row, col) = pq.heappop(queue)
			for (dr, dc) in self._dirs:
				(new_r, new_c) = (row + dr, col + dc)
				if not 0 <= new_r < N or not 0 <= new_c < M:
					continue
				curr_elevation = abs(heights[row][col] - heights[new_r][new_c])
				if curr_elevation < elevations[new_r][new_c]:
					pq.heappush(queue, (max(curr_elevation, height), new_r, new_c))
					elevations[new_r][new_c] = curr_elevation
					if new_r == N - 1 and new_c == M - 1:
						result = min(result, max(curr_elevation, height))
		return result


import numpy as np
import queue

class Solution:

	def MinimumEffort(self, a):
		n = len(a)
		m = len(a[0])
		dist = np.full((n, m), 1000000000.0)
		dist[0][0] = 0
		delr = [-1, 0, 1, 0]
		delc = [0, 1, 0, -1]
		pq = queue.PriorityQueue()
		pq.put((0, (0, 0)))
		while pq:
			it = pq.get()
			diff = it[0]
			r = it[1][0]
			c = it[1][1]
			if r == n - 1 and c == m - 1:
				return diff
			for i in range(4):
				newr = r + delr[i]
				newc = c + delc[i]
				if newr > -1 and newr < n and (newc > -1) and (newc < m):
					neweffort = max(abs(a[r][c] - a[newr][newc]), diff)
					if neweffort < dist[newr][newc]:
						dist[newr][newc] = neweffort
						pq.put((neweffort, (newr, newc)))
		return 0


import heapq

class Solution:

	def MinimumEffort(self, a):
		m = len(a)
		n = len(a[0])
		q = [[0, [0, 0]]]
		efforts = [[float('inf')] * n for i in range(m)]
		efforts[0][0] = 0
		dx = [0, 0, -1, 1]
		dy = [-1, 1, 0, 0]
		while q:
			(pres_eff, node) = heapq.heappop(q)
			(x, y) = node
			for k in range(4):
				i = x + dx[k]
				j = y + dy[k]
				if i >= 0 and i < m and (j >= 0) and (j < n):
					absdiff = abs(a[x][y] - a[i][j])
					absdiff = max(pres_eff, absdiff)
					if efforts[i][j] > absdiff:
						heapq.heappush(q, [absdiff, [i, j]])
						efforts[i][j] = absdiff
		return efforts[m - 1][n - 1]


import heapq
import math

class Solution:

	def MinimumEffort(self, heights):
		X = [-1, 1, 0, 0]
		Y = [0, 0, 1, -1]
		q = []
		heapq.heapify(q)
		dis = []
		n = len(heights)
		m = len(heights[0])
		for i in range(n):
			l = []
			for j in range(m):
				l.append(math.inf)
			dis.append(l)
		dis[0][0] = 0
		heapq.heappush(q, (0, 0, 0))
		while q:
			(c, i, j) = heapq.heappop(q)
			if i == n - 1 and j == m - 1:
				return c
			for k in range(4):
				x = i + X[k]
				y = j + Y[k]
				if x >= 0 and x < n and (y >= 0) and (y < m):
					neweffort = max(c, abs(heights[x][y] - heights[i][j]))
					if dis[x][y] > neweffort:
						dis[x][y] = neweffort
						heapq.heappush(q, [neweffort, x, y])


from heapq import heappush, heapify, heappop

class Solution:

	def MinimumEffort(self, a):
		m = len(a)
		n = len(a[0])
		effort = [[float('inf')] * n for i in range(m)]
		effort[0][0] = 0
		heap = [(0, 0, 0)]
		heapify(heap)
		direct = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		c = 0
		while heap:
			(e, r, c) = heappop(heap)
			if r == m - 1 and c == n - 1:
				return e
			for (dr, dc) in direct:
				newR = dr + r
				newC = dc + c
				if min(newR, newC) >= 0 and newR < m and (newC < n):
					newEffort = max(abs(a[r][c] - a[newR][newC]), e)
					if newEffort < effort[newR][newC]:
						effort[newR][newC] = max(abs(a[r][c] - a[newR][newC]), e)
						heappush(heap, (effort[newR][newC], newR, newC))


from collections import deque
from heapq import heappop, heappush, heapify

def solve(a):
	r = len(a)
	c = len(a[0])
	dt = [[999999 for i in range(c)] for j in range(r)]
	dt[0][0] = 0
	q = []
	heappush(q, [0, 0, 0])
	lr = r
	lc = c
	while len(q):
		val = heappop(q)
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		dist = val[0]
		r = val[1]
		c = val[2]
		if r == lr - 1 and c == lc - 1:
			return dist
		for i in range(4):
			nr = r + dr[i]
			nc = c + dc[i]
			if nr > -1 and nr < lr and (nc > -1) and (nc < lc):
				step = abs(a[r][c] - a[nr][nc])
				if dt[nr][nc] > max(step, dist):
					dt[nr][nc] = max(step, dist)
					heappush(q, [max(step, dist), nr, nc])

class Solution:

	def MinimumEffort(self, a):
		return solve(a)


import heapq

class Solution:

	def MinimumEffort(self, heights):
		m = len(heights)
		n = len(heights[0])
		vis = [[False for i in range(n)] for j in range(m)]
		q = []
		heapq.heappush(q, (0, 0, 0))
		while len(q) > 0:
			(val, i, j) = heapq.heappop(q)
			if vis[i][j]:
				continue
			if i == m - 1 and j == n - 1:
				return val
			vis[i][j] = True
			for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= x < m and 0 <= y < n and (not vis[x][y]):
					heapq.heappush(q, (max(val, abs(heights[x][y] - heights[i][j])), x, y))
		return -1


from heapq import heappush, heappop, heapify

class Solution:

	def MinimumEffort(self, a):
		q = [(0, 0, 0)]
		rows = len(a)
		cols = len(a[0])
		dist = [[float('inf')] * cols for _ in range(rows)]
		while q:
			(d, i, j) = heappop(q)
			if i == rows - 1 and j == cols - 1:
				return d
			for (r, c) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
				new_i = i + r
				new_j = j + c
				if new_i < 0 or new_j < 0 or new_i == rows or (new_j == cols):
					continue
				dis = max(d, abs(a[i][j] - a[new_i][new_j]))
				if dist[new_i][new_j] > dis:
					dist[new_i][new_j] = dis
					heappush(q, (dis, new_i, new_j))


from heapq import *

class Solution:

	def MinimumEffort(self, a):
		min_heap = []
		n = len(a)
		m = len(a[0])
		dist = [[10000000 for i in range(m)] for j in range(n)]
		dist[0][0] = 0
		heappush(min_heap, (0, 0, 0))
		dr = [-1, 0, 1, 0]
		dc = [0, 1, 0, -1]
		while min_heap:
			(diff, row, col) = heappop(min_heap)
			if row == n - 1 and col == m - 1:
				return diff
			for i in range(4):
				newr = row + dr[i]
				newc = col + dc[i]
				if newr >= 0 and newc >= 0 and (newr < n) and (newc < m):
					neweffort = max(abs(a[row][col] - a[newr][newc]), diff)
					if neweffort < dist[newr][newc]:
						dist[newr][newc] = neweffort
						heappush(min_heap, (neweffort, newr, newc))
		return 0


import heapq

class Solution:

	def MinimumEffort(self, grid):
		drow = [-1, 0, 1, 0]
		dcol = [0, 1, 0, -1]
		n = len(grid)
		m = len(grid[0])
		dis = [[float('inf') for i in range(m)] for j in range(n)]
		dis[0][0] = 0
		pq = []
		pq.append((0, (0, 0)))
		heapq.heapify(pq)
		while pq:
			(d, a) = heapq.heappop(pq)
			r = a[0]
			c = a[1]
			if [r, c] == [n - 1, m - 1]:
				return d
			for i in range(4):
				x = r + drow[i]
				y = c + dcol[i]
				if x >= 0 and x < n and (y >= 0) and (y < m) and (max(abs(grid[x][y] - grid[r][c]), d) < dis[x][y]):
					dis[x][y] = max(abs(grid[x][y] - grid[r][c]), d)
					heapq.heappush(pq, (dis[x][y], (x, y)))