Frequency Queries

Sharing is caring!

Problem Statement
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 queries of size where queries[i][0] contains the operation, and queries[i][1] 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. 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 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
* 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

Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static List freqQuery(List queries) {
        List ans = new ArrayList<>();
        final int INSERT = 1;
        final int REMOVE = 2;
        final int QUERY = 3;

        Map value2count = new HashMap<>();
        Map count2countOccurance = new HashMap<>();

        for (Integer[] q: queries) {
            int type = q[0];
            int value = q[1];

            if (type == INSERT) {
                if (value2count.containsKey(value)) {
                    int oldCount = value2count.get(value);
                    int newCount = oldCount + 1;

                    value2count.put(value, newCount);

                    count2countOccurance.put(oldCount, count2countOccurance.get(oldCount) - 1);

                    if (!count2countOccurance.containsKey(newCount)) {
                        count2countOccurance.put(newCount, 0);
                    }
                    count2countOccurance.put(newCount, count2countOccurance.get(newCount) + 1);
                } else {
                    value2count.put(value, 1);
                    if (!count2countOccurance.containsKey(1)) {
                        count2countOccurance.put(1, 0);
                    }
                    count2countOccurance.put(1, count2countOccurance.get(1) + 1);
                }
            } else if (type == REMOVE) {
                if (value2count.containsKey(value)) {
                    int oldCount = value2count.get(value);
                    int newCount = Math.max(oldCount - 1, 0);

                    value2count.put(value, newCount);

                    count2countOccurance.put(oldCount, count2countOccurance.get(oldCount) - 1);

                    if (!count2countOccurance.containsKey(newCount)) {
                        count2countOccurance.put(newCount, 0);
                    }
                    count2countOccurance.put(newCount, count2countOccurance.get(newCount) + 1);
                }
            } else if (type == QUERY) {
                if (count2countOccurance.containsKey(value) && count2countOccurance.get(value) > 0) {
                    ans.add(1);
                } else {
                    ans.add(0);
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        List queries = new ArrayList<>();

        for (int i = 0; i < q; i++) {
            String[] queriesRowTempItems = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

            Integer[] queriesRowItems = new Integer[2];
            queriesRowItems[0] = Integer.parseInt(queriesRowTempItems[0]);
            queriesRowItems[1] = Integer.parseInt(queriesRowTempItems[1]);
            queries.add(queriesRowItems);
        }

        List ans = freqQuery(queries);

        for (int i = 0; i < ans.size(); i++) {
            bufferedWriter.write(String.valueOf(ans.get(i)));

            if (i != ans.size() - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}