Frequency Queries - Hacker Rank Solution

You are given  queries. Each query is of the form two integers described below:
-  : Insert x in your data structure.
-  : Delete one occurence of y from your data structure, if present.
-  : Check if any integer is present whose frequency is exactly . If yes, print 1 else 0.

The queries are given in the form of a 2-D array  of size  where  contains the operation, and  contains the data element. For example, you are given array . The results of each operation are:

Operation   Array   Output
(1,1)       [1]
(2,2)       [1]
(3,2)                   0
(1,1)       [1,1]
(1,1)       [1,1,1]
(2,1)       [1,1]
(3,2)                   1

Return an array with the output: .

Function Description

Complete the freqQuery function in the editor below. It must return an array of integers where each element is a  if there is at least one element value with the queried number of occurrences in the current array, or 0 if there is not.

freqQuery has the following parameter(s):

• queries: a 2-d array of integers

Input Format

The first line contains of an integer , the number of queries.
Each of the next  lines contains two integers denoting the 2-d array .

Constraints

• All 

Output Format

Return an integer array consisting of all the outputs of queries of type .

Sample Input 0

8
1 5
1 6
3 2
1 10
1 10
1 6
2 5
3 2

Sample Output 0

0
1

Explanation 0

For the first query of type , there is no integer whose frequency is  (). So answer is .
For the second query of type , there are two integers in  whose frequency is  (integers =  and ). So, the answer is .

Sample Input 1

4
3 4
2 1003
1 16
3 1

Sample Output 1

0
1

Explanation 1

For the first query of type , there is no integer of frequency . The answer is .
For the second query of type , there is one integer,  of frequency  so the answer is .

Sample Input 2

10
1 3
2 3
3 2
1 4
1 5
1 5
1 4
3 2
2 4
3 2

Sample Output 2

0
1
1

Explanation 2

When the first output query is run, the array is empty. We insert two 's and two 's before the second output query,  so there are two instances of elements occurring twice. We delete a  and run the same query. Now only the instances of  satisfy the query.

Frequency Queries - Hacker Rank Solution

The brute force approach will be to use a container like array or vector and each time we get a query of type  and , we insert and delete the element accordingly by traversing the array. For query of type , we again traverse the array by sorting it and check if any element of a particular count exists. This approach is clearly  which won't pass.

We may improve our approach by using a hashmap. We store the count of each element in the hashmap and increase or decrease the count of a particular element in . For query of type , we can traverse the hashmap and check if any element of that count exists in . This approach runs in  which is still too slow to pass. We can improve.

This time we use two hashmaps. One to store the frequencies and the other to store the frequency of the frequencies.
So, whenever we get query of type , we first get the count (say, ) of the element and then increment it's counter by . Then we decrease the count of  by  in the second map by  and increase the count of  by .
When we get a type  query, again we get it's count (say, ) from the first map and then decrease it by . Now, we decrease the count of  by  and increase the count  by  in the second map.
Finally, for the third query, we can just check if it's entry in the second map is positive. If, yes we print  else .

Problem Setter's code:

#include<bits/stdc++.h>
using namespace std;

//m1 is to store values with their frequency
//m2 is to store the count of every frequency
map<int,int> m1,m2;

int main()
{
 int q;
 scanf("%d",&q);
 int a[q],b[q];
    
    // array of type of queries
 for(int i=0;i<q;i++)
  scanf("%d",&a[i]);
    
    // array of values
 for(int i=0;i<q;i++)
  scanf("%d",&b[i]);
 
 for(int i=0;i<q;i++)
 {
     // insert query
  if(a[i]==1)
  {
   int k=m1[b[i]];
            //decrease count of present frequency
   if(k>0)
    m2[k]--;
            //increase occurence of a number
   m1[b[i]]++;
            //increase count of present frequency + 1
   m2[k+1]++;
  }
        
        //delete query
  else if(a[i]==2)
  {
   int k=m1[b[i]];
   if(k>0)
   {
             //decrease occurence of a number
    m1[b[i]]--;
                //decrease count of present frequency
    m2[k]--;
                //increase count of present frequency - 1
    if(k-1>0) 
     m2[k-1]++;
   }
  }
  else
  {
         //true if the count of asked frequency is non-zero
   if(m2[b[i]]>0)
    printf("1\n");
   else
    printf("0\n");
  }
 }
 return 0;
}

Problem Tester's code:

#!/bin/python3


import os
from collections import defaultdict


def freqQuery(queries):
    elementFreq = defaultdict(int)
    freqCount = defaultdict(int)
    ans = []
    for i, j in queries:
        if i == 1:
            if freqCount[elementFreq[j]]:
                freqCount[elementFreq[j]] -= 1
            elementFreq[j] += 1
            freqCount[elementFreq[j]] += 1            
        elif i == 2:
            if elementFreq[j]:
                freqCount[elementFreq[j]] -= 1
                elementFreq[j] -= 1
                freqCount[elementFreq[j]] += 1
        else:
            # operation 3
            if j in freqCount and freqCount[j]:
                ans.append(1)
            else:
                ans.append(0)
    return ans



if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    queries = []

    for _ in range(q):
        queries.append(map(int, input().rstrip().split()))

    ans = freqQuery(queries)

    fptr.write('\n'.join(map(str, ans)))
    fptr.write('\n')

    fptr.close()