Problem statement

https://binarysearch.com/problems/Shortest-Absolute-Value-Distance/

Solution

Create graph and the use dijkstra.

Complexity

It is O(mn*log(mn)) for time and O(mn*log(mn)) for space.

Code

class Solution:
    def solve(self, M):
        G = defaultdict(list)
        m, n = len(M), len(M[0])
        for x in range(m):
            for y in range(n):
                for dx, dy in (x, y-1), (x, y+1), (x-1, y), (x+1, y):
                    if 0 <= dx < m and 0 <= dy < n:
                        G[x*n + y] += [(dx*n + dy, abs(M[x][y] - M[dx][dy]))]
        
        q, t = [(0, 0)], {}
        while q:
            time, node = heappop(q)
            if node not in t:
                t[node] = time
                for v, w in G[node]:
                    heappush(q, (time + w, v))
        return t[m*n - 1]