Solution: Path With Minimum Effort

Problem Statement

You are given a 2D array heights[][] of size n x m, where heights[n][m] represents the height of the cell (n, m).

Find a path from the top-left corner to the bottom-right corner that minimizes the effort required to travel between consecutive points, where effort is defined as the absolute difference in height between two points. In a single step, you can either move up, down, left or right.

Return the minimum effort required for any path from the first point to the last.

Examples

Example 1:

Input: heights =

.....

Like the course? Get enrolled and start learning!

Ike Nwankwo

· 2 years ago

class Solution:

def minimumEffortPath(self, heights: List[List[int]]) -> int:

    row = len(heights)

    col = len(heights[0])

    difference_matrix = [[math.inf]*col for _ in range(row)]

    difference_matrix[0][0] = 0

    visited = [[False]*col for _ in range(row)]

    queue = [(0, 0, 0)]  # difference, x, y

    while queue:

        difference, x, y = heapq.heappop(queue)

        visited[x][y] = True

        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:

            adjacent_x = x + dx

            adjacent_y = y + dy

            if 0 <= adjacent_x < row and 0 <= adjacent_y < col and not visited[

                    adjacent_x][adjacent_y]:

                current_difference = abs(

Mohammed Dh Abbas

· 2 years ago

Standard Dijkstra finds the shortest path in directed graph. we could treat the matrix as directed graph.

instead of calculating the new distance to reach a node we could calculate the effort to reach that node "that's the modification "

time complexity = O((NM) log (NM))

from heapq import * 

class Solution:

    def get_neighbors(self, x, y, heights):
        alpha_rows = [-1, 0, 1, 0]
        alpha_cols = [0, 1, 0, -1]
        neighbors = []
        for i in range(len(alpha_rows)):
            row = x + alpha_rows[i]
            col = y + alpha_cols[i]
            if row >= 0 and row < len(heights) and col >= 0 and col < len(heights[0]):
                neighbors.append([row, col])
        return neighbors

    def minimumEffortPath(self, heights):
        cols = l