Path With Minimum Effort

Photo by Alexander Milo on Unsplash

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 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.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

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 of [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].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.

Constraints:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 106

Naive BFS doesn’t work because you only visit the node once, and therefore you only consider one of many paths. Secondly, a naive BFS will give you the path with minimal nodes visited. In this problem, though, we can clearly see that optimal path != path with minimal length. (Look at Example 3)

When a question asks about something related to shortest path, always consider how BFS can help because that’s what BFS does. However after a few minutes of thinking, I quickly realize that a simple naïve BFS would not work.

Before going further, here is the pseudocode of naïve BFS:

queue = []
visited = set()
while queue:
me = queue.popleft()
for every neighbor of me:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

Consider the first test case. If you loop your neighbors this way: [[0,1], [1,0], [-1,0], [0, -1]] (you push your right neighbor first to the queue), then you would find the below path before other possible paths (notice that the first move of the path is go to the right).

That’s great. Although it is not the optimal path, at least you found a path to the destination and you know the effort here is 3. Now, you can look for other better paths right? Unfortunately, in naïve BFS, you only visit a node exactly once. This means that unless you reset the visited set, you can't find other way to the destination. Remember, by now, the destination itself is already marked as visited right? So you will not visit it again.

Interestingly, if you loop your neighbors in the following order [[1,0], [0,1], [-1,0], [0, -1]] (you push your below neighbor first to the queue), then you will find optimal path.

So the order of iterating the neighbor matters. But wait a minute! that’s no longer the scope of BFS!

In BFS, the order of looping the neighbors should never affect the answer.

BFS should find the shortest path regardless of how you iterate your neighbors. It is true our BFS has found the path with minimal length (i.e. both of the above paths visit 4 nodes). However, our BFS cannot differentiate the effort of the two paths above. And so, naive BFS would not work for this problem. We need to modify our stupid BFS.

Fortunately, we’re close. At this point, I know that the logic for visiting a node is messed up; I cannot just visit a node once and call it a day, I need to visit it more than once. Where in the code that is responsible of whether or not I should visit a node?

That’s right:

if neighbor not in visited:
# visit neighbor

So we need to change the logic and how we store the BFS’s visited state. How? Well, ask this question.

When would I ever bother to visit a node for the second time?

The answer is

when we found a better path (i.e. lower cost)

And this answer should be sufficient to give me a hint that instead of a visited set, we need to store a cost in dictionary. Hence, the modified BFS should look like the following:

queue = []
cost = {} # dictionary, instead of a set
while queue:
me = queue.popleft()
for every neighbor of me:
new_cost = compute_cost()
if new_cost < cost[neighbor]: # better path!
cost[neighbor] = new_cost
queue.append(neighbor)

And this modified BFS is actually what Dijkstra does :).

Comment the time complexity. ;-)

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Please, No More “Stop Using” Articles!

Where am I at concerning web development? The catharsis of a lifelong search of my passion

The Best Sources to learn Java Programming

Why we moved Amaterasu to Kotlin, and what the future holds

Android and iOS App testing with Appium and WireMock — Appium & WireMock

Definition of Done — or why it’s not enough to make a list

38 Material Design UI For Website

Web Development with Rust — 03/x: Create a REST API

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Koko Eating Bananas

How I Prepared for Amazon Interview— Software Engineer

How to Prepare for Conducting a Coding/TInterview

How to answer time and space complexity questions in coding interviews?