Path With Minimum Effort
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.
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.
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.
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
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-
Find The Single Element
Distance to a Cycle in Undirected Graph
Search In A Sorted 2D Matrix
Fake Coin Problem