Add in matrix

Easy
0/40
Average time to solve is 15m
1 upvote
Asked in company
Incedo Inc.

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1:

2
3 3 2
2 2
3 3
4 4 3
1 3
3 1
2 2

Sample Output 1:

4
1

Explanation of Sample Output 1:

Test Case 1: we can see in the image below how we get four occurrence of 2.


Test Case 2:  we can see in the image below how we get one occurrence of 3.

Sample Input 2:

2
4 4 4
1 1
2 2
3 3
4 4
3 4 3
1 4
2 2
3 3

Sample Output 2:

1
2
Hint

Think the brute force way.

Approaches (2)
Brute Force

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.
Time Complexity

O(Q * N * M), where ‘N’ and ‘M’ are the number of rows and columns and ‘Q’ represents the number of operations.

 

In the worst case, we need to update the whole matrix in each operation.

Space Complexity

O(N * M), where ‘N’ and ‘M’ are the number of rows and columns.

 

To store the matrix, we need O(N * M) space.

Code Solution
(100% EXP penalty)
Add in matrix
Full screen
Console