Find A Specific Pair In Matrix

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
43 upvotes
Asked in company
Adobe

Problem statement

You have been given a 2-D matrix ‘MAT’ of size ‘N’ x ‘N’ i.e. N rows and N columns. Your task is to find the maximum value of ‘MAT[a][b]’ - ‘MAT[c][d]’ over all possible indices (0 <= ‘a’, ‘b’, ‘c’, ‘d’ < ‘N’) such that . ‘a’ > ‘c’ and ‘b’ > ‘d’.

For example:

Matrix

In this example, to maximise the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ fulfilling the given conditions on indices (‘a’ > ‘c’ and ‘b’ > ‘d’), we take ‘a’ = 2, ‘b’ = 2, ‘c’ = 0 and ‘d’ = 0 .  So, ‘MAT[a][b]’ = 9 and ‘MAT[c][d]’ = 1 and the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ => 9 - 1 = 8 which is maximum among all possible combinations.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains one integer ‘N’ representing the number of rows (or columns) of the square matrix ‘MAT’.

The next ‘N’ lines of each test case contain ‘N’ single space-separated integers denoting the values of ‘MAT’.
Output Format : 
For each test case, print the maximum value of ‘MAT[a][b]’ - ‘MAT[c][d]’ over all possible choices of indices i.e. 0 <= ‘a’, ‘b’, ‘c’, ‘d’ < ‘N’ such that  ‘a’ > ‘c’ and ‘b’ > ‘d’.

Print the output of each test case in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 100
2 <= ‘N’ <= 100
-10^5 <= ‘MAT[i][j]’ <= 10^5

Time Limit : 1 second
Sample Input 1:
2
3
1 2 3
4 5 6
7 8 9
3
-1 -2 -3
-4 -5 -6
-7 -8 -9
Sample Output 1:
8
-4
Explanation For Sample Output 1:
For sample test case 1:

Matrix

In this sample test case, to maximise the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ fulfilling the given conditions on indices (‘a’ > ‘c’ and ‘b’ > ‘d’), we take ‘a’ = 3, ‘b’ = 3, ‘c’ = 0 and ‘d’ = 0 .  So, ‘MAT[a][b]’ = 9 and ‘MAT[c][d]’ = 1 and the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ => 9 - 1 = 8 which is maximum among all possible combinations.

For sample test case 2:

matrix

In this sample test case, to maximise the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ fulfilling the given conditions on indices (‘a’ > ‘c’ and ‘b’ > ‘d’), we take ‘a’ = 1, ‘b’ = 1, ‘c’ = 0 and ‘d’ = 0 .  So, ‘MAT[a][b]’ = -5 and ‘MAT[c][d]’ = -1 and the value of ‘MAT[a][b]’ - ‘MAT[c][d]’ => (-5) - (-1) = -4 which is maximum among all possible combinations.
Sample Input 2:
2
2
1 5 
4 2 
3
-1 5 -3
-14 -5 -2
-7 8 -9
Sample Output 2:
1
22
Hint

Think of a brute force approach.

Approaches (2)
Brute Force

First of all we simply iterate the 2-D array ‘MAT’ and find a cell ‘MAT[c][d]’ where 0 <= ‘c’, ‘d’ < ‘N’ - ‘1’. Then we find the other cell ‘MAT[a][b]’ such that the given condition is fulfilled i.e. ‘a’ > ‘c’ and ‘b’ > ‘d’.

 

Here is the algorithm :

 

  • We declare a variable ‘maxVal’ in which we store our final answer and initialize it with the minimum possible value.
  • We run a loop for ‘c’ = ‘0’ to ‘c’ < ‘N’ - ‘1’.
    • We run a loop for ‘d’ = ‘0’ to ‘d’ < ‘N’ - ‘1’.
      • We run a loop for ‘a’ = ‘c’ + ‘1’ to ‘a’ < ‘N’.
        • We run a loop for ‘b’ = ‘d’ + ‘1’ to ‘b’ < ‘N’.
          • ‘maxVal’ = max( ‘maxVal’, ‘MAT[a][b]’ - ‘MAT[c][d]’).
  •  Finally, we return ‘maxVal’ as our answer.
Time Complexity

O(N ^ 4)  Where ‘N’ is the number of rows (or columns) of the square matrix ‘MAT’.

 

To find the maximum value of the given function, we are iterating ‘MAT’ using 4 nested loops for all possible choices of ‘a’, ‘b’, ‘c’ and ‘d’. Hence, the overall time complexity is O(N ^ 4).

Space Complexity

O(1)  

 

Because we are not using any extra space for finding our resultant answer.

Code Solution
(100% EXP penalty)
Find A Specific Pair In Matrix
Full screen
Console