Leetcode 1631: Path With Minimum Effort
You are a hiker navigating a terrain represented by a 2D grid of heights. Your goal is to find the path from the top-left corner to the bottom-right corner that minimizes the maximum height difference between any two consecutive cells.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D array `heights` of size `rows x columns`, where `heights[i][j]` represents the height at position `(i, j).`
Example: heights = [[2, 3, 1], [5, 6, 4], [7, 8, 3]]
Constraints:
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6
Output: Return an integer representing the minimum possible effort to travel from the top-left to the bottom-right cell.
Example: Output: 2
Constraints:
• The output is a single integer.
Goal: The goal is to compute the minimum possible effort to travel from the top-left to the bottom-right cell.
Steps:
• Use a priority queue to explore the grid.
• At each cell, track the maximum difference in heights from the previous cell.
• Keep track of the smallest maximum difference encountered and return that as the result.
Goal: The constraints ensure that the grid size is manageable and that the height values are within a reasonable range for computation.
Steps:
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6
Assumptions:
• You can move in four directions (up, down, left, right).
• The top-left cell is always your starting point and the bottom-right cell is always your destination.
• Input: heights = [[2, 3, 1], [5, 6, 4], [7, 8, 3]]
• Explanation: The optimal path involves moving from 2 -> 5 -> 6 -> 4 -> 3, with the largest height difference between two consecutive cells being 2.
Approach: The approach leverages a priority queue to explore the grid cells, calculating the minimum possible maximum height difference encountered along the path.
Observations:
• We need to explore the grid and calculate the maximum height difference between consecutive cells along the path.
• A priority queue can help efficiently explore the grid and maintain the smallest possible maximum difference.
Steps:
• Initialize a priority queue with the starting cell.
• Explore each neighboring cell, updating the maximum difference encountered so far.
• Return the smallest maximum difference once the bottom-right cell is reached.
Empty Inputs:
• No empty grids are expected in the input.
Large Inputs:
• The solution must efficiently handle grids with up to 100 rows and columns.
Special Values:
• The solution should handle cases where all heights are the same, resulting in zero effort.
Constraints:
• The height values are constrained between 1 and 10^6, ensuring the differences are manageable.
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& h) {
int dir[] = {0, 1, 0, -1, 0};
int m = h.size(), n = h[0].size();
vector<vector<int>> sz(m, vector<int>(n, INT_MAX));
priority_queue<array<int, 3>, vector<array<int, 3>>, cmp> pq;
pq.push({0, 0, 0});
while(!pq.empty()) {
array<int, 3> r = pq.top();
pq.pop();
int i = r[0], j = r[1], d = r[2];
//cout << i << ' ' << j << ' ' << d << endl;
if(d > sz[i][j]) continue;
if((i == (m - 1)) && (j == (n - 1))) return d;
for(int k = 0; k < 4; k++) {
int ni = i + dir[k], nj = j + dir[k + 1];
if(min(ni, nj) < 0 || ni >= m || nj >= n) continue;
int nxt = sz[ni][nj];
int nd = max(abs(h[i][j] - h[ni][nj]), d);
if (nxt > nd) {
sz[ni][nj] = nd;
pq.push({ni, nj, nd});
}
}
}
return 0;
}
1 : Class Definition
class Solution {
Define the 'Solution' class that encapsulates the method for solving the problem.
2 : Access Modifier
public:
Declare the public section of the class where the method 'minimumEffortPath' will be defined.
3 : Method Definition
int minimumEffortPath(vector<vector<int>>& h) {
Define the 'minimumEffortPath' method, which takes a 2D vector 'h' representing the grid of elevations as input.
4 : Variable Initialization
int dir[] = {0, 1, 0, -1, 0};
Initialize the 'dir' array, which contains the four possible movement directions (right, down, left, and up) for traversal.
5 : Variable Initialization
int m = h.size(), n = h[0].size();
Determine the dimensions of the grid, 'm' for rows and 'n' for columns.
6 : Matrix Initialization
vector<vector<int>> sz(m, vector<int>(n, INT_MAX));
Create a 2D vector 'sz' initialized with 'INT_MAX' to store the minimum effort required to reach each cell.
7 : Priority Queue Initialization
priority_queue<array<int, 3>, vector<array<int, 3>>, cmp> pq;
Initialize a priority queue 'pq' that will store the current state of traversal (row, column, and effort). The queue is ordered by the effort required to reach each cell.
8 : Queue Push
pq.push({0, 0, 0});
Push the initial position (0,0) with an effort of 0 into the priority queue.
9 : Loop Constructs
while(!pq.empty()) {
Start a while loop to process each element in the priority queue until it is empty.
10 : Queue Operations
array<int, 3> r = pq.top();
Get the top element from the priority queue, which contains the current row, column, and effort.
11 : Queue Operations
pq.pop();
Remove the top element from the priority queue.
12 : Variable Assignment
int i = r[0], j = r[1], d = r[2];
Assign the row index 'i', column index 'j', and the current effort 'd' from the top element.
13 : Conditional Check
if(d > sz[i][j]) continue;
Check if the current effort 'd' is greater than the already stored effort for cell (i, j). If so, skip the current iteration.
14 : Termination Condition
if((i == (m - 1)) && (j == (n - 1))) return d;
If the current position is the bottom-right corner of the grid, return the current effort 'd' as the result.
15 : Loop Constructs
for(int k = 0; k < 4; k++) {
Start a for loop to explore the four possible directions (right, down, left, and up) from the current cell.
16 : Coordinate Update
int ni = i + dir[k], nj = j + dir[k + 1];
Calculate the new coordinates (ni, nj) based on the current direction.
17 : Boundary Check
if(min(ni, nj) < 0 || ni >= m || nj >= n) continue;
Check if the new coordinates (ni, nj) are out of bounds. If so, skip the current iteration.
18 : Effort Calculation
int nxt = sz[ni][nj];
Get the current minimum effort stored for the neighboring cell (ni, nj).
19 : Effort Calculation
int nd = max(abs(h[i][j] - h[ni][nj]), d);
Calculate the new effort 'nd' required to move from the current cell to the neighboring cell, which is the maximum of the absolute elevation difference and the current effort.
20 : Conditional Check
if (nxt > nd) {
If the new calculated effort 'nd' is smaller than the previously recorded effort for the neighboring cell, proceed to update it.
21 : State Update
sz[ni][nj] = nd;
Update the minimum effort for the neighboring cell to the newly calculated effort.
22 : Queue Push
pq.push({ni, nj, nd});
Push the updated state (ni, nj, nd) into the priority queue for further processing.
23 : Return Statement
return 0;
Return 0 as a default value if no valid path is found (although this case should not occur with a valid input).
Best Case: O(rows * columns * log(rows * columns))
Average Case: O(rows * columns * log(rows * columns))
Worst Case: O(rows * columns * log(rows * columns))
Description: The time complexity is dominated by the priority queue operations, which take log(rows * columns) time.
Best Case: O(rows * columns)
Worst Case: O(rows * columns)
Description: The space complexity is determined by the size of the priority queue and the auxiliary storage for visited cells.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus