Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

156. Path With Minimum Effort

MediumDay 46 of 60Graphs

You are hiking on a grid heights of size rows x cols and start at the top-left cell, wanting to reach the bottom-right cell. You can move up, down, left or right. The effort of a route is the largest absolute height difference between two consecutive cells on it. Return the minimum effort needed to reach the destination.

Example 1
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
The route 1, 3, 5, 3, 5 never climbs or drops more than 2 in one move.
Example 2
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
The route 1, 2, 3, 4, 5 has every step equal to 1.
Constraints
  • 1 <= rows, cols <= 100
  • 1 <= heights[i][j] <= 10^6
Hints
Frequently asked at: Google, Amazon
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min