1631. Path With Minimum Effort LeetCode Solution

In this guide, you will get 1631. Path With Minimum Effort LeetCode Solution with the best time and space complexity. The solution to Path With Minimum Effort problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Path With Minimum Effort solution in C++
  4. Path With Minimum Effort solution in Java
  5. Path With Minimum Effort solution in Python
  6. Additional Resources
1631. Path With Minimum Effort LeetCode Solution image

Problem Statement of 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.

Example 1:

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:

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].

See also  720. Longest Word in Dictionary LeetCode Solution

Example 3:

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

Complexity Analysis

  • Time Complexity: O(mn\log mn)
  • Space Complexity: O(mn)

1631. Path With Minimum Effort LeetCode Solution in C++

struct T {
  int i;
  int j;
  int d;  // the maximum difference of (i, j) and its neighbors
};

class Solution {
 public:
  int minimumEffortPath(vector<vector<int>>& heights) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = heights.size();
    const int n = heights[0].size();
    auto compare = [](const T& a, const T& b) { return a.d > b.d; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    // diff[i][j] := the maximum absolute difference to reach (i, j)
    vector<vector<int>> diff(m, vector<int>(n, INT_MAX));
    vector<vector<bool>> seen(m, vector<bool>(n));

    minHeap.emplace(0, 0, 0);
    diff[0][0] = 0;

    while (!minHeap.empty()) {
      const auto [i, j, d] = minHeap.top();
      minHeap.pop();
      if (i == m - 1 && j == n - 1)
        return d;
      seen[i][j] = true;
      for (const auto& [dx, dy] : dirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        const int newDiff = abs(heights[i][j] - heights[x][y]);
        const int maxDiff = max(diff[i][j], newDiff);
        if (diff[x][y] > maxDiff) {
          diff[x][y] = maxDiff;
          minHeap.emplace(x, y, maxDiff);
        }
      }
    }

    throw;
  }
};
/* code provided by PROGIEZ */

1631. Path With Minimum Effort LeetCode Solution in Java

class Solution {
  public int minimumEffortPath(int[][] heights) {
    // d := the maximum difference of (i, j) and its neighbors
    record T(int i, int j, int d) {}
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = heights.length;
    final int n = heights[0].length;
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.d, b.d));
    // dist[i][j] := the maximum absolute difference to reach (i, j)
    int[][] diff = new int[m][n];
    Arrays.stream(diff).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
    boolean[][] seen = new boolean[m][n];

    minHeap.offer(new T(0, 0, 0));
    diff[0][0] = 0;

    while (!minHeap.isEmpty()) {
      final int i = minHeap.peek().i;
      final int j = minHeap.peek().j;
      final int d = minHeap.poll().d;
      if (i == m - 1 && j == n - 1)
        return d;
      seen[i][j] = true;
      for (int[] dir : dirs) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        final int newDiff = Math.abs(heights[i][j] - heights[x][y]);
        final int maxDiff = Math.max(diff[i][j], newDiff);
        if (diff[x][y] > maxDiff) {
          diff[x][y] = maxDiff;
          minHeap.offer(new T(x, y, maxDiff));
        }
      }
    }

    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

1631. Path With Minimum Effort LeetCode Solution in Python

class Solution:
  def minimumEffortPath(self, heights: list[list[int]]) -> int:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(heights)
    n = len(heights[0])
    # diff[i][j] := the maximum absolute difference to reach (i, j)
    diff = [[math.inf] * n for _ in range(m)]
    seen = set()

    minHeap = [(0, 0, 0)]  # (d, i, j)
    diff[0][0] = 0

    while minHeap:
      d, i, j = heapq.heappop(minHeap)
      if i == m - 1 and j == n - 1:
        return d
      seen.add((i, j))
      for dx, dy in dirs:
        x = i + dx
        y = j + dy
        if x < 0 or x == m or y < 0 or y == n:
          continue
        if (x, y) in seen:
          continue
        newDiff = abs(heights[i][j] - heights[x][y])
        maxDiff = max(diff[i][j], newDiff)
        if diff[x][y] > maxDiff:
          diff[x][y] = maxDiff
          heapq.heappush(minHeap, (diff[x][y], x, y))
# code by PROGIEZ

Additional Resources

See also  3312. Sorted GCD Pair Queries LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.