# Path With Minimum Effort
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-with-minimum-effort)
Canonical: https://scaleengineer.com/dsa/problems/path-with-minimum-effort
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Heap (Priority Queue), Matrix
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Cohesity](https://scaleengineer.com/companies/cohesity)
---
## Problem
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.

Return _the minimum **effort** required to travel from the top-left cell to the bottom-right cell._

**Example 1:**

![](https://assets.glich.co/dsa/path-with-minimum-effort/image0.png)

**Input:** heights = [[1,2,2],[3,8,2],[5,3,5]]
**Output:** 2
**Explanation:** 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.

**Example 2:**

![](https://assets.glich.co/dsa/path-with-minimum-effort/image1.png)

**Input:** heights = [[1,2,3],[3,8,4],[5,3,5]]
**Output:** 1
**Explanation:** The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

**Example 3:**

![](https://assets.glich.co/dsa/path-with-minimum-effort/image2.png) 

**Input:** heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
**Output:** 0
**Explanation:** This route does not require any effort.

**Constraints:**

* `rows == heights.length`
* `columns == heights[i].length`
* `1 <= rows, columns <= 100`
* `1 <= heights[i][j] <= 106`

# Approaches
## Brute Force with Backtracking
This approach explores every possible path from the starting cell (0, 0) to the destination (rows-1, columns-1) using recursion (Depth First Search). For each path, it calculates the effort, which is the maximum absolute height difference between consecutive cells. The minimum effort found across all paths is the result.
**Time:** O(3^(R*C)). From each cell, there are roughly 3 new directions to explore. The number of simple paths is exponential, making this approach infeasible for the given constraints. · **Space:** O(R * C) for the recursion stack in the worst case (a path that visits every cell) and the `visited` matrix.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to perform a classic backtracking search on the grid. We define a recursive function that explores paths starting from `(0, 0)`. This function keeps track of the maximum effort encountered so far along the current path.

To prevent infinite loops (e.g., moving back and forth between two cells), we use a `visited` boolean matrix to mark cells that are part of the current path being explored. When the recursion backtracks, we un-mark the cell, allowing it to be part of other potential paths.

The base case for the recursion is when we reach the destination cell `(rows-1, columns-1)`. At this point, we have found one complete path, and we compare its effort with a globally maintained minimum effort, updating it if the current path's effort is smaller.

While simple, this method is highly impractical as the number of paths in a grid grows exponentially with its size.

```java
class Solution {
    int minEffort = Integer.MAX_VALUE;

    public int minimumEffortPath(int[][] heights) {
        backtrack(0, 0, 0, heights, new boolean[heights.length][heights[0].length]);
        return minEffort;
    }

    private void backtrack(int r, int c, int currentMax, int[][] heights, boolean[][] visited) {
        if (r == heights.length - 1 && c == heights[0].length - 1) {
            minEffort = Math.min(minEffort, currentMax);
            return;
        }

        visited[r][c] = true;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < heights.length && nc >= 0 && nc < heights[0].length && !visited[nr][nc]) {
                int effort = Math.abs(heights[r][c] - heights[nr][nc]);
                int newMax = Math.max(currentMax, effort);
                // A small pruning optimization: if current path effort is already worse, skip
                if (newMax < minEffort) { 
                    backtrack(nr, nc, newMax, heights, visited);
                }
            }
        }
        visited[r][c] = false;
    }
}
```
### Algorithm
*   Initialize a global variable `minEffort` to `Integer.MAX_VALUE`.
*   Create a `visited` grid of the same dimensions as `heights`, initialized to `false`.
*   Call a recursive function, let's say `dfs(0, 0, 0, visited, heights)` from the starting cell.
*   The `dfs(row, col, currentMaxEffort)` function works as follows:
    *   If the current path's effort `currentMaxEffort` is already greater than or equal to the global `minEffort`, we can prune this path and return (optional optimization).
    *   If the destination `(rows-1, cols-1)` is reached, update `minEffort = min(minEffort, currentMaxEffort)` and return.
    *   Mark the current cell `(row, col)` as visited: `visited[row][col] = true`.
    *   Iterate through all four neighbors (up, down, left, right).
    *   For each valid and unvisited neighbor:
        *   Calculate the effort to move to it: `effort = abs(heights[row][col] - heights[neighbor_row][neighbor_col])`.
        *   The new maximum effort for the path is `max(currentMaxEffort, effort)`.
        *   Make a recursive call for the neighbor with this new maximum effort.
    *   After exploring all neighbors, backtrack by un-marking the current cell: `visited[row][col] = false`.

## Binary Search on the Answer
The problem asks for the *minimum* maximum effort. This structure suggests that the answer lies within a defined range of possible effort values. We can observe that if a path exists with a maximum effort of `k`, a path also exists for any effort `k' > k`. This monotonicity allows us to use binary search on the answer (the effort value).
**Time:** O(R * C * log(K)), where `R` and `C` are the grid dimensions and `K` is the maximum possible height difference (`10^6`). The binary search performs `log(K)` iterations, and each involves a BFS/DFS traversal taking `O(R * C)` time. · **Space:** O(R * C) for the `visited` array and the queue (for BFS) or recursion stack (for DFS) used in the path checking function.
**Pros:** Efficient and guaranteed to find the optimal solution.; Conceptually clean, separating the problem of finding the value from checking a given value.
**Cons:** The time complexity depends on `log(K)`, where `K` is the maximum possible height difference. If `K` is extremely large, this might be slightly slower than other approaches.
### Explanation
We can binary search for the minimum required effort `k` in the range `[0, 10^6]`. For each candidate effort `mid` that we test, we need to answer the question: "Is it possible to travel from `(0, 0)` to `(rows-1, columns-1)` such that the absolute height difference between any two adjacent cells on the path is at most `mid`?"

This question can be answered efficiently using a graph traversal like Breadth-First Search (BFS) or Depth-First Search (DFS). We treat the grid as a graph where an edge between two cells exists only if the effort to cross it is less than or equal to `mid`. We then simply check for connectivity between the start and end cells.

*   If a path exists for a given `mid`, it means `mid` is a valid effort. We then try to find an even smaller effort by searching in the lower half of the range: `high = mid - 1`.
*   If no path exists, `mid` is too restrictive. We must allow for a larger effort, so we search in the upper half: `low = mid + 1`.

The smallest `mid` for which a path exists is our final answer.

```java
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int left = 0, right = 1000000;
        int result = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canReachDestination(heights, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    private boolean canReachDestination(int[][] heights, int maxEffort) {
        int rows = heights.length;
        int cols = heights[0].length;
        boolean[][] visited = new boolean[rows][cols];
        java.util.Queue<int[]> queue = new java.util.LinkedList<>();

        queue.offer(new int[]{0, 0});
        visited[0][0] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            if (r == rows - 1 && c == cols - 1) {
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                    if (Math.abs(heights[nr][nc] - heights[r][c]) <= maxEffort) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   Define a search range for the answer. The minimum possible effort is 0, and the maximum is `10^6 - 1`. Let's use `low = 0` and `high = 1000000`.
*   Perform a binary search on this range.
*   In each iteration of the binary search, pick a `mid` value.
*   Check if a path exists from `(0, 0)` to `(rows-1, columns-1)` where the effort of every step is at most `mid`. This check can be done with a graph traversal algorithm like BFS or DFS.
    *   **Path Existence Check (using BFS):**
        *   Initialize a queue and a `visited` array.
        *   Add the starting cell `(0, 0)` to the queue and mark it as visited.
        *   While the queue is not empty, dequeue a cell `(r, c)`.
        *   If `(r, c)` is the destination, a path exists, so return `true`.
        *   Explore its neighbors. For each neighbor `(nr, nc)`, if it's within bounds, not visited, and `abs(heights[r][c] - heights[nr][nc]) <= mid`, mark it as visited and enqueue it.
        *   If the queue becomes empty and the destination was not reached, no such path exists, so return `false`.
*   If the path existence check returns `true`, it means `mid` is a possible effort. We try for a better (smaller) solution, so we set `ans = mid` and `high = mid - 1`.
*   If the check returns `false`, `mid` is too small. We need to allow more effort, so we set `low = mid + 1`.
*   The loop terminates when `low > high`, and the final `ans` is the minimum effort required.

## Dijkstra's Algorithm on Grid
This problem can be framed as finding a shortest path in a graph where cells are nodes and the "cost" of a path is its maximum edge weight (effort). A modified version of Dijkstra's algorithm is perfectly suited for this. Instead of minimizing the sum of weights along a path, we minimize the maximum weight encountered so far.
**Time:** O(R * C * log(R * C)). The number of vertices is `N = R * C`. Each vertex is enqueued and dequeued at most once. Priority queue operations take `O(log N)` time. · **Space:** O(R * C) for the `efforts` array and the priority queue, which can store up to `R * C` elements in the worst case.
**Pros:** A standard and very efficient graph algorithm for this type of problem.; Often performs very well in practice and can be faster than binary search if the destination is found early.
**Cons:** Can be slightly more complex to implement correctly compared to the binary search approach.
### Explanation
We treat the grid as a graph where each cell is a vertex. The weight of an edge between two adjacent cells is the absolute difference of their heights. The problem is to find a path from `(0,0)` to `(rows-1, columns-1)` that minimizes the maximum edge weight along the path.

Dijkstra's algorithm finds the shortest paths from a source to all other nodes. We can adapt it for our purpose. We'll maintain an `efforts` array, where `efforts[r][c]` stores the minimum effort (minimum of maximums) to reach cell `(r,c)`. We use a priority queue to always explore the cell that is reachable with the minimum effort so far.

When we extract a cell `(r, c)` with effort `d` from the priority queue, `d` is guaranteed to be the minimum possible effort to reach that cell. We then relax its neighbors: for a neighbor `(nr, nc)`, the effort to reach it via `(r, c)` is the maximum of `d` and the effort of the edge between `(r, c)` and `(nr, nc)`. If this is better than the known effort for `(nr, nc)`, we update it and add the neighbor to the queue. The first time we extract the destination cell, we have found our answer.

```java
class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        int[][] efforts = new int[rows][cols];
        for (int[] row : efforts) {
            java.util.Arrays.fill(row, Integer.MAX_VALUE);
        }
        efforts[0][0] = 0;

        // Min-heap storing {effort, row, col}
        java.util.PriorityQueue<int[]> pq = new java.util.PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0, 0});

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            int r = curr[1];
            int c = curr[2];

            if (d > efforts[r][c]) {
                continue;
            }

            if (r == rows - 1 && c == cols - 1) {
                return d;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    int newEffort = Math.max(d, Math.abs(heights[r][c] - heights[nr][nc]));
                    if (newEffort < efforts[nr][nc]) {
                        efforts[nr][nc] = newEffort;
                        pq.offer(new int[]{newEffort, nr, nc});
                    }
                }
            }
        }
        return 0; // Should not be reached
    }
}
```
### Algorithm
*   Get grid dimensions `R` and `C`.
*   Create an `efforts` grid of size `R x C` to store the minimum effort to reach each cell, initialized to `Integer.MAX_VALUE`.
*   Set the effort for the starting cell: `efforts[0][0] = 0`.
*   Create a min-priority queue to store tuples of `(effort, row, col)`. The priority queue will always return the tuple with the smallest effort.
*   Add the starting cell information `{0, 0, 0}` to the priority queue.
*   While the priority queue is not empty:
    *   Extract the cell with the minimum effort from the queue: `(d, r, c)`.
    *   If `d > efforts[r][c]`, this is a stale entry from a path that has already been improved. Skip it.
    *   If `(r, c)` is the destination `(R-1, C-1)`, we have found the path with the minimum possible effort. Return `d`.
    *   For each of the four neighbors `(nr, nc)` of `(r, c)`:
        *   Calculate the effort to move from `(r, c)` to `(nr, nc)`: `edgeEffort = abs(heights[r][c] - heights[nr][nc])`.
        *   The effort of the path to the neighbor via `(r, c)` is `max(d, edgeEffort)`.
        *   If this new path effort is less than the currently known minimum effort to reach `(nr, nc)` (`efforts[nr][nc]`):
            *   Update `efforts[nr][nc]` with this better value.
            *   Add the new information `{efforts[nr][nc], nr, nc}` to the priority queue.

## Union-Find on Sorted Edges
This approach rephrases the problem as: what is the minimum effort `k` such that there exists a path from start to end using only edges with effort `<= k`? This is equivalent to finding the smallest `k` for which the start and end cells become connected in the graph. We can solve this elegantly using a Union-Find data structure, which is specifically designed for tracking connectivity in a graph as edges are added.
**Time:** O(E log E), where `E` is the number of edges. Since `E` is proportional to `R * C`, the complexity is `O(R * C * log(R * C))`. The dominant step is sorting the edges. The subsequent Union-Find operations are nearly constant time on average. · **Space:** O(R * C) to store the list of all edges and for the parent/rank arrays in the Union-Find data structure.
**Pros:** Very elegant and efficient.; Directly solves the connectivity problem which is at the heart of the question.; The Union-Find data structure with path compression and union by rank is extremely fast for its operations.
**Cons:** Requires creating and sorting all edges upfront, which might have a higher constant factor for time and space compared to Dijkstra's lazy exploration.
### Explanation
This method is inspired by Kruskal's algorithm for finding a Minimum Spanning Tree (MST). The key insight is that we are looking for a path, and the cost of that path is its single most 'expensive' edge. 

1.  **Edge List:** First, we generate a list of all possible 'edges' in our grid. An edge connects two adjacent cells, and its 'weight' is the effort required to traverse it (the absolute difference in heights).

2.  **Sort Edges:** We sort this list of edges by their weights in non-decreasing order.

3.  **Union-Find:** We then iterate through the sorted edges. We use a Union-Find data structure to keep track of the connected components of cells. Initially, every cell is in its own component.

For each edge, we 'union' the components of the two cells it connects. After each union, we check if the start cell `(0, 0)` and the end cell `(rows-1, columns-1)` now belong to the same component. The first time they do, the weight of the edge we just added is the answer. Because we process edges from smallest to largest weight, this edge is the 'bottleneck' of the 'easiest' path, and thus its weight is the minimum possible effort.

```java
class Solution {
    class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]); // Path compression
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                // Union by rank
                if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
            }
        }
    }

    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        if (rows == 1 && cols == 1) return 0;

        java.util.List<int[]> edges = new java.util.ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                int currentCellId = r * cols + c;
                if (c + 1 < cols) {
                    int effort = Math.abs(heights[r][c] - heights[r][c + 1]);
                    edges.add(new int[]{effort, currentCellId, currentCellId + 1});
                }
                if (r + 1 < rows) {
                    int effort = Math.abs(heights[r][c] - heights[r + 1][c]);
                    edges.add(new int[]{effort, currentCellId, currentCellId + cols});
                }
            }
        }

        java.util.Collections.sort(edges, (a, b) -> a[0] - b[0]);

        UnionFind uf = new UnionFind(rows * cols);
        int startNode = 0;
        int endNode = rows * cols - 1;

        for (int[] edge : edges) {
            int effort = edge[0];
            int u = edge[1];
            int v = edge[2];
            uf.union(u, v);
            if (uf.find(startNode) == uf.find(endNode)) {
                return effort;
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
*   Get grid dimensions `R` and `C`. If `R*C == 1`, return 0.
*   Create a list of all edges in the grid. An edge connects two adjacent cells. For each edge, store its effort (absolute height difference) and the indices of the two cells it connects. A cell `(r, c)` can be mapped to a single index `r * C + c`.
*   Sort the list of edges in ascending order of their effort.
*   Initialize a Union-Find (Disjoint Set Union) data structure with `R * C` elements, one for each cell.
*   Iterate through the sorted edges `(effort, u, v)`:
    *   Perform a `union` operation on the two cells `u` and `v`.
    *   After the union, check if the start cell (index 0) and the end cell (index `R*C - 1`) are in the same connected component using the `find` operation (`find(0) == find(R*C - 1)`).
    *   If they are connected, it means we have just added the crucial edge that forms a path between start and end. Since we are processing edges in increasing order of effort, this edge's effort is the minimum possible maximum effort required. Return this effort.
*   The loop will always find a path and return, so no return statement is needed after the loop.

# Solutions
### Java

```java
class UnionFind { private final int [] p ; private final int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } public boolean connected ( int a , int b ) { return find ( a ) == find ( b ); } } class Solution { public int minimumEffortPath ( int [][] heights ) { int m = heights . length , n = heights [ 0 ]. length ; UnionFind uf = new UnionFind ( m * n ); List < int []> edges = new ArrayList <>(); int [] dirs = { 1 , 0 , 1 }; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { for ( int k = 0 ; k < 2 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n ) { int d = Math . abs ( heights [ i ][ j ] - heights [ x ][ y ]); edges . add ( new int [] { d , i * n + j , x * n + y }); } } } } Collections . sort ( edges , ( a , b ) -> a [ 0 ] - b [ 0 ]); for ( int [] e : edges ) { uf . union ( e [ 1 ], e [ 2 ]); if ( uf . connected ( 0 , m * n - 1 )) { return e [ 0 ]; } } return 0 ; } }
```

### CPP

```cpp
class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } bool connected ( int a , int b ) { return find ( a ) == find ( b ); } private: vector < int > p , size ; }; class Solution { public: int minimumEffortPath ( vector < vector < int >>& heights ) { int m = heights . size (), n = heights [ 0 ]. size (); vector < array < int , 3 >> edges ; int dirs [ 3 ] = { 0 , 1 , 0 }; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { for ( int k = 0 ; k < 2 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n ) { edges . push_back ({ abs ( heights [ i ][ j ] - heights [ x ][ y ]), i * n + j , x * n + y }); } } } } sort ( edges . begin (), edges . end ()); UnionFind uf ( m * n ); for ( auto & [ h , a , b ] : edges ) { uf . unite ( a , b ); if ( uf . connected ( 0 , m * n - 1 )) { return h ; } } return 0 ; } };
```

### Python

```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 ) e = [] dirs = ( 0 , 1 , 0 ) for i in range ( m ): for j in range ( n ): for a , b in pairwise ( dirs ): x , y = i + a , j + b if 0 <= x < m and 0 <= y < n : e . append ( ( abs ( heights [ i ][ j ] - heights [ x ][ y ]), i * n + j , x * n + y ) ) e . sort () for h , a , b in e : uf . union ( a , b ) if uf . connected ( 0 , m * n - 1 ): return h return 0
```