Last Updated: 26 Mar, 2021
Find Number of Empty cells
Easy
Asked in company
You are given two integers, ‘N’ and ‘K,’ and initially, you have an 'N' * 'N' grid. You are asked ‘K’ queries wherein each query you are given a coordinate, and you have to colour it and print the number of uncoloured cells in the grid.
Input Format:
The first line of the input contains ‘T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘K,’ denoting dimensions of the grid and number of queries.
The following ‘K’ lines contain two space-separated integers, 'X[i]' and 'Y[i]', denoting the coordinates of the grid.
Output Format:
For each test case, return the answer of each query.
Print the answer in a separate line for each query.
Constraints:
1 <= T <= 3
1 <= N <= 5000
1 <= K <= min(3000,N * N)
1 <= X[i], Y[i] <= N
Time limit: 1 sec
Approaches
Explanation:
- There are a total of ‘N’ ^ 2 cells in the grid.
- To find the total number of uncolored cells in the first q queries, we can just find the total number of colored cells in the first q queries and then subtract it from ‘N’ ^ 2 to get the answer.
- So to answer the q’th query we just need to find the number of unique cells in the first q queries.
- This can be done by using a set to store all unique coordinates till the current query.
The steps are as follows:
Initialize a set ‘ST’ which will be used to store coordinates of the colored cells.
In each query, we have coordinates ('X[i]', ‘Y[i]’) and we do the following each time:
- Insert cell number of the coordinates ( ‘X[i]’, ‘Y[i]’) in the set ‘ST’.
- Find the size of the set, 'SZ’.
- Print output as ‘N’ ^ 2 - ‘SZ’.
A cell number of a coordinate is the position this coordinate would be if we were to flatten the matrix i.e. if there was only 1 row and ‘N’ * ‘N’ column. A cell number of coordinate ('i', ‘j’) is = ‘N’ * ‘i’ + ‘j’ .