Last Updated: 17 Apr, 2021
Add in matrix
Easy
Asked in company
This time Ninja is doing research on a matrix of size ‘N’ X ‘M’ initialised with ‘0’. He performs ‘Q’ operations where each operation is denoted by two integers [ a, b ] and he increments the value of the element present at [x, y] in the matrix such that 1 <= x <= a and 1 <= y <= b.
Ninja is busy doing some other work so he needs your help to know the occurrence of the maximum number in the matrix after all operations.
For Example: If one operations is [2, 2] then
Note:
Indexing of matrix starts from [1, 1] i.e. first element of matrix is [1, 1].
Input Format:
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains three integers ‘N’, ‘M’ and ‘Q’ denoting the number of rows, number of columns of the matrix and number of operations respectively.
The next ‘Q’ lines contain two space-separated integers denoting the operation.
Output Format :
For each test case, return a single integer denoting the number of occurrences of the maximum number.
The output for each test case is printed 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 <= 5
1 <= N <= 200
1 <= M <= 200
1 <= Q <= 200
1 <= A <= N
1 <= B <= M
Time limit: 1 second
Approaches
The idea here is to do exactly the same as written in the question. We will apply brute force and increase each element in the matrix and after all operations, we iterate on the matrix once more to find the occurrence of the maximum number.
Algorithm:
- Declare a 2-D matrix of size ‘N’ X ’M’ initialized with ‘0’.
- Traverse the operation array using ‘i’ from 0 to OPS.SIZE
- Increment all elements present at index (X, Y) in the matrix such that X : 0 to OPS[i][0] and Y : 0 to OPS[i][1].
- Declare a variable ‘FREQ’ := 0 to store the frequency.
- Traverse the matrix using ‘i’ from 0 to ‘N’ and ‘j’ from 0 to ‘M’
- And find the maximum element and increase its frequency FREQ++.
- Return FREQ.
As we can observe that all operations are performed on a submatrix starting from (0, 0) and the maximum element will be only those who are present in all the operations.
So we need to find the intersection of all operations which we can do by finding the minimum row in all operations and minimum columns of each operation.
Algorithm:
- Declare two variables MIN_ROW := N+1 and MIN_COL := M+1
- Traverse the array operations using ‘i’ from 0 to OPS.SIZE:
- MIN_ROW = min(MIN_ROW,OPS[i][0])
- MIN_COL = min(MIN_COL, OPS[i][1])
- Return MIN_ROW * MIN_COL.