## Similar Problems

Similar Problems not available

# Path With Minimum Effort - Leetcode Solution

LeetCode: Path With Minimum Effort Leetcode Solution

Difficulty: Medium

Topics: binary-search depth-first-search union-find breadth-first-search matrix heap-priority-queue array

The "Path With Minimum Effort" problem on LeetCode asks for the minimum effort required to traverse a grid from the upper left corner to the lower right corner, where the cells have different weights. The approach to solving this problem involves using Dijkstra's algorithm.

Dijkstra's algorithm is a graph algorithm used to find the shortest path between nodes in a directed or undirected graph. In this case, the grid can be considered as a graph, where each cell is a node and the edges between them represent the paths that can be taken to move from one cell to another.

To apply Dijkstra's algorithm, we first create a priority queue of cells, sorted by increasing effort. We start with the source cell (upper left corner) and initialize its effort as 0. We then add the source cell to the priority queue and start processing cells from the queue.

For each cell in the queue, we check its neighboring cells and calculate the effort required to move from the current cell to the neighboring cell. If the effort is less than the current effort stored for the neighboring cell, we update the effort and add the neighboring cell to the priority queue. We continue this process until we reach the destination (lower right corner) or until the priority queue is empty.

After we have processed all the cells, the minimum effort required to traverse the grid is stored in the effort value of the destination cell.

Here's an implementation for the problem:

```
import heapq
def minimumEffortPath(heights: List[List[int]]) -> int:
# initialize source, destination, and directions
m = len(heights)
n = len(heights[0])
src = (0, 0)
dest = (m - 1, n - 1)
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
# create priority queue and visited set
pq = []
heapq.heappush(pq, (0, src))
visited = set()
# dijkstra's algorithm
while pq:
effort, cell = heapq.heappop(pq)
if cell == dest:
return effort
if cell in visited:
continue
visited.add(cell)
r, c = cell
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
new_effort = max(effort, abs(heights[nr][nc] - heights[r][c]))
heapq.heappush(pq, (new_effort, (nr, nc)))
return -1 # destination is not reachable
```

In this implementation, we first initialize the source, destination, and directions. We then create a priority queue and a visited set. We push the source cell to the priority queue with a 0 effort and start processing the cells.

For each cell, we check if it is the destination or if it has already been visited. If not, we add it to the visited set and check its neighboring cells. If a neighboring cell has not been visited and is within the bounds of the grid, we calculate the new effort required to move from the current cell to the neighboring cell. We then add the neighboring cell to the priority queue with the new effort.

After processing all the cells, we check if the destination has been reached. If so, we return the effort required to reach it. Otherwise, we return -1 to indicate that the destination is not reachable.

Overall, this implementation has a time complexity of O(mn log(mn)) and a space complexity of O(mn). The time complexity is due to the use of the priority queue and the space complexity is due to the visited set.

## Path With Minimum Effort Solution Code

`1`