Path With Minimum Effort
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Find the path from top-left to bottom-right in a 2D grid with heights, minimizing the maximum absolute difference between consecutive cell heights (Minimum Effort Path Problem)., Arrays, Two-dimensional Array Traversal, Graph, Weighted Graph, Dijkstra's Algorithm, Priority Queue, Time Complexity, Space Complexity, Brute Force, complexity analysis, priority queue, brute force, graph algorithms, graph traversal, dijkstra's algorithm, grid traversal, pathfinding, Shortest Path (Dijkstra's Algorithm).
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 the 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. Example 1: Input: Output: 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: Output: Explanation: The route of [1,1,1,1,1,1,1,1,1,1,1,1,1,1] has a maximum absolute difference of 0 in consecutive cells. This is better than the route of [1,1,1,1,1,1,2,1], where the maximum absolute difference is 1.