Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Frequency Queries

Sharing is caring!

Problem Statement
You are given 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 queries 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=\left[(1,1),(2,2),(3,2),(1,1),(1,1),(2,1),(3,2)\right]. 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: \left[0,1\right].

Function Description
Complete the freqQuery function. 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 \le q \le 10^6
* 1 \le x,y,z \le 10^9
* All queries\left[i\right]\left[0\right] \in {1,2,3}
* All queries\left[i\right]\left[1\right] \le 10^9

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

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();
    }
}