Last Updated: 5 Jan, 2022
The Chunin Ninja
Easy
Asked in companies
You are the Supreme Ninja Warrior on a visit to Ninja Class, and class can be represented as a rectangular matrix ‘ARR’ of ‘N’ rows and ‘M’ columns.
Each Ninja has a skill level, and each element in matrix ‘ARR’ represents the skill level of the Ninja present in the class. More formally, ‘ARR[i][j]’ represents the skill level of Ninja sitting in the ‘jth’ column of the ‘ith’ row.
A ninja is said to be ‘Chunin’ if he has maximum skill among all Ninjas in his column and minimum skill level among all Ninjas in his row.
Can you find all the ‘Chunin’ Ninjas present in the class?
Example :
N = 3 M = 3
ARR = [ [3, 4, 5], [2, 7, 6] , [1, 2, 4] ]
Ninja at Position (0,0) has maximum skill in ‘0th’ column and minimum skill in ‘0th’ row, it is the only Chunin Ninja.
So, we return [ 3 ] as our ‘ANS’.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains two integers, ‘N’ and ‘M’, denoting the number of rows and columns in the matrix ‘ARR’, respectively.
Each of the following for each test case. Print ‘N’ lines contain ‘M’ space-separated integers denoting the skill level of Ninjas.
Output format :
For each test case, print all ‘Chunin’ Ninja present in the class. Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N , M <= 10^5
0 <= ARR[i][j] <= 10^9
Sum of N*M over all Test cases <= 10^5
Time Limit: 1 sec
Approaches
APPROACH :
- We will Pick each element and find the maximum element over its column, and the minimum element over its row.
- If the current element is the maximum element over its column, and the minimum element over its row, insert it into ‘ANS’.
ALGORITHM :
- Initialise an empty array ‘ARR’
- Iterate the first loop from ‘0’ till ‘N’.
- Iterate the second loop from ‘0’ till ‘M’
- Initialise variable ‘MAX_HERE’ and ‘MIN_HERE’ to the value of ‘ARR[i][j]’
- Iterate the third loop inside the second loop from ‘0’ to ‘N’, if any element ‘ARR[k][j] is encountered with a value less than ‘MIN_HERE’ replace ‘MIN_HERE’ with the value of ‘ARR[k][j]’.
- Iterate the third loop inside the second loop from ‘0’ to ‘M’’, if any element ‘ARR[i][k] is encountered with a value greater than ‘MAX_HERE’ replace ‘MAX_HERE’ with the value of ‘ARR[i][k]’.
- If ‘MAX_HERE’ equals ‘ARR[i][j]’ and ‘MIN_HERE’ also equals ‘ARR[i][j]’, push ‘ARR[i][j]’ to ‘ANS’.
- Return ‘ANS’.
APPROACH :
- We will be finding the minimum element for each row and storing them in separate arrays.
- If both maximum and minimum match at the same value, insert the element into the ‘ANS’ array.
ALGORITHM :
- Initialise an empty array ‘ARR’, and two array ‘ROW_MIN’ and ‘COL_MAX’ of size ‘N’ and ‘M’ respectively.
- Iterate the first loop from ‘0’ till ‘N’.
- Assume the first index (‘0’) as the minimum for the current row in variable and set ‘ith’ value of ‘ROW_MIN’ with the first value of the current row. And start iterating over from ‘0’ to ‘M’ and whenever smaller ‘ARR[i][j]’ is encountered replace ‘ROW_MIN’ with ‘ARR[i][j]’.
- Iterate the first loop from ‘0’ till ‘M’’.
- Assume the first index (‘0’) as the minimum for the current row in variable and set ‘jth’ value of ‘COL_MAX’ with the first value of the current row. And start iterating over from ‘0’ to ‘M’ and whenever large ‘ARR[i][j]’ is encountered replace ‘COL_MAX’ with ‘ARR[i][j]’.
- Iterate first loop ‘0’ to ‘N’
- Iterate second loop ‘0’ to ‘M’
- If the current element has value equal to ‘ROW_MIN[i]’ and ‘COL_MAX[j]’ push ‘ARR[i][j] to ‘ANS’
- Iterate second loop ‘0’ to ‘M’
- return ‘ANS’.