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.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Frequency Queries
  2. Discussions

Frequency Queries

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 621 Discussions, By:

votes

Please Login in order to post a comment

  • eduardocorral 2 years ago+ 0 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.

    130|
    Permalink
  • naomi_nguyen7 3 years ago+ 0 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`
    
    50|
    Permalink
  • codersanjeev 2 years ago+ 0 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;
    }
    
    15|
    Permalink
  • ivanduka 2 years ago+ 0 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]

    14|
    Permalink
  • nico_dubus 2 years ago+ 0 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");
                }
            }
        }
    }
    
    11|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature