Problem Statement
A hiker is preparing for an upcoming hike. Given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of the cell (row, col). The hiker is situated in the top-left cell, (0, 0), and hopes to travel to the bottom-right cell, (rows-1, columns-1) (i.e.,0-indexed). He can move up, down, left, or right. He wishes 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.
Examples
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 [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].Different Approaches
1️⃣ Modified Dijkstra Algorithm
Intuition:
The problem resembles a pathfinding problem in a weighted graph, where we need to find a path with minimal maximum effort. We already know, traditional shortest path algorithms like Dijkstra's Algorithm are used to find the path with the minimum total cost. This gives an idea of using Dijkstra's algorithm to get to the solution. But there will be definitely some modifications needed.
Adapting Dijkstra's algorithm:
By slightly modifying the algorithm, it can be adapted to minimize the maximum effort:
- Instead of accumulating total distances, the maximum effort encountered so far can be tracked.
- And the priority queue (min-heap) can be used to store the pair {difference, {row of cell, column of cell}} which will help to always expand the least difference (effort) path first.
Comparing Edge Relaxation Steps in Dijkstra's Algorithms:
- Normal Dijkstra: Updates the distance if the new distance is smaller.
new_distance = current_distance + edge_weight - Modified Dijkstra: Updates the effort if the new effort (max of current effort and edge effort) is smaller.
new_effort = max(current_effort, edge_effort)
Approach:
- Define arrays to represent possible movement directions: up, down, left, and right. Create a matrix to track the minimum effort needed to reach each cell, initialized to a very large value.
- Use a priority queue to explore cells starting from the top-left corner with an initial effort of 0. Extract the cell with the lowest effort from the priority queue. If this cell is the bottom-right corner, return the current effort as the result.
- For each neighboring cell, calculate the effort required to move there, considering the maximum height difference encountered so far. Update the tracking matrix if this path offers a smaller maximum effort to reach the neighbor.
- Push the neighboring cell with the updated effort into the priority queue. Continue this process until the queue is empty or the destination is reached.
- If the priority queue is exhausted without reaching the destination, return a special value indicating failure (though this will never occur).
Code:
#include <bits/stdc++.h>
using namespace std;
/* Define P as a shorthand for
the pair<int, pair<int,int>> type */
#define P pair <int, pair<int,int>>
class Solution {
private:
// Delta row and column array
vector<int> delRow = {-1, 0, 1, 0};
vector<int> delCol = {0, -1, 0, 1};
// Function to check if a cell is valid
bool isValid(int &row, int &col,
int &n, int &m) {
// Return false if the cell is invalid
if(row < 0 || row >= n) return false;
if(col < 0 || col >= m) return false;
// Return true if the cell is valid
return true;
}
public:
/* Function to determine minimum efforts
to go from top-left to bottom-right */
int MinimumEffort(vector<vector<int>>& heights) {
// Get the dimensions of grid
int n = heights.size();
int m = heights[0].size();
// To store maximum difference
vector<vector<int>> maxDiff(n, vector<int>(m, 1e9));
/* Min-Heap storing the pair:
{diff, {row of cell, column of cell}} */
priority_queue <P, vector<P>, greater<P>> pq;
// Mark the initial position as 0
maxDiff[0][0] = 0;
// Push the starting cell to min-heap
pq.push({0, {0, 0}});
// Until the min-heap is not empty
while(!pq.empty()) {
/* Get the cell with minimum
difference (effort) */
auto p = pq.top();
// Get the difference
int diff = p.first;
int row = p.second.first; // Row
int col = p.second.second; // Column
pq.pop();
/* If the destination cell is reached,
return the difference */
if(row == n-1 && col == m-1)
return diff;
// Traverse it's neighbors
for(int i=0; i<4; i++) {
/* Get the coordinates
of neighboring cell */
int newRow = row + delRow[i];
int newCol = col + delCol[i];
// Check if the cell is valid
if(isValid(newRow, newCol, n, m)) {
/* Get the current difference
in heights of cells */
int currDiff =
abs(heights[newRow][newCol] - heights[row][col]);
/* Check if the current difference is
less than earlier known difference */
if(max(currDiff, diff) < maxDiff[newRow][newCol]) {
// Store the current difference
maxDiff[newRow][newCol] = max(currDiff, diff);
// Add the new pair found in the min-heap
pq.push({max(currDiff, diff), {newRow, newCol}});
}
}
}
}
// Return -1
return -1;
}
};
int main() {
vector<vector<int>> heights = {
{1,2,2},
{3,8,2},
{5,3,5}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to determine minimum efforts
to go from top-left to bottom-right */
int ans = sol.MinimumEffort(heights);
// Output
cout << "The minimum efforts required to go from cell (0,0) to cell (row-1, col-1) is: " << ans;
return 0;
}Complexity Analysis:
- Time Complexity: O(N*M*log(N*M))
- The algorithm processes each cell and explores its neighbors using a priority queue taking O(4*N*M) time.
- The priority queue operations (insertion and extraction) are logarithmic in nature making overall complexity as O(4*N*M*log(N*M)).
- Space Complexity: O(N*M)
- Matrix to store maximum differences for each cell takes O(N*M) space.
- Priority queue will store N*M elements in worst case contributing to O(N*M) space.