# Path With Minimum Effort

Posted: 2 Apr, 2021

Difficulty: Hard

#### You are a Ninja training for an upcoming battle. 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 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. Return the minimum time required to travel from the top-left cell to the bottom-right cell.

##### For Example

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

##### Input Format:

```
The first line determines the number of test cases that would be given in the problem.
The first line of each test case contains two space-separated integers where the first value is the number of rows ‘rows’ while the second integer is the number of columns ‘columns’ given for the 2-D list (array) heights
Now the 2-D list (array) input is taken according to the rows and columns entered before. I.e. The number of lines of input would be equal to the number of rows while in each line there would be as many space-separated integers as the number of columns for each row.
For example for a given row = 3 and columns = 3 we would have 3 lines of input with each line comprising of 3 space-separated integers.
```

##### Output Format:

```
For every test case, Return the minimum time required by you to travel from the top-left cell to the bottom-right cell.
For each test case, print the output in a separate line.
```

##### Constraint :

```
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6
Where ‘rows’ is the number of rows and ‘columns’ is the number of columns. The 2-D list (array) heights would contain the cells and their values with a dimension of ‘rows’ x ‘columns’.
Time Limit: 1 sec
```

Approach 1

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:
- Do not go outside our grid
- The cell is not visited yet
- 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:
- 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.
- 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.

Approach 2

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.

SIMILAR PROBLEMS

# Get DFS Path

Posted: 22 Jul, 2021

Difficulty: Easy

# Get Path using BFS

Posted: 22 Jul, 2021

Difficulty: Easy

# Bellman Ford

Posted: 23 Jul, 2021

Difficulty: Moderate

# Floyd Warshall

Posted: 23 Jul, 2021

Difficulty: Moderate

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate