Empty Cells in a Matrix

Easy
0/40
Average time to solve is 10m
profile
Contributed by
28 upvotes
Asked in companies
Deutsche BankShareChatCredit Suisse

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample input 1:
1
2 2
0 0
0 1
Sample output 1:
1 0
Explanation for input 1 :
Initial Matrix:  [[NULL, NULL]
                  [NULL, NULL]]

Matrix after task (0,0)
[[ 0,0 ]
[ 0,NULL]] 

As we can see, there is only one empty cell. So we will print 1.

Matrix after task (0,1)
[[0,0]
[0,0]] 

Now there is no empty cell in the matrix so print 0.
Sample input 2:
1
1 1 
0 0
Sample output 2:
0
Explanation for input 2:
Initial matrix: [[NULL]] 
After processing the task, the matrix will become [[0]].
As there are no empty cells in the matrix, 0 is the answer.
Sample input 3:
2
4 2
0 1 
2 3
3 3
0 0
1 1
2 2
Sample output 3:
9 4 
4 1 0
Hint

Try applying brute force. Can you do it by creating a matrix and then updating it?

Approaches (2)
Brute Force

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:

  1. Create an integer array matrix of size 'N' * 'N' and initialize every cell with -1.
  2. Create an integer array of size K, namely outputArray.
  3. 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’.
  4. Return outputArray.
Time Complexity

O(K * N * N), where ‘N’ is the number of rows and columns of the matrix, and ‘K’ is the number of tasks.
 


We are traversing a matrix of size N * N for each of the ‘K’ tasks. Hence, the time complexity is O(K * N * N).

Space Complexity

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

We are creating a matrix of size N * N. Hence, the space complexity is O(N * N).

Code Solution
(100% EXP penalty)
Empty Cells in a Matrix
Full screen
Console