Last Updated: 18 Mar, 2021

Query And Matrix

Moderate

Asked in companies

Solve now

Problem statement

You are given a binary matrix with ‘M’ rows and ‘N’ columns initially consisting of all 0s. 'Q' queries follow. The queries can be of 4 types:

Query 1: 1 R index
Query 2: 1 C index 
Query 3: 2 R index
Query 4: 2 C index

In each query, the first input is the type of the query, the second input is whether we have to consider the row ('R') or the column ('C') and the third input is the index of the row/column. 

For each type 1 query, we need to flip the elements of the row/column having the given index. 

For each type 2 query, we have to output the number of zeros present in the row/column having the given index.

Note:

Note that the matrix is a binary matrix, meaning that it only contains either 0 or 1.

Example :

Given M = 3, N = 3, 
Queries : 1R1, 1R2, 2C1

So, in the above example the change in the matrix would look like this:

Example

Next query 2C1 will return the count of the number of zeroes in the 1st column: 1

Input Format:

The first line contains an integer ‘T’ which denotes the number of test cases.

The first line of each test case contains two space-separated integers ‘M’ and ‘N’, denoting the dimensions of the matrix.

The next line contains a single integer ‘Q’ denoting the number of queries.

The next ‘Q’ lines of each test contain the queries.

Output Format:

For each test case, return a single integer denoting the number of zeroes according to the given query of type 2.

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

Note:

You don’t need to print anything; It has already been taken care of. Juts implement the given function.

Constraints:

1 <= T <= 10
1 <= M, N  <= 100
1 <= Q <= 1000
1 <= R <= M
1 <= C <= N
type = 1, 2

Time limit: 1 sec

Solve now

Approaches

01 Approach

A simple idea is to traverse the given row or column. If you come across a query that is of type 1 then swap 0 with 1 and vice-versa and for the query of type 2 initialize a variable ‘COUNT’ and increment count when you encounter ‘0’ and return ‘COUNT’.

The steps are as follows:

If the type of query is 1.
- If we have to consider row ‘R’ at the given ‘INDEX’
  - Run a loop for row ‘INDEX’ and every column - ‘i’ : 0 to ‘M’ - 1
    - Flip element at ‘MAT[ ‘INDEX’ ] [ ‘i’ ]’.
- If we have to consider column ‘C’ at the given ‘INDEX’
  - Run a loop for every row and column ‘INDEX’ ’ - ‘i’ : 0 to ‘N’ - 1.
    - Flip element at ‘MAT[ ‘i’ ] [ ‘INDEX’ ]’.
If the type of query is 2.
- Initialize a variable 'COUNT’ with 0.
  - If we have to consider row ‘R’ at the given ‘INDEX’
    - Run a loop for row ‘INDEX’ and every column - i : 0 to ‘M’ - 1
      - If ‘MAT[ ‘INDEX’ ] [ i ]’ is ‘0’, Increment ‘COUNT’.
  - If we have to consider column ‘C’ at the given ‘INDEX’
    - Run a loop for every row and column ‘INDEX’ - i : 0 to ‘N’ - 1.
      - If ‘MAT[ i ] [ ‘INDEX’ ]’ is ‘0’, Increment 'COUNT’.
- Return ‘COUNT’

Solve now