[LeetCode][1631. Path With Minimum Effort] 3 Approaches: BFS(Dijkstra), Binary Search, Union Find

By Long Luo

This article is the solution 3 Approaches: BFS(Dijkstra), Binary Search, Union Find of Problem 1631. Path With Minimum Effort.

Here shows 3 Approaches to slove this problem: BFS(Dijkstra), Binary Search, Union Find.

BFS(Dijkstra)

public int minimumEffortPath(int[][] heights) {
    if (heights == null || heights.length == 0 || heights[0].length == 0) {
        return 0;
    }

    int rows = heights.length;
    int cols = heights[0].length;

    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    PriorityQueue<int[]> pq = new PriorityQueue<>((edge1, edge2) -> edge1[2] - edge2[2]);

    pq.offer(new int[]{0, 0, 0});

    int[] dist = new int[rows * cols];
    Arrays.fill(dist, Integer.MAX_VALUE);

    dist[0] = 0;

    boolean[][] vis = new boolean[rows][cols];

    while (!pq.isEmpty()) {
        int[] edge = pq.poll();

        int x = edge[0];
        int y = edge[1];
        int d = edge[2];

        if (vis[x][y]) {
            continue;
        }

        if (x == rows - 1 && y == cols - 1) {
            break;
        }

        vis[x][y] = true;
        for (int[] dir : dirs) {
            int nextX = x + dir[0];
            int nextY = y + dir[1];

            if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols
                    && Math.max(d, Math.abs(heights[nextX][nextY] - heights[x][y])) < dist[nextX * cols + nextY]) {
                dist[nextX * cols + nextY] = Math.max(d, Math.abs(heights[nextX][nextY] - heights[x][y]));
                pq.offer(new int[]{nextX, nextY, dist[nextX * cols + nextY]});
            }
        }
    }

    return dist[rows * cols - 1];
}

Analysis

• Time Complexity: $O(mnlog(mn))$.
• Space Complexity: $O(mn)$.

Binary Search

public int minimumEffortPath(int[][] heights) {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int rows = heights.length;
    int cols = heights[0].length;

    int left = 0;
    int right = 1_000_000 - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        boolean[][] visited = new boolean[rows][cols];

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});

        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();
            for (int[] dir : dirs) {
                int nextX = curPos[0] + dir[0];
                int nextY = curPos[1] + dir[1];

                if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && !visited[nextX][nextY]
                        && Math.abs(heights[nextX][nextY] - heights[curPos[0]][curPos[1]]) <= mid) {
                    visited[nextX][nextY] = true;
                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }

        if (visited[rows - 1][cols - 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

Analysis

• Time Complexity: $O(mnlogC)$.
• Space Complexity: $O(mn)$.

Union Find

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

    List<int[]> edges = new ArrayList<>();

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int index = i * cols + j;
            if (i > 0) {
                edges.add(new int[]{index - cols, index, Math.abs(heights[i][j] - heights[i - 1][j])});
            }

            if (j > 0) {
                edges.add(new int[]{index - 1, index, Math.abs(heights[i][j] - heights[i][j - 1])});
            }
        }
    }

    Collections.sort(edges, (edge1, edge2) -> edge1[2] - edge2[2]);

    UnionFind uf = new UnionFind(rows * cols);
    int ans = 0;
    for (int[] edge : edges) {
        int x = edge[0];
        int y = edge[1];
        int d = edge[2];
        uf.union(x, y);
        if (uf.isConnected(0, rows * cols - 1)) {
            ans = d;
            break;
        }
    }

    return ans;
}

class UnionFind {
    int[] parent;
    int[] size;
    int count;

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

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (size[rootX] < size[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }

        count--;
    }

    public int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }

        return x;
    }

    public boolean isConnected(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        return rootX == rootY;
    }
}

Analysis

• Time Complexity: $O(mnlog(mn))$.
• Space Complexity: $O(mn)$.

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗