Find Number of Empty cells

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Amazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
4 4
1 2
3 4
2 3
1 2
Sample Output 1:
15
14
13
13
Explanation for Sample Output 1:

Sample Input 2:
2
9 4
1 2
4 1
3 3
2 4
6 5
2 2
2 3
2 3
2 1
3 3
Sample Output 2:
80
79
78
77
35
34
34
33
32
Explanation of Sample Output 2:
In test case 1,

After Query 1, the cell is newly covered and hence 1 less cell will be the output from 81. Thus 80 is the answer.

Similarly Queries 2, 3, 4 are unique, the cell is newly covered and thus answers will be 79, 78, 77 respectively.

In test case 2, 

After Query 1, the cell is newly covered and hence 1 less cell will be the output from 36. Thus 35 is the answer.

After Query 2, the cell is newly covered and hence 1 less cell will be the output from 35. Thus 34 is the answer.

After Query 3, the cell query is repeating. Thus 34 is the answer.

After Query 4, the cell is newly covered and hence 1 less cell will be the output from 34. Thus 33 is the answer.

After Query 5, the cell is newly covered and hence 1 less cell will be the output from 33. Thus 32 is the answer.
Hint

Find the number of coloured cells after each query.

Approaches (1)
Brute Force

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’ .

Time Complexity

O(K * log(K)), Where ‘K’ is the number of queries.

 

Since there are K queries and in each query we are doing O(log(K)) operations insertion or updation in the set. Thus the time complexity will be O(K * log(K)).

Space Complexity

O(K), Where ‘K’ is the number of queries.

 

Since we will store colored cells coordinated in the map, which will take O(K) space. Thus the space complexity will be O(K).

Code Solution
(100% EXP penalty)
Find Number of Empty cells
Full screen
Console