Frequency Queries


Problem Statement :


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

The queries are given in the form of a 2-D array querries of size q where queries[i][0] contains the operation, and queries[i][1] contains the data element. For example, you are given array 

queries =  [ (1,1), (2,2), (3,2), (1,1), (1,1) , (2,1), (3,2) ] . 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: [0, 1] .

Function Description

Complete the freqQuery function in the editor below. It must return an array of integers where each element is a 1 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 q, the number of queries.
Each of the next q lines contains two integers denoting the 2-d array queries.

Constraints

  1 <= q <= 10^5
  1 <= x, y,  z <= 10^9
  1 <= queries[i][1]  <= 10^9

Output Format

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



Solution :





                        In Python3 :


#!/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()
                    



Copyrights © ClownMonster's Inc