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