Last Updated: 23 Oct, 2020
Empty Cells in a Matrix
Easy
Asked in companies
You are given an integer 'N' denoting the size of a 'N' * 'N' matrix. Initially, each cell of the matrix is empty. You are also given an integer 'K' denoting the number of tasks. In each task, you are given two integers ('I','J') where 'I' represents the ith row, and 'J' represents the jth column of the matrix.
You have to perform each task in the given order. For each task, you have to place 0 in each cell of ith row and jth column. After completing all the tasks, you have to return an array of size 'K' where the nth element of the array is the number of empty cells in the matrix after the nth task.
For example: Consider an empty matrix of size 'N'*'N' where 'N' = 3.
[[ 'NULL', 'NULL', 'NULL']
[ 'NULL', 'NULL', 'NULL']
[ 'NULL', 'NULL', 'NULL']]
Suppose the value of 'K' is 2, which means we have to perform 2 tasks.
Task 1: (0, 0)
Matrix after placing 0 in each cell of 0th row and 0th column:
[[0, 0, 0]
[ 0, 'NULL', 'NULL']
[ 0, 'NULL', 'NULL']]
The number of empty cells now: 4
Task 2: (1,0)
Matrix after placing 0 in each cell of 1st row and 0th column:
[[0, 0, 0]
[ 0, 0, 0]
[ 0, 'NULL', 'NULL']]
The number of empty cells now: 2
Return the array [4,2]
Note:
1. We call a cell empty only if it does not contain any value.
2. Indexing is 0-based.
Input Format:
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of every test case contains two space-separated integers 'N' and 'K', where 'N' is the number of rows, and the columns of the given matrix and 'K' is the number of tasks.
Next 'K' lines of each test case contain two space-separated integers 'I' and 'J'.
Output format:
For each test case, print a line that contains a vector/array containing the number of empty cells in the matrix after each task.
Note:
You are not required to print anything it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= 'N' <= 10^5
0 <= 'K' <= 10^5
0 <= 'I','J' < 'N'
Time limit: 1 second
Approaches
We will create a matrix of size 'N' * 'N' and initialize all of its elements with a number say -1. Now for every task ('I', 'J'), we will be replacing -1 with 0 for every cell of the ith row and jth column.
Now we will simply count the number of -1 in the matrix using two loops, and we will print it.
Algorithm:
- Create an integer array matrix of size 'N' * 'N' and initialize every cell with -1.
- Create an integer array of size K, namely outputArray.
- Run a loop ‘i’ from 0 to ‘K’.
- Initialize ‘x’ and ‘y’ with ‘tasks[i][0]’ and ‘tasks[i][1]’ respectively.
- Run a loop ‘j’ from 0 to ‘N’:
- Make ‘matrix[x][j]’ and ‘matrix[j][y]’ as 0.
- Initialize a variable ‘count’ with 0.
- Run a loop ‘j’ from 0 to ‘N’ and for every ‘j’ run a loop ‘p’ from 0 to ‘N’:
- Increment ‘count’ by 1 if ‘matrix[j][p]’ is equal to -1.
- Assign outputArray[i] as ‘count’.
- Return outputArray.
Suppose we have a task ('I', 'J'). Now we will update ith row and jth column of the matrix by 0. What can we conclude from this? We can say that the ith row and jth column will not contribute any empty cells. So we can just consider a matrix not having ith row and jth column. This means our number of rows has been reduced by one and the number of columns has also been reduced by 1.
Algorithm:
- Initialize 2 variables, rows by 'N' and columns by 'N'.
- Create an integer array of size 'K' namely outputArray.
- Take 2 sets, rowSet and colSet to keep track of the rows and columns we are eliminating.
- For every task ('I', 'J'), repeat the steps from 5 to 7.
- Check for 'I'
- If 'I' is not present in rowSet, add it to the rowSet and reduce the number of rows by 1.
- If 'I' is already present in the rowSet, we don’t have to do anything because this row has already been eliminated.
- Check for 'J'
- If 'J' is not present in colSet, add it to the colSet and reduce the number of columns by 1.
- If 'J' is already present in the colSet, we don’t have to do anything because this column has already been eliminated.
- Now the number of empty cells would be the product of the remaining rows and columns, insert it to the outputArray.
- Return the outputArray.