DevExCode

LeetCode 1631: Path With Minimum Effort Solution

Master LeetCode problem 1631 (Path With Minimum Effort), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the minimum effort required to travel from the top-left cell to the bottom-right cell. We will create a priority queue to store the cells with their corresponding efforts, and at each step, we will explore the neighboring cells and update the effort required to reach each cell. We will keep track of the minimum effort to reach the bottom-right cell.

The algorithm steps are as follows:

  1. Initialize a priority queue and add the top-left cell with effort 0.
  2. While the priority queue is not empty:
    • Pop the cell with the minimum effort from the priority queue.
    • If this cell is the bottom-right cell, return its effort as the minimum effort.
    • Otherwise, explore its neighbors and update the effort required to reach each neighbor.
  3. Return the minimum effort found.

The time complexity of this algorithm is O(rows * columns * log(rows * columns)) where rows and columns are the dimensions of the input grid. The space complexity is O(rows * columns) for storing the efforts in the priority queue.

Solution Code

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        
        int[][] efforts = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(efforts[i], Integer.MAX_VALUE);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        pq.offer(new int[]{0, 0, 0});
        
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int row = curr[0];
            int col = curr[1];
            int effort = curr[2];
            
            if (row == rows - 1 && col == cols - 1) {
                return effort;
            }
            
            for (int[] dir : dirs) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                    int newEffort = Math.max(effort, Math.abs(heights[newRow][newCol] - heights[row][col]));
                    
                    if (newEffort < efforts[newRow][newCol]) {
                        efforts[newRow][newCol] = newEffort;
                        pq.offer(new int[]{newRow, newCol, newEffort});
                    }
                }
            }
        }
        
        return -1; // Should not reach here
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1631 (Path With Minimum Effort)?

This page provides optimized solutions for LeetCode problem 1631 (Path With Minimum Effort) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1631 (Path With Minimum Effort)?

The time complexity for LeetCode 1631 (Path With Minimum Effort) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1631 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1631 in Java, C++, or Python.

Back to LeetCode Solutions