Last Updated: 1 Feb, 2021

Find A Specific Pair In Matrix

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The idea is to pre-process the given matrix ‘MAT’ and store the minimum element encountered so far in a new 2-D array. We take an extra 2-D matrix ‘dp’ of size ‘N’ x ‘N’ and store the minimum element encountered from ‘MAT[0][0]’ to ‘MAT[i][j]’ at ‘dp[i][j]’. Then the maximum value of the function ‘maxVal’ is max(‘maxVal’, ‘MAT[i][j]’ - ‘dp[i - 1][j - 1]’).

Here is the algorithm :

We declare a 2-d matrix ‘dp’ of size ‘N’ x ‘N’.
We initially fill ‘dp’ as follows:
- ‘dp[0][0]’ = ‘MAT[0][0]’.
- We run a loop for ‘i’ = ‘1’ to ‘N’.
  - ‘dp[i][0]’ = min(‘dp[i-1][0]’, ‘MAT[i][0]’)
- We run a loop for ‘j’ = ‘1’ to ‘N’.
  - ‘dp[0][j]’ = min(‘dp[0][j - 1]’, ‘MAT[0][j]’)
We declare a variable ‘maxVal’ to store our final answer and initialize it with the minimum possible value.
We run a loop for ‘i’ = ‘1’ to ‘N’:
- We run a loop for ‘j’ = ‘1’ to ‘N’:
  - ‘maxVal’ = max(‘maxVal’, ‘MAT[i][j]’ - ‘dp[i - 1][j - 1]’).
  - ‘dp[i][j]’ = min(‘dp[i-1][j]’, min(‘dp[i][j-1]’,’mat[i][j]’)).
Finally, we return ‘maxVal’ as our answer.

Solve now