1631. Path With Minimum Effort

This problem asks to find the minimum effort required to travel from the top-left cell (0, 0) to the bottom-right cell (rows-1, columns-1) in a 2D array of heights. The effort is defined as the maximum absolute difference in heights between consecutive cells along a path.

We can solve this using three main approaches: Union-Find, Binary Search + BFS, and Dijkstra's Algorithm with a Heap.

Solution 1: Union-Find

This approach cleverly transforms the problem into a minimum spanning tree problem.

Approach:

1. Create Edges: We represent the grid as a graph where each cell is a node. An edge connects adjacent cells, and its weight is the absolute difference in height between those cells. We create a list of all these edges.

2. Sort Edges: We sort the edges in ascending order of their weights.

3. Union-Find: We use a Union-Find data structure to track connected components. Initially, each cell is its own component.

4. Iterative Union: We iterate through the sorted edges. For each edge, we check if the two connected nodes belong to different components. If they do, we unite the components using the Union-Find's union operation and record the current edge's weight.

5. Termination: We stop when the top-left and bottom-right cells belong to the same component. The weight of the last edge added is the minimum effort required because we've connected the two cells using the smallest possible maximum edge weight.

Time Complexity: O(MN log(MN)), where M and N are the number of rows and columns respectively. This is dominated by the sorting of edges.

Space Complexity: O(M*N) to store the Union-Find data structure and the edges.

Code (Python):

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n
 
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
 
    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True
 
    def connected(self, a, b):
        return self.find(a) == self.find(b)
 
 
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        uf = UnionFind(m * n)
        edges = []
        for i in range(m):
            for j in range(n):
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n:
                        edges.append((abs(heights[i][j] - heights[x][y]), i * n + j, x * n + y))
        edges.sort()
        for w, u, v in edges:
            uf.union(u, v)
            if uf.connected(0, m * n - 1):
                return w
        return 0
 

Solution 2: Binary Search + BFS

This approach leverages the monotonic nature of the problem.

Approach:

1. Binary Search: We perform a binary search on the possible range of maximum effort (0 to the maximum height difference in the grid).

2. BFS Check: For each potential maximum effort mid in the binary search, we use Breadth-First Search (BFS) to check if there exists a path from (0,0) to (rows-1, columns-1) where the maximum difference between adjacent cells is less than or equal to mid.

3. Refinement: If a path exists for a given mid, it means we might be able to find a path with even less effort, so we search in the lower half. Otherwise, we search in the upper half.

Time Complexity: O(MN log(H)), where H is the maximum height difference. The log(H) factor comes from the binary search. Each BFS takes O(MN) in the worst case.

Space Complexity: O(M*N) for the visited set in BFS.

Code (Python):

from collections import deque
 
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        def bfs(effort):
            q = deque([(0, 0)])
            visited = {(0, 0)}
            while q:
                r, c = q.popleft()
                if r == len(heights) - 1 and c == len(heights[0]) - 1:
                    return True
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < len(heights) and 0 <= nc < len(heights[0]) and \
                            abs(heights[nr][nc] - heights[r][c]) <= effort and (nr, nc) not in visited:
                        q.append((nr, nc))
                        visited.add((nr, nc))
            return False
        
        left, right = 0, 10**6  #Adjust range as needed based on constraints
        ans = right
        while left <= right:
            mid = (left + right) // 2
            if bfs(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans
 

Solution 3: Dijkstra's Algorithm with Heap

This is a more general shortest path algorithm suitable for weighted graphs.

Approach:

1. Graph Representation: Similar to the Union-Find approach, we represent the grid as a graph.

2. Dijkstra's: We use Dijkstra's algorithm to find the shortest path from (0,0) to (rows-1, columns-1). The weight of each edge is the absolute difference in height between adjacent cells. The "shortest path" in this context is the path with the minimum maximum edge weight.

3. Priority Queue (Heap): We use a min-heap (priority queue) to efficiently select the node with the minimum maximum edge weight encountered so far.

Time Complexity: O(MN log(MN)) due to the heap operations.

Space Complexity: O(M*N) for the distance array and heap.

Code (Python):

import heapq
 
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        pq = [(0, 0, 0)]  # (effort, row, col)
        while pq:
            d, r, c = heapq.heappop(pq)
            if d > dist[r][c]:
                continue
            if r == m - 1 and c == n - 1:
                return d
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    new_d = max(d, abs(heights[nr][nc] - heights[r][c]))
                    if new_d < dist[nr][nc]:
                        dist[nr][nc] = new_d
                        heapq.heappush(pq, (new_d, nr, nc))
        return 0
 

All three solutions correctly solve the problem. The choice of which to use depends on your preference and understanding of graph algorithms. Union-Find might be slightly simpler conceptually, but Dijkstra's algorithm is a more broadly applicable shortest path algorithm. Binary Search + BFS offers a different approach and might perform better in some specific scenarios. Remember to handle edge cases and potential overflows appropriately.