Path With Minimum Effort

Hard
0/120
Average time to solve is 20m
profile
Contributed by
39 upvotes
Asked in companies
VisaTata1mg

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3 3
1 2 3
3 8 4
5 3 5
Sample output 1:
1
Explanation:

The figure above describes the following heights list (array). 

Here, The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than the route [1,3,5,3,5].
Sample Input 2:
3 3
1 3 1
9 9 3
9 9 1
Sample output 2:
2
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. 

Time Limit: 1 sec
Hint

You can use a Depth-Search Fashioned algorithm to traverse the heights list (array) combined with a binary search to find out the minimum absolute difference.

Approaches (2)
Path With Minimum Effort

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.
Time Complexity

O(m * n * log (H)), Where ‘m’ is the number of rows and ‘n’ represents the number of columns with ‘H’ being the size of the heights list (array).

 

Since each dfs will take O(m * n) time and we will have O(log H) steps in binary search, where H is biggest number in our grid we have, so final time complexity becomes O(m * n * log (H)).

Space Complexity

O( m * n ),  Where ‘m’ is the number of rows and ‘n’ represents the number of columns.

 

We are using a visited array/list to store keep track of already visited set of nodes hence, the Space Complexity is O( m * n ).

Code Solution
(100% EXP penalty)
Path With Minimum Effort
Full screen
Console