Last Updated: 2 Apr, 2021

Path With Minimum Effort

Hard

Asked in companies

Solve now

Problem statement

You are given heights, a 2D array of size 'rows' x 'columns', where heights[row][col] represents the height of a cell (which would contain a row and column).

You are a Ninja training for an upcoming battle. 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 time. A route's time is the maximum absolute difference in heights between two consecutive cells of the route.

You must return the minimum time required to travel from the top-left cell to the bottom-right cell.

For Example:

Input: 'heights' = [[1, 8, 8],[3, 8, 9],[5,3,5]]
Output: 2

Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.

Input Format:

The first line contains two space-separated integers, 'rows' and 'columns'.

Next 'rows' lines contain 'columns' space-separated integers.

Output Format:

The only line contains the minimum time you require to travel from the top-left cell to the bottom-right cell.

Solve now

Approaches

01 Approach

The main idea here is to implement a dfs function with parameter TIME_LIMIT here: it is the maximum time you (as a ninja) can deal with. Then the idea is to use binary search to find the smallest TIME_LIMIT for which you can reach the ending point.

The algorithm will be-

Initialise the lengths of rows, columns and a neighbours 2-D list (array) comprising the valid set of moves which can be performed on the heights list (array).
Now we define a function named DFS(TIME_LIMIT, x, y), where TIME_LIMIT is the maximum time we can take to reach our destination and x, y are current coordinates for each iteration. To perform the depth-first search traversal, we need to visit all neighbours, and make sure that we follow the below constraints:
1. Do not go outside our grid
2. The cell is not visited yet
3. The effort to go from the old cell to a new one is less or equal to TIME_LIMIT.
Now we use a binary search to ensure that:
1. We can be sure that if TIME_LIMIT = -1, we never reach the end, and if TIME_LIMIT is maximum overall heights, then we will reach the end.
2. Choose the middle point and keep marking visited sets of cells, perform a depth first search and choose a left or right part to search for.
We finally return the minimum time taken to traverse from source to destination.

Solve now

02 Approach

The main idea here is to think about how the problem can be modelled as an undirected graph and solved using Dijkstra's algorithm using a breadth-first search fashion of cell (node) traversal.

The algorithm will be-

Initialise the lengths of rows, columns and a costs 2-D list (array) comprising of the heights of the cells initialised with a value of infinity and also initialise a neighbours 2-D list (array) comprising of the valid set of moves which can be performed on the heights list (array).
Initialise a priority_queue which would comprise the time required to get to a cell (i,j) with the end cell (destination) being the last row and last column.
Now traverse the items present in the queue until it becomes empty. For each cell keep the minimum time we need to have to reach this node.
For each iteration, we will extract the cell with minimum time, look at its neighbours and put them to the heap with each element of the form (time, i, k).
In every iteration keep popping the vertex with the minimum time. For each valid neighbour, its time if arrived from the popped vertex would be the max(parent time, time between neighbour vertex and parent).
If this time is less than the current best time in the neighbour, relax its value and add it to the heap.
End the loop when the bottom-right cell is reached and finally return the value of the minimum time that we have obtained.

Solve now