1631. Path With Minimum Effort

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.

• union find solution
• Time : O(nmlog(nm))
• Space : O(nm)

class Solution {
    int n, m;
    vector<array<int,3>> dist;
    int find(vector<int>& g, int n) {
        return g[n] == n ? n : g[n] = find(g, g[n]);
    }

    void uni(vector<int>& g, int a, int b) {
        int pa = find(g,a), pb = find(g,b);
        g[pa] = g[pb] = min(pa,pb);
    }
    void initGraph(vector<int>& g) {
        for(int i = 0; i < n*m; i++)
            g[i] = i;
    }
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        n = heights.size(), m = heights[0].size();
        if(n == 1 and m == 1) return 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(j != m - 1) {
                    int diff = abs(heights[i][j] - heights[i][j+1]);
                    dist.push_back({diff, i*m+j, i*m+ j+1});
                }
                if(i != n - 1) {
                    int diff = abs(heights[i][j] - heights[i+1][j]);
                    dist.push_back({diff,i*m+j, (i+1)*m + j});
                }
            }
        }
        vector<int> graph(n*m, 0);
        initGraph(graph);
        sort(dist.begin(), dist.end());
        for(auto [d, from, to]: dist) {
            uni(graph, from, to);
            if(find(graph, 0) == find(graph, n*m-1))
                return d;
        }
        return -1;
    }
};

• dijkstra solution
• Time : O(nmlog(nm))
• Space : O(nm)

class Solution {
    int n, m;
public:
    int minimumEffortPath(vector<vector<int>>& heights) { //o(n^2log(n^2))
        n = heights.size(), m = heights[0].size();
        int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
        vector<vector<int>> dist(n,vector<int>(m,INT_MAX));
        priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> pq;
        dist[0][0] = 0;
        pq.push({0,0,0});

        while(!pq.empty()) {
            auto [effort, y, x] = pq.top(); pq.pop();
            if(y == n - 1 and x == m - 1) return effort;

            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                    int diff = max(effort, abs(heights[y][x] - heights[ny][nx]));
                    if(dist[ny][nx] > diff) {
                        dist[ny][nx] = diff;
                        pq.push({diff, ny, nx});
                    }
                }
            }
        }

        return -1;
    }
};