Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 2 Apr, 2021

Hard

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

```
The first line contains two space-separated integers, 'rows' and 'columns'.
Next 'rows' lines contain 'columns' space-separated integers.
```

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

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.

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

Find The Single Element

Easy

Posted: 30 Oct, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022

Find minimum

Hard

Posted: 8 Nov, 2022

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022