Path With Maximum And Minimum Value

Easy
0/40
Average time to solve is 15m
13 upvotes
Asked in company
Adobe

Problem statement

Given a matrix of integers ‘ARR’ with ‘R’ rows and ‘C’ columns, find the maximum score of a path starting at [0, 0] and ending at [R-1, C-1]. The score of a path is the minimum value in that path. For example, the value of the path 8 -> 4 -> 5 -> 9 is 4. A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Example:

Let’s say we have ARR = { {5 4 5} , {1 2 6} , {7 4 6}} so the path with 
maximum value will be 5 -> 4 -> 5 -> 6 -> 6 and we have to return 
the minimum value in this path as the answer i.e 4.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains two integers ‘R’ and ‘C’ denoting the number of rows and columns respectively.

Then the remaining input is of R lines where each line contains C space-separated numbers denoting the elements of the RXC sized matrix ‘ARR’.
Output format: 
For each test case, return the minimum value in the maximum path.

Output for each test case is printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just return the minimum value in the maximum path.
Constraints: 
1 <= T <= 10
1 <= R , C <= 100
0 <= ARR[i][j] <= 10^9

Time Limit: 1 sec
Sample Input 1:
2
2 6
2 2 1 2 2 2
1 2 2 2 1 2
3 3
5 4 5
1 2 6
7 4 6
Sample Output 1:
 2
 4
Explanation 1:
For the first test case, 
The path will be {0, 0} -> {0, 1} -> {1, 1} -> {1, 2} -.> {1, 3} -> 
{0, 3} -> {0, 4} -> {0, 5} -> {1, 5};


Therefore the path highlighted is the maximum path and the 
minimum value in this path will be 2 which is our required answer.

For the second test case,
It is already explained above in the example.
Sample Input 2:
2
3 3
6 8 5
7 2 4
7 7 6
3 4
1 2 3 4
5 6 7 8
9 10 11 12
Sample Output 2:
6
1
Hint

Can you solve this problem by using a priority queue?

Approaches (1)
Path With Maximum And Minimum Value

Approach:

  • The idea is to use a max heap which can be implemented by using a max priority queue. In the priority queue, we will push the unvisited neighbours of the current element which is pop out from the queue from all four directions and side by side also maintain the minimum element which is our required answer.

 

Algorithm:

  • Create a 2d boolean array ‘VISITED’ of the same size as that of the given ‘ARR’ which value initially ‘False’.
  • Next, create a max priority queue ‘PQ’ which will store a pair in which the first one will be the element and the second part will be the indices of the element.
  • Push {ARR[0][0] , {0, 0}} into ‘PQ’.  Also, create an ‘ANS’ variable to store the answer which is equal to ARR[0][0] initially.
  • Now till the priority queue is not empty do the following:
    • Pop-out the first element from the queue and store it in ‘P’.
    • Take X = P.FIRST and Y = P.SECOND.
    • Make VISITED[X][Y] = ‘True’.
    • Also update the ‘ANS’ as ANS = min(ANS, A[X][Y]).
    • Also, check that if we reach the endpoint that is R-1 and C-1 then break the loop.
    • Otherwise, push the element along with its indices of all the unvisited neighbours of the pop-out element into the queue ‘PQ’.
  • Finally, return the ‘ANS’ as the required answer.
Time Complexity

O(R*C*Log(R*C)), where R and C are the rows and the columns of the given input 2d array.

 

Since there is a total of R*C elements, therefore traversing over the matrix will take O(R*C) time and pushing and popping out each element from the Priority Queue ‘PQ’ will take O(Log(R*C)) time. Thus total time complexity will be O(R*C*Log(R*C)).

Space Complexity

O(R*C), where R and C are the rows and the columns of the given input 2d array.

 

O(R*C) extra space is required to maintain the visited array. Also, O(R*C) extra space is required by the priority Queue. Hence, the overall space complexity is O(R*C).

Code Solution
(100% EXP penalty)
Path With Maximum And Minimum Value
Full screen
Console