We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Frequency Queries
  2. Discussions

Frequency Queries

Sort 784 Discussions, By:

  • eduardocorral
     + 54 comments

    For Java 7/8, change the boilerplate code to this

    public static void main(String[] args) throws IOException {
    try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {
      int q = Integer.parseInt(bufferedReader.readLine().trim());
      List<int[]> queries = new ArrayList<>(q);
      Pattern p  = Pattern.compile("^(\\d+)\\s+(\\d+)\\s*$");
      for (int i = 0; i < q; i++) {
        int[] query = new int[2];
        Matcher m = p.matcher(bufferedReader.readLine());
        if (m.matches()) {
          query[0] = Integer.parseInt(m.group(1));
          query[1] = Integer.parseInt(m.group(2));
          queries.add(query);
        }
      }
      List<Integer> ans = freqQuery(queries);
      try (BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")))) {
        bufferedWriter.write(
                ans.stream()
                        .map(Object::toString)
                        .collect(joining("\n"))
                        + "\n");
      }
    }
  }

    and note each query is now an int[2] instead of a List. The method to implement is then

    static List<Integer> freqQuery(List<int[]> queries) {

    Reduced the run time in inputs 9 and 13 from ~1.7s (i7-4710MQ CPU @ 2.50GHz) to ~0.8s, and all cases pass now.

  • naomi_nguyen7
     + 27 comments

    My Python solution. Let me know if there's a shorter way:

    `def freqQuery(queries):

    freq = Counter()

cnt = Counter()

arr = []

for q in queries:
    if q[0]==1:
        cnt[freq[q[1]]]-=1
        freq[q[1]]+=1
        cnt[freq[q[1]]]+=1

    elif q[0]==2:
        if freq[q[1]]>0:
            cnt[freq[q[1]]]-=1
            freq[q[1]]-=1
            cnt[freq[q[1]]]+=1

    else:
        if cnt[q[1]]>0:
            arr.append(1)
        else:
            arr.append(0)

return arr`

  • [deleted] + 7 comments

    Used the simple idea that search in keys of map takes O(1) time and search in values of map takes O(n) time.

    first map will store <element, frequency> second map will store <frequency, frequencyCount>

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int nq;
    cin>>nq;
    
    // first will contain <element, frequency> pairs
    map<int,int> first;
    // second will contain <frequency, frequencyCount> pairs
    map<int,int> second;

    for(int i=0; i<nq; i++){
        
        int a, b;
        
        cin >>a >>b;
        
        if(a == 1) {
            // Insert b into first map.
            // Update the frequencies in second map.
            int elem = first[b];    // ele = current frequency of element b.
            
            if(elem > 0) {
                // b was already present.
                second[elem]--;
            }

            // Add b 
            // increase frequency of b
            first[b]++;
            
            // Update the count of new frequency in second map
            second[first[b]]++;
        }

        else if(a == 2) {
            // Remove b
            int temp = first[b];    // temp = current frequency of element b
            if(temp > 0){
                // b is present
                second[temp]--; // Update frequency count
                first[b]--;     // decrease element frequency
                second[first[b]]++; // Update frequency count
            }
        }
        else {
            // check for the b frequency of any element
            int res = second[b];
            if(res > 0) {
                cout<<1<<endl;
            }
            else {
                cout<<0<<endl;
            }
        }
    }
    return 0;
}

  • ivanduka
     + 7 comments

    JavaScript solution (passes all tests):

    const func = arr => {
  const result = [];
  const hash = {};
  const freq = [];

  for (let i = 0; i < arr.length; i += 1) {
    const [action, value] = arr[i];
    const initValue = hash[value] || 0;

    if (action === 1) {
      hash[value] = initValue + 1;

      freq[initValue] = (freq[initValue] || 0) - 1;
      freq[initValue + 1] = (freq[initValue + 1] || 0) + 1;
    }

    if (action === 2 && initValue > 0) {
      hash[value] = initValue - 1;

      freq[initValue - 1] += 1;
      freq[initValue] -= 1;
    }

    if (action === 3) result.push(freq[value] > 0 ? 1 : 0);
  }

  return result;
};

    The idea is that we count 3 things: 1. Creating a dictionary with all added/removed values as keys and number of elements as values 2. Updating a frequency table 3. Result that we return in the end

    Obvious solution would be to keep only the dictionary. However, then in case 3 every time we need to traverse the whole dictionary to check if there is a key with value that equals the search value;

    It works fine on the initial tests but fails on the main set of tests because traversal of the whole dictionary is expensive.

    OK, then we need to keep an extra list of frequencies. I used a simple array where the index is the number of occurencies, for example [0,2,3] means that there are 2 values which occur twice and 3 values that occur 3 times (dictionary in this case would be something like: {12: 2, 14: 3}

    This way in case 3 I need only to check freq[number of occurencies]

  • nico_dubus
     + 5 comments

    I was timing out on a few of the test cases, even using two hashmaps. I tried the optimization of boilerplate code proposed here, and was still timing out on 10 which, to be fair, has a million operations. So to really turbocharge it, you can pass a BufferedReader to your freqQuery function, and rather than pass in an int array[q][2], undertake your operations as you read them line by line, so you only do a single pass.

    My code - if there's another optimization I missed, please feel free to point it out to me. 

    import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Solution {

    // Complete the freqQuery function below.
    static List<Integer> freqQuery (BufferedReader bufferedReader, int q)throws IOException {

        HashMap<Integer, Integer> valuesToCounts = new HashMap<>();
        HashMap<Integer, Set<Integer>> countsToValues = new HashMap<>();
        ArrayList<Integer> results = new ArrayList<>(); 
        int size = q;
           
        for (int i = 0; i < q; i++) {
            String[] query = bufferedReader.readLine().split(" ");
            int operation = Integer.parseInt(query[0]);
            int number = Integer.parseInt(query[1]);

            int oldCount = valuesToCounts.getOrDefault(number, 0); 
            int newCount; 

            if (operation == 1) {
                newCount = oldCount + 1; 
                valuesToCounts.put(number, newCount);
                
                if (countsToValues.containsKey(oldCount)) {
                    countsToValues.get(oldCount).remove(number);
                }
                countsToValues.putIfAbsent(newCount, new HashSet<>());
                countsToValues.get(newCount).add(number);
            }

            if (operation == 2) {
                newCount = (oldCount > 1) ? oldCount - 1 : 0;
                valuesToCounts.put(number, newCount);

                if (countsToValues.containsKey(oldCount)) {
                    countsToValues.get(oldCount).remove(number);
                }

                countsToValues.putIfAbsent(newCount, new HashSet<>());
                countsToValues.get(newCount).add(number);
            }

            if (operation == 3) {
                if (number > size) results.add(0);
                else {
                    results.add((number == 0 || countsToValues.getOrDefault(number, Collections.emptySet()).size() > 0) ? 1 : 0);
                }
            }
        }

        return results; 
    }

    public static void main(String[] args) throws IOException {
        try (BufferedReader bufferedReader = new BufferedReader(
                    new InputStreamReader(System.in))) {
            
            int q = Integer.parseInt(bufferedReader.readLine().trim());

            List<Integer> ans = freqQuery(bufferedReader, q); 
          
            try (BufferedWriter bufferedWriter = new BufferedWriter(
                        new FileWriter(System.getenv("OUTPUT_PATH")))) {
            
                bufferedWriter.write(ans.stream().map(Object::toString)
                            .collect(joining("\n")) + "\n");
            }
        }
    }
}
Load more conversations