Last Updated: 2 Apr, 2021

# Path With Minimum Effort

Hard

## Problem statement

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

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

1. 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).
2. 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.
3. 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.
4. We finally return the minimum time taken to traverse from source to destination.