Frequency Queries

  • + 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.

    • + 2 comments

      I can confirm that changing the boilerplate code to this made all tests failing due to timeout pass.

      Thanks!

      • + 2 comments

        Thanks!

        • + 8 comments

          Solved it by creating two dictionaries.

          One which holds key value pair of number and its frequencies. And the other which holds key value pairs of a frequency and all the number having that particular frequency. Such as.

          number:frequency
          {4: 2, 5: 2, 3: 0, 1:1}
          
          frequency:numbers
          {0: {3}, 2: {4, 5}, 1:{1}}
          

          Full python solution Hackerrank - Frequency Queries Solution

          • + 0 comments

            here is problem solution in Python java and C++ programming languages. https://programs.programmingoneonone.com/2021/03/hackerRank-frequency-queries-solution.html

          • + 0 comments

            I thought of it as well and was able to figure it out. I love hashtables!

          • + 0 comments

            Great solution , I thought of the same idea , but I think in the second dictionary you don't need to keep track of the exact numbers for each frequency key since the question only asks about whether there is a number of a certain frequency or not so you can only keep the count of the numbers having a certain frequency key as the value for the second dictionary and update that count while inserting and deleting elements

          • + 0 comments

            The second dict only has to keep track of how many numbers have that frequency, not the numbers themselves.

          • + 1 comment

            I had a similar approach: First dictionary (map) holds pairs of {number, frequency}. Second dictionary holds pairs of {frequency, frequency's frequency}. (Note that in the second map you don't really care which values have that frequency, just the number of values that have that frequency).

            • + 0 comments

              Java:

              static List<Integer> freqQuery(List<List<Integer>> queries) {
                  List<Integer> res = new LinkedList<>();
                  Map<Integer, Integer> counts = new HashMap<>();
                  Map<Integer, Integer> freqs = new HashMap<>();
                  for (List<Integer> q : queries) {
                      Integer val = q.get(1);
                      switch (q.get(0)) {
                          case 1:
                              // insert
                              if (counts.containsKey(val)) {
                                  Integer oldCount = counts.get(val);
                                  counts.put(val, oldCount+1);
                                  dec(freqs, oldCount);
                                  inc(freqs, oldCount+1);
                              } else {
                                  counts.put(val, 1);
                                  inc(freqs, 1);
                              }
                              break;
                          case 2:
                              // delete
                              if (counts.containsKey(val)) {
                                  Integer oldCount = counts.get(val);
                                  if (oldCount == 1) {
                                      counts.remove(val);
                                      dec(freqs, 1);
                                  } else {
                                      counts.put(val, oldCount-1);
                                      dec(freqs, oldCount);
                                      inc(freqs, oldCount-1);
                                  }
                              }
                              break;
                          case 3:
                              // check frequency
                              res.add(freqs.containsKey(val) ? 1 : 0);
                              break;
                      }
                  }
              
                  return res;
              }
              
              private static void inc(Map<Integer, Integer> map, Integer i) {
                  Integer oldCount = map.getOrDefault(i, 0);
                  map.put(i, oldCount+1);
              }
              
              private static void dec(Map<Integer, Integer> map, Integer i) {
                  Integer oldCount = map.getOrDefault(i, 0);
                  if (oldCount == 0)
                      return;
                  if (oldCount == 1) {
                      map.remove(i);
                  } else {
                      map.put(i, oldCount-1);
                  }
              }
              
          • + 0 comments

            This is the working solution, I did the same in Java here.

          • + 0 comments

            weird, that's what I did, but I get some errors on the corner cases... need to check more..

          • + 0 comments

            That's exactly what I did but 5 testcases seem to be failing and I don't understand why. Any thoughts? Thanks!

        • + 0 comments

          here is problem solution in python java and c++ programming. https://programs.programmingoneonone.com/2021/03/hackerRank-frequency-queries-solution.html

    • + 1 comment

      Can also confirm that changing my (Java 8) boilerplate code to this made all tests that were failing due to timeout (Test cases 9 - 15) pass.

      Thank you so much, and shame on HackerRank for providing bad boilerplate code!

      • + 1 comment

        Boilerplate is great :), makes you make sure code works. Hints: Input does not fit memory, there are requests for too hight frequencies.

        • + 0 comments

          Good hint, thanks :)

    • + 14 comments

      I did this but still tests 10,12,13 fail due to timeout. Please help

      my solution :

      static List freqQuery(List queries) {

          HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
          List<Integer> retList = new ArrayList<Integer>();
      
          for(int i=0;i<queries.size();i++)
          {
              int op = queries.get(i)[0];
              int num = queries.get(i)[1];
              if(op==1)
              {
                  if(!hash.containsKey(num))
                      hash.put(num,1);
                  else
                      hash.put(num,hash.get(num)+1);
              }
              else
              if(op==2)
              {
                  if(hash.containsKey(num))
                  {
                      if(hash.get(num)<=1)
                          hash.remove(num);
                      else
                          hash.put(num,hash.get(num)-1);
                  }
      
              }
              else
              if(op==3)
              {
                  if(hash.containsValue(num)){
                      retList.add(1);
                  }
                  else
                      retList.add(0);
      
              }
          }
      
          return retList;
      }
      
      • + 3 comments

        Same! The new boilerplate fixed 9, 11 but 10, 12, 13 still failing. I even tried taking OP's suggestion a step further and changed the boilerplate to int[q][2] (instead of just List<int[2]>) and still times out. Bummer.

        • + 0 comments

          Changing to 2-D array worked for me

        • + 4 comments

          I kept adjusting my code, and got my solution to O(n), where n = number of queries, and it still didn't pass test case 10 due to time out. Cut out a bunch of fat from the Boilerplate, and finally got it everything to pass with my solution. Here's what I ended up with for my boilerplate:


          public static void main(String[] args) throws IOException {
                  try (BufferedReader bufferedReader = new BufferedReader(
                              new InputStreamReader(System.in))) {
                      
                      int q = Integer.parseInt(bufferedReader.readLine().trim());
                      int[][] queries = new int[q][2];
                     
                      for (int i = 0; i < q; i++) {
                          String[] query = bufferedReader.readLine().split(" ");
                          queries[i][0] = Integer.parseInt(query[0]);
                          queries[i][1] = Integer.parseInt(query[1]);
                      }
                    
                      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");
                      }
                  }
              }
          


          Solution method does need to take in int[][] instead of List<List<Integer>>

          • + 1 comment

            Thanks, Finally this worked for me. I used two maps one to track values and another to track frequencies. I don't know why hackerrack adds boiler plate code if it's so bad.

          • + 0 comments

            Didn't work for me!

          • + 0 comments

            Worked for me!

          • + 0 comments

            bufferedWriter.write(ans.stream().map(Object::toString) .collect(joining("\n")) + "\n"); part of the boiler plate contains error please help cant figure out

        • + 3 comments

          For me, setting the intitital capacity of the maps made the difference between the 1000000 query tests timing out vs. passing...

          static List freqQuery(int[][] queries) {

              int qs = queries.length;
          
              // maps values and their frequencies
              // setting the initial capacity to qs was key to not timing out
              Map<Integer, Integer> map = new HashMap<>(qs);
          
              // maps frequencies and number of values which have that frequency
              // setting the initial capacity to qs was key to not timing out
              Map<Integer, Integer> freqMap = new HashMap<>(qs);
          
          • + 0 comments

            mine also passed all the test cases by just setting map size to number of queries and burn down boiling code to the array.

          • + 0 comments

            // Can someone please tell me why 5 testcases fail with this code vector freqQuery(vector> queries) { map store; vector result; long n=queries.size();

            for(int i=0;i

               }
            

            } if(queries[i][0]==3) { int count=0;

               for(auto it=store.begin();it!=store.end();it++)
               {  
                   if(it->second==queries[i][1])
                   {  count=1;
                      break;
                   }
            
               }
               if(count==1)
               {
                   result.push_back(1);
            
               }
               else
                  result.push_back(0);
            

            } } return result; }

          • + 0 comments

            Great suggestion. You are right. No need of changing the boiler plate code. But instead of setting the initial capacity using hash map, I used a linked hash map and that worked. Linked Hash Map doesn't have the added time complexity of resizing (i.e. everytime the length exceeds the default size)

      • + 10 comments

        Hashmap.containsValue is O(n) time complexity - more expensive than needed. In my solution, I use both a counter Hashmap to know how many times a specific number appears and a frequency Hashmap to count how many numbers appeared for a specific amount of times. Then, for op==3 I just check if frequency is greater than zero.

        All tests passed after changing the boilerplate.

        • + 0 comments

          Oh, like a histogram! Nice work! Maybe call that frequency variable 'histogram'. Will make much easier to read/understand.

        • + 0 comments

          Ultimate :)

        • + 0 comments

          Nice solution.

        • + 1 comment

          No it is O(1). It is basicallly calculating the hashcode!

          • + 0 comments

            He is talking about map.containsValue NOT containsKey. So you basically have to iterate through the map to know whether desired value is present in the map or not. And that's O(n). where n is the number of keys present in the map.

        • + 1 comment

          Can you please check my code, It's timing out for testcase 9, 10, 11, 12, 13. I have chnaged boilerplate code. Thanks in advance.

          static List<Integer> freqQuery(int[][] queries) {
              List<Integer> res = new ArrayList<>();
              if(queries==null || queries.length==0){
                  return null;
              }
              Map<Integer, Integer> elementFreeqMap = new HashMap<>();
              Map<Integer, Integer> freqCountMap = new HashMap<>();
              int currentFreq = 0;
              int currFreqElemCount = 0;
              for(int[] query:queries){
                  int command = query[0];
                  int param = query[1];
                  if(command==1){
                      currentFreq = elementFreeqMap.getOrDefault(param, 0);
                      currFreqElemCount = freqCountMap.getOrDefault(currentFreq, 0);
                      if(currFreqElemCount>0){
                          freqCountMap.put(currentFreq, currFreqElemCount-1);
                      }
                      currentFreq ++;
                      elementFreeqMap.put(param,currentFreq);
                      currFreqElemCount = freqCountMap.getOrDefault(currentFreq, 0);
                      freqCountMap.put(currentFreq, currFreqElemCount+1);
                  }else if(command==2){
                      currentFreq = elementFreeqMap.getOrDefault(param, 0);
                      if(currentFreq>0){
                          currFreqElemCount = freqCountMap.getOrDefault(currentFreq, 0);
                          if(currFreqElemCount>0){
                              freqCountMap.put(currentFreq, currFreqElemCount-1);
                          }
                          currentFreq--;
                          elementFreeqMap.put(param,currentFreq);
                          currFreqElemCount = freqCountMap.getOrDefault(currentFreq, 0);
                          freqCountMap.put(currentFreq, currFreqElemCount+1);
                      }
                  }else if(command==3){
                      currFreqElemCount = freqCountMap.getOrDefault(param, 0);
                      if(currFreqElemCount==0){
                          res.add(0);
                      }else{
                          res.add(1);
                      }
                  }else{
                      //error
                  }
              }
              return res;
          }
          
          • + 0 comments

            From my experience, the getOrDefault() method is slower than the simple if-else get statements, and helped me get over the line for no fewer than 3 test cases.

        • + 0 comments

          how you solve this error Sorry, we can't accept your submission. The custom input size should not exceed 50Kb.

        • + 8 comments

          This solution in Python, and it passed all test cases.

          def freqQuery(queries):
              d = defaultdict(lambda: 0)
              f = defaultdict(lambda: 0)
              output = []
              for command, key in queries: # O(n) queries
                  if command == 1:
                      f[d[key]] = max(0, f[d[key]] - 1)
                      d[key] += 1
                      f[d[key]] += 1
                  elif command == 2:
                      f[d[key]] = max(0, f[d[key]] - 1)
                      d[key]= max(0, d[key] - 1)
                      if d[key] > 0:
                          f[d[key]] += 1
                  else:
                      if f[key] > 0: # O(1)
                          output.append(1)
                      else:
                          output.append(0)
              return output
          
          • + 0 comments

            Seems like python has a hard time switching from operations to printing. So placing everything in a list and then printing it works! Nice job! Thanks for sharing!

          • + 0 comments

            Here is a shorter variant in Python3 that uses a frequency dictionary of sets rather than of ints. I was inspired by fromtheeast1's use of a frequency dictionary f, which prevents a timeout on the longer query lists. This success is due to a dict's or set's find-by-value time being O(1) average and O(n) worst, whereas a list's find-by-value time is O(n) average.

            from collections import defaultdict
            def freqQuery(queries):
            
                d, f = defaultdict(int), defaultdict(set)
                for c,v in queries:
                    if c==3 : yield 1 if f[v] else 0 ; continue
                    f[d[v]].discard(v)
                    if c==1 : d[v] += 1
                    elif d[v] : d[v] -= 1
                    f[d[v]].add(v)
            
          • + 1 comment

            Can you explain the use of d and f deictionaries and why increment f[d[key]] when command is 2.

          • + 0 comments

            Just a quick comment, in

            elif command == 2: f[d[key]] = max(0, f[d[key]] - 1) d[key]= max(0, d[key] - 1) if d[key] > 0: f[d[key]] += 1

            You don't need to check for if d[key] > 0 , as it's already taken care of in the max(0, d[key] - 1) part

          • + 0 comments

            from collections import defaultdict

            d,f=defaultdict(int),defaultdict(int) cnt=0 for _ in range(int(input())): n,k=map(int, input().split()) if(n==1): f[d[k]]-=1 d[k]+=1 f[d[k]]+=1 if(n==2): f[d[k]]-=1 d[k]-=1 f[d[k]]+=1 if(n==3): if(f[k]>0): print(1) else: print(0)

          • + 0 comments

            Can you explain the logic behind? Thank u.

        • + 0 comments

          awesome

        • + 0 comments

          only test case 11 not passed. i think problem in containsValue() method. please help..

          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 abc {

          // Complete the freqQuery function below.
          static List<Integer> freqQuery(List<int[]> queries) {
              List<Integer> arr = new ArrayList<>(); 
              Map<Integer, Integer> hm = new HashMap<Integer,Integer>();
              int a;
              int b; 
              for(int i=0;i<queries.size();i++)
              {
                  a=queries.get(i)[0];
                  b=queries.get(i)[1];
          
                  if(a==1)
                  {
                      hm.put(b, hm.getOrDefault(b, 0)+1);
                  }
                  else if(a==2)
                  {
                      if(hm.getOrDefault(b, 0)>0)
                      {
                          hm.put(b,hm.getOrDefault(b, 0)-1);
                      }  
          
                  }
                  else
                  {
                      if(hm.containsValue(b))
                      {
                          //hm.values().remove(queries.get(i).get(1));
                          arr.add(1);
                      }
                      else
                      {
                          arr.add(0);
                      }
                  }
              }
              return arr;
          
          }
          

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

        • + 0 comments

          Thanks for this :)

      • + 4 comments

        This solution works

        static List<Integer> freqQuery(List<int[]> queries) {
            final Map<Integer, Integer> valueToFreq = new HashMap<>();
            final Map<Integer, Integer> freqToOccurrence = new HashMap<>();
            final List<Integer> frequencies = new ArrayList<>();
        
            int key;
            int value;
            Integer oldFreq;
            Integer newFreq;
            Integer oldOccurrence;
            Integer newOccurrence;
            for (int[] query : queries) {
                key = query[0];
                value = query[1];
                if (key == 3) {
                    if (value == 0) {
                        frequencies.add(1);
                    }
                    frequencies.add(freqToOccurrence.get(value) == null ? 0 : 1);
                } else {
                    oldFreq = valueToFreq.get(value);
                    oldFreq = oldFreq == null ? 0 : oldFreq;
                    oldOccurrence = freqToOccurrence.get(oldFreq);
                    oldOccurrence = oldOccurrence == null ? 0 : oldOccurrence;
        
                    if (key == 1) {
                        newFreq = oldFreq + 1;
                    } else {
                        newFreq = oldFreq - 1;
                    }
                    newOccurrence = freqToOccurrence.get(newFreq);
                    newOccurrence = newOccurrence == null ? 0 : newOccurrence;
        
                    if (newFreq < 1) {
                        valueToFreq.remove(value);
                    } else {
                        valueToFreq.put(value, newFreq);
                    }
        
                    if ((oldOccurrence - 1) < 1) {
                        freqToOccurrence.remove(oldFreq);
                    } else {
                        freqToOccurrence.put(oldFreq, oldOccurrence - 1);
                    }
                    freqToOccurrence.put(newFreq, newOccurrence + 1);
                }
            }
            return frequencies;
        }
        
        • + 0 comments

          Can you please explain your solution. Thank you

        • + 0 comments

          The following should be removed.

          if (value == 0) { frequencies.add(1); }

          In the contstraints section it mentions that "z" is >= 1.

          Also if 0 was possible you would be adding a 1 and then a 0 from your next statment.

        • + 0 comments

          For me didn't work failed in 4 cases

        • + 0 comments

          You are just a frikin beast bro :)

      • + 1 comment

        This isn't an issue with boiler plate. Your code is failing for cases where there is large amount of queries for op 3 that don't find a matching value.

        containsValue is probably O(n) since the value list is not sorted.

        Imagine your hash had >100k unique entries all with a frequency of one. Each query with op 3 would have to do 100k tests if the the value was two. This would be true even if every call to op 3 was testing for the same exact value each time!

        That is going to be really really slow. Especially if you do all op 3 queries after all op 1 and op 2 queries. The hash table is not changing and we're passing the same values over and over and yet this code does O(n) look up every time.

        If you want it to be fast you need a reverse look up of frequency value to list of operand.

        • + 0 comments

          This is what helped me.

          Ended up having to add some extra operations to op 1 and 2 to maintain a second map of frequencies. But op 3 is now O(1), which was the bottleneck.

      • + 0 comments

        else if(op==3) { need to compare the count of a number.. Z not the actual number

                if(hash.containsValue(num)){
        
      • + 0 comments

        You are iterating the map for finding whether the required frequency is present or not. Try maintaining the frequency to values map. So you won't have to iterate the map. see below code :-

        static List freqQuery(List queries) { List result = new ArrayList<>(); Map operationsMap = new HashMap();

            Map<Integer, Set<Integer>> frequencyMap = new HashMap<>();
            for (int[] query : queries) {
                switch (query[0]) {
                case 1:
                    Integer m = operationsMap.get(query[1]);
                    if (m == null) {
                        operationsMap.put(query[1], 1);
                        Set<Integer> sampleMap = frequencyMap.get(1);
                        if (sampleMap != null)
                            sampleMap.add(query[1]);
                        else
                            frequencyMap.put(1, new HashSet() {
                                {
                                    add(query[1]);
                                }
                            });
                    } else {
                        operationsMap.put(query[1], ++m);
                        frequencyMap.get(m - 1).remove(query[1]);
                        Set<Integer> sampleMap = frequencyMap.get(m);
                        if (sampleMap != null)
                            sampleMap.add(query[1]);
                        else
                            frequencyMap.put(m, new HashSet() {
                                {
                                    add(query[1]);
                                }
                            });
                    }
        
                    break;
                case 2:
                    Integer n = operationsMap.get(query[1]);
                    if (n == null)
                        break;
                    else if (n == 1) {
                        operationsMap.remove(query[1]);
                        frequencyMap.get(1).remove(query[1]);
                    } else {
                        operationsMap.put(query[1], --n);
                        frequencyMap.get(n + 1).remove(query[1]);
                        Set<Integer> sampleMap = frequencyMap.get(n);
                        if (sampleMap != null)
                            sampleMap.add(query[1]);
                        else
                            frequencyMap.put(n, new HashSet() {
                                {
                                    add(query[1]);
                                }
                            });
        
                    }
                    break;
                case 3:
                    result.add((frequencyMap.get(query[1]) == null || frequencyMap.get(query[1]).isEmpty()) ? 0 : 1);
                    break;
                }
            }
        

        return result; }

      • + 0 comments

        i also did same but my test case failed dur to time out

      • + 0 comments

        if(hash.get(num)<=1) hash.remove(num); else hash.put(num,hash.get(num)-1);

                 Change this snippet to :        
                 if(hash.containsKey(num)){     
                        hash.put(num,hash.get(num)-1);
                        if(hash.get(num)==0) 
                                            hash.remove(num);
                    }
        
      • + 0 comments

        int op = queries.get(i).get(0); int num = queries.get(i).get(1);

      • + 0 comments

        Use

        hash.put(num,hash.getOrDefault(num,0)+1); for creating a one liner frequency counter... Happy Coding ;-)

      • + 0 comments

        This code may not perform well since hash.containsValue has a time complexity of O(n). Need to obtain the frequency in O(1) time. I used another map for frequency. This code has some functional issue. Trying to fix it.

        so far I've got the following:

        import java.io.; import java.util.;

        public class Solution2 {

        // Complete the freqQuery function below.
        static List<Integer> freqQuery(int[][] queries) {
            Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
            List<Integer> retList = new ArrayList<Integer>();
            Map<Integer,Integer> frequency=new HashMap<Integer,Integer>();
            int cnt=0;
        
            for(int i=0;i<queries.length;i++)
            {
                int op = queries[i][0];
                int num = queries[i][1];
                cnt++;
                if(op==1)
                {
                    if(!hash.containsKey(num)) {
                        hash.put(num,1);
                        if(frequency.containsKey(1)){
                            frequency.put(1,frequency.get(1)+1);
                        } else {
                            frequency.put(1,1);
                        }
                    }
                    else {
                        frequency.put(hash.get(num),frequency.get(hash.get(num))-1);
                        hash.put(num,hash.get(num)+1);
                        if (frequency.containsKey(hash.get(num))){
                            frequency.put(hash.get(num),frequency.get(hash.get(num))+1);
                        } else {
                            frequency.put(hash.get(num),1);
                        }
        
                    }
        
                }
                else
                if(op==2)
                {
                    if(hash.containsKey(num))
                    {
                        if(hash.get(num)<=1) {
                            hash.remove(num);
                            if (frequency.get(1)==1)
                                frequency.remove(1);
                            else
                                frequency.put(1,frequency.get(1)-1);
                        }
                        else {
                            frequency.put(hash.get(num),frequency.get(hash.get(num))-1);
                            hash.put(num,hash.get(num)-1);
                            frequency.put(hash.get(num),frequency.get(hash.get(num))+1);
                        }
                    }
                }
                else
                if(op==3)
                {
        
                    if(frequency.containsKey(num) && frequency.get(num)>=1){
                        retList.add(1);
                    }
                    else
                        retList.add(0);
                }
            }
            return retList;
        
        }
        
        public static void main(String[] args) throws IOException {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter("c:\\temp\\aa.txt"));
        
            int q = Integer.parseInt(bufferedReader.readLine().trim());
        
            int[][] queries = new int[q][2];
        
            for (int i = 0; i < q; i++) {
                String[] queriesRowTempItems = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
        
                queries[i][0]=Integer.parseInt(queriesRowTempItems[0]);
                queries[i][1]=Integer.parseInt(queriesRowTempItems[1]);
        
            }
        
            List<Integer> 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();
        }
        

        }

      • + 0 comments

        instead of using containsKey and containsValue, try to use get and put operations. I got all test cases solved

    • + 2 comments

      Thanks! Now tests 9-13 pass without "Terminated due to timeout" status with Java 8.

      • + 1 comment

        include

        using namespace std;

        string ltrim(const string &); string rtrim(const string &); vector split(const string &);

        // Complete the freqQuery function below. vector freqQuery(vector> queries) {

        map m; map m1; vector v; for(int i=0;i

                if(queries[i][0]==1)
                {
                    m[queries[i][1]]++;
                    m1[m[queries[i][1]]]++;
                }
                else if(queries[i][0]==2)
                {
                    auto f=m.find(queries[i][1]);
                    if(f!=m.end())
                    {
                        m[queries[i][1]]--;
                        m1[m[queries[i][1]]]--;
                    }
        
                }
                else if(queries[i][0]==3)
                {
                    int flag=0;
                    auto f=m1.find(queries[i][1]);
                    if(f!=m1.end())
                    {
                        if(f->second>0)
                        flag=1;
                    }
        
                    if(flag==0)
        
                      v.push_back(0);
                      else
                      v.push_back(1);
        
                }
        }
                    return v; 
        

        }

        int main() { ofstream fout(getenv("OUTPUT_PATH"));

        string q_temp;
        getline(cin, q_temp);
        
        int q = stoi(ltrim(rtrim(q_temp)));
        
        vector<vector<int>> queries(q);
        
        for (int i = 0; i < q; i++) {
            queries[i].resize(2);
        
            string queries_row_temp_temp;
            getline(cin, queries_row_temp_temp);
        
            vector<string> queries_row_temp = split(rtrim(queries_row_temp_temp));
        
            for (int j = 0; j < 2; j++) {
                int queries_row_item = stoi(queries_row_temp[j]);
        
                queries[i][j] = queries_row_item;
            }
        }
        
        vector<int> ans = freqQuery(queries);
        
        for (int i = 0; i < ans.size(); i++) {
            fout << ans[i];
        
            if (i != ans.size() - 1) {
                fout << "\n";
            }
        }
        
        fout << "\n";
        
        fout.close();
        
        return 0;
        

        }

        string ltrim(const string &str) { string s(str);

        s.erase(
            s.begin(),
            find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
        );
        
        return s;
        

        }

        string rtrim(const string &str) { string s(str);

        s.erase(
            find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
            s.end()
        );
        
        return s;
        

        }

        vector split(const string &str) { vector tokens;

        string::size_type start = 0;
        string::size_type end = 0;
        
        while ((end = str.find(" ", start)) != string::npos) {
            tokens.push_back(str.substr(start, end - start));
        
            start = end + 1;
        }
        
        tokens.push_back(str.substr(start));
        
        return tokens;
        

        }

        • + 1 comment

          bro, u can't pass any test cases. infact you haven't read the question.

          • + 3 comments

            vector freqQuery(vector> queries) {

            vector v;

            map m;

            map m1;

            for (int i = 0; i

            if (queries[i][0] == 1) {
            
              if (m[queries[i][1]] > 0) {
            
                m1[m[queries[i][1]]]--;
            
              }      
            
              m[queries[i][1]]++;
            
              m1[m[queries[i][1]]]++;
            
            }
            
            else if (queries[i][0] == 2) {
            
              if (m[queries[i][1]] > 0) {
            
                m1[m[queries[i][1]]]--;
            
                m[queries[i][1]]--;
            
                m1[m[queries[i][1]]]++;
            
              };
            
            }
            
            else {
            
              if (m1[queries[i][1]]>0)
            
                v.push_back(1);
            
              else 
            
                v.push_back(0);
            
            }
            

            } return v; }

            • + 1 comment

              Test case 10 got terminated due to timeout......

              • + 0 comments

                If you're getting a time out that means your algorithm can be improved. Try to come up with a solution that doesn't use loops at

            • + 0 comments

              Nice solution. All test cases passed.

            • + 0 comments

              very good solution,easy to understand

    • + 0 comments

      I agree with above comment.

    • + 1 comment

      I am getting compilation error in the main after changing my boilerplate code. Solution.java:63: error: ')' expected .map(Object::toString) ^

      Solution.java:63: error: ';' expected .map(Object::toString) ^

      Solution.java:63: error: not a statement .map(Object::toString) ^

      Solution.java:63: error: ';' expected .map(Object::toString) ^

      Solution.java:65: error: not a statement + "\n"); ^

      Solution.java:65: error: ';' expected + "\n"); ^

      • + 0 comments

        Check for opening braces.

    • + 0 comments

      That was very helpful. Thank you.

      • Ramo
    • + 0 comments

      Good catch! I was hoping something like this was the case. I was pretty confident my implementation was O(1) for each of the query operations, but was still getting timeout errors for cases 9-13. After fixing the boilerplate code, all cases are passing. Thanks!

    • + 0 comments

      Hackerrank has so many issues... Thanks a ton! This made my test cases pass. My algorithm was linear and always used constant time access, so really this boiler plate code shouldn't matter if the tests are correct. I.E. they should be testing Big O not absolute time.

    • + 0 comments

      It's sad! I wasted hours trying to figure out why my tests were timing-out only to find out the bloddy boilerplate code as the culprit!

    • + 0 comments

      Very true. Saved further debugging time! I was wondering why its still failing instead my algorithm is quite efficient

    • + 0 comments

      I supposed, the result depends on server state. I have to rewrite output code and add inverse map to pass all tests.

    • + 0 comments

      Thank you. I didn't know why I had problems of timeout, but your change solved my problem. TY.

    • + 0 comments

      Thanks, the Java 8 harness is often joke tier but this one... I came to the discussions after measuring that the whole main method took 1600ms while my own code took 200ms for one of the failing cases.

    • + 0 comments

      Thanks, works for me!

    • + 0 comments

      Same for me. Solution is in O(n), this new boiler plate made me pass the tests immediately.

    • + 0 comments

      I was surprised that when I changed the boilerplate to use an array list presized to q, with elements that were array lists of size 2, I still couldn't beat the timeout. If anybody gets this to work with arraylist or list as the entries, I would be curious to see what they did in the boilerplate. Maybe above would work with compiled pattern but array list of array lists.... Maybe it's the time lost simply to allocate a wrapped integer instead of a primitive.

    • + 0 comments

      thank you. I was slowly getting pissed off but now everything passes.

    • + 0 comments

      Arrrrgh.... changed the function to take an int[], AND had it return an int[] (by counting the number of queries on input, and then passing that into the function) and am still timing out on 12 and 13. Stripped down my code so it now uses only a single non-primitive structure (one Map to keep track of the frequency of each number), and it's still not passing.

      I'll have to come back to this one.

    • + 0 comments

      My solution was showing WA for test cases 9-13. Changing boiler plate code fixed it.

      Thanks a lot @eduardocorral

    • + 0 comments

      Thank you! I was just coming to the discussion to complain how tests are timing out on my O(n) solution and it's not obvious how to optimize it to pass.

    • + 0 comments

      Yay, works great! Thanks @eduardocorral. Agreed, HackerRank should test their own code.

    • + 0 comments

      Thank you for this. Was there more optimizations that i should have made that could have passed? I went over all queries once and used 2 maps to count frequencies and then the number of occurances for a particular value.

    • + 0 comments

      confirm, thank you!

    • + 0 comments

      Thanks man:) I spent 2 hours trying to understand what else can be improved. Shame on hackerrank boilerplate.

    • + 0 comments

      I also confirm that changing the boilerplate code to this made all tests failing due to timeout pass. Thank you so much !

    • + 0 comments

      Thanks. Finally it's work for me.

    • + 0 comments

      Why changing to int[] make it faster? I changed the code and all the tests passed. I wonder why. Is it because intializing a list is slower than intializing an array? Or list.get() is slower than array[index]?

    • + 1 comment
      [deleted]
      • + 0 comments

        Still test cases 10,11,12 could not pass.

    • + 0 comments

      Test cases 10-13 were failing but after changing the boilerplate code to the above code, they passed. Thanks brother.!

    • + 0 comments

      Bless you. You code executes 2-3 times faster on my machine and I finally passed the tests

    • + 1 comment

      There are two more things have to be done before passing all test cases.

      1. Use String.split() instead of pattern match.
      2. Use 2D array instead of List<int[]> to store all queries.
      public static void main(String[] args) throws IOException {
          try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {
      
              int q = Integer.parseInt(bufferedReader.readLine().trim());
              int[][] queries = new int[q][2];
              
              for (int i = 0; i < q; i++) {
                  String[] qs = bufferedReader.readLine().split(" ");
                  queries[i][0] = Integer.parseInt(qs[0]);
                  queries[i][1] = Integer.parseInt(qs[1]);
              }
      
              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");
              }
          }
      }
      
      • + 0 comments

        I am still timingout on 9,10,11 with this boiler plate code.

    • + 0 comments

      Can you give me your code

    • + 3 comments

      For all those who were like me , trying to find solution for java.... just use the above one or fast IO (make sure u do the same justice with output also) with your own implementation........

      OR

      import java.io.; import java.util.; import static java.util.stream.Collectors.joining;

      public class Solution { public static void main(String[] args) throws IOException {

          BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
          BufferedWriter out = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
      
          List<Integer> result = new ArrayList<>();
          int n = Integer.parseInt(in.readLine());
          HashMap<Long, Long> map = new HashMap<Long, Long>();
          HashMap<Long, Long> freq = new HashMap<Long, Long>();
      
          for (int i = 0; i < n; i++) {
              StringTokenizer s= new StringTokenizer(in.readLine());
              int a = Integer.parseInt(s.nextToken());
              final long b = Long.parseLong(s.nextToken());
              switch (a) {
                  case 1:
                      freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
                      map.compute(b, (k, v) -> v == null ? 1 : v + 1);
                      freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
                      break;
                  case 2:
                      freq.computeIfPresent(map.get(b), (k, v) -> v == 1 ? freq.remove(map.get(b)) : v - 1);
                      map.computeIfPresent(b, (k, v) -> v == 1 ? map.remove(b) : v - 1);
                      freq.compute(map.get(b), (k, v) -> v == null ? 1 : v + 1);
                      break;
                  case 3:
                      result.add(freq.containsKey(b) ? 1 : 0);
                      break;
              }
          }
          out.write(result.stream().map(Object::toString).collect(joining("\n")) + "\n");
      
          in.close();
          out.close();
      }
      

      }

      • + 0 comments

        Bro, thank you very much for the solution, since two days I'm trying for this, tried in hundreds of ways, but only yours suceeded. thanks a lot

      • + 0 comments

        Thanks, your input/output code was the key for me. I found that the official boilerplate and other ones provided both weren't passing for me, but this did the trick!

      • + 0 comments

        Thank you very much bro. i almost gave up on this, but saved me☺☺☺

    • + 0 comments

      Using Java 8 even with the change in the boiler plate my code timed out some test cases.

      I switched to using Java 7 and all tests pass.

    • + 0 comments

      Thank you so much for this! I was beginning to pull my hair wondering why I was still getting timeouts after implementing a reverse HashMap to keep track of frequencies instead of calling values().contains()

    • + 0 comments

      Check my accepted c++ code here: https://www.hackerrank.com/challenges/frequency-queries/forum/comments/648137?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

    • + 0 comments

      Thank you for pointing this out. Here is a c# version of boiler plate:

              static void Main(string[] args)
              {
                      int q = Convert.ToInt32(Console.ReadLine().Trim());
      
                      var queries = new int[q,2];
      
                      for (int i = 0; i < q; i++)
                      {
                          var nq = new int[2];
                          nq = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(queriesTemp => Convert.ToInt32(queriesTemp)).ToArray();
                          queries[i, 0] = nq[0];
                          queries[i, 1] = nq[1];
                      }
      
                      List<int> ans = freqQuery(queries);
                      Console.WriteLine(String.Join("\n", ans));
              }
      
    • + 0 comments

      Why doesn't this code which runs in O(n) pass the test cases 10, 11, 12 and 13? It times out.

      static List<Integer> freqQuery(List<int[]> queries) {
          List<Integer> result = new ArrayList<Integer>();
          HashMap<Integer, Integer> map = new HashMap<>();
          HashMap<Integer, Integer> freq = new HashMap<>();
          for (int[] q: queries) {
              System.out.println("\nIndex: " + _count ++);
              int x = q[0];
              int y = q[1];
              Integer count = map.getOrDefault(y, 0);
              Integer _freq = freq.getOrDefault(count, 0);            
              if (x == 1) {
                  freq.put(count, _freq > 0 ? (_freq - 1): 0);
                  freq.put(count + 1, freq.getOrDefault(count + 1, 0) + 1);
                  map.put(y, count + 1);
              } else if (x == 2) {
                  if (count != 0) {
                      freq.put(count, _freq > 0 ? (_freq - 1): 0);
                      freq.put(count - 1, freq.getOrDefault(count - 1, 0) + 1);
                      map.put(y, count - 1);
                  }
              } else if (x == 3) {
                  result.add(freq.getOrDefault(y, 0) > 0 ? 1: 0);
              }
          }
          return result;
      }
      
    • + 0 comments

      Thank you for calarifying this. I have spent a significant amount of time trying to come up with something better than O(n) . I have just changed the boilerplate code and have all test cases passing. My solution is O(n)

    • + 0 comments

      I can confirm that boilerplate in Java 8 is doing tests failling due to timeout. You can easily test it by submitting the code (without implementing the freqQuery method). Test 9 to 14 will fail due to timeout instead of wrong answer, like the others.

      Thanks for the new boilerplate code!

    • + 0 comments

      Also, if someone still struggles with tests 12 and 13 due to timeout, use: List<Integer> result = new ArrayList<>(queries.size()); instead of List<Integer> result = new LinkedList<>();.

      Of course we potentially allocate unnecessary memory in ArrayList (if queries contains other operations than operation 3), but this tric is to pass those tests. I.e. LinkedList will be better only with small amount of operations 3.

    • + 0 comments

      Thanks a bunch! I was lossing my mind trying to think of a sub linear solution. After first reading your comment I ran a submission with all my code commented out, still went over time.

    • + 0 comments

      how do we call the elements from the listqueries

    • + 0 comments

      I am getting an error in last part of the boiler plate that you have written from bufferedWriter.write thank you

    • + 1 comment

      If the frequency is greater than 10^5 then add 0 to the List, b/c the frequency of any number cannot exceed the value of 10^5.

      Just Add the below condition, all the test cases will pass.

      if(value > 100000) result.add(0);

      else
      result.add(arr[value] > 0 ? 1 : 0);

      • + 0 comments

        Works perfectly for 11th case. Thank you!

    • + 0 comments

      Hi, I have made the adjustment suggested but it still won't pass test case 11. Any suggestions?

      static List<Integer> freqQuery(List<int[]> queries) {
          HashMap<Integer, Integer> counter = new HashMap<>();
          Integer command, value;
          ArrayList<Integer> output = new ArrayList<>();
          for (Integer i = 0; i <  queries.size(); i++) {
              command = queries.get(i)[0];
              value = queries.get(i)[1];
      
              Integer occurencesOfValue = counter.get(value);
              switch(command) {
                  case 1:
                      if (occurencesOfValue != null) {
                          counter.put(value, occurencesOfValue + 1);
                      } else {
                          counter.put(value, 1);
                      }
                      break;
                  case 2:
                      if (occurencesOfValue != null) {
                          if (occurencesOfValue == 1) {
                              counter.remove(value);
                          } else {
                              counter.put(value, occurencesOfValue - 1);
                          }
                      } 
                      break;
                  case 3:
                      if(counter.values().contains(value)) {
                          output.add(1);
                      } else {
                          output.add(0);
                      }
              }
          }
          return output;   
      }
      
    • + 0 comments

      Changing the boilerplate is unnecessary to avoid a timeout.

      Rather you can keep two hashmaps where the keyset of one is the set of integers in the array and the keyset of the other is the set of frequencies with which integers appear in the array.

      This allows you to perform all operations using keys rather than values, which is efficient enough that it doesn't timeout.

    • + 0 comments

      I don't know if the timeout restrictions have changed but my O(n) solution is passing without changing the boilerplate pretty quickly.

      static List<Integer> freqQuery(List<List<Integer>> queries) {
          // one hash (numCtr) with key=>number, value=>occurances
          Map<Integer, Integer> numCtr = new HashMap<>();
          // one hash (occurancesCtr) with key=>occurances, value=>occurances of occurances
          Map<Integer, Integer> occurancesCtr = new HashMap<>();
      
          List<Integer> output = new LinkedList<>();
      
          for(List<Integer> query : queries) {
              final int currentCount = numCtr.getOrDefault(query.get(1), 0);
              if (query.get(0) == 1) {
                  increaseByOne(numCtr, query.get(1));
                  decreaseByOne(occurancesCtr, currentCount);
                  increaseByOne(occurancesCtr, currentCount+1);
              } else if (query.get(0) == 2) {
                  if (currentCount > 0) {
                      decreaseByOne(numCtr, query.get(1));
                      decreaseByOne(occurancesCtr, currentCount);
                      if(currentCount-1 > 0) {
                          Solution.increaseByOne(occurancesCtr, currentCount-1);
                      }
                  }
              } else if (query.get(0) == 3) {
                  if (occurancesCtr.getOrDefault(query.get(1), 0) > 0) {
                      output.add(1);
                  } else {
                      output.add(0);
                  }
              }
          }
      
      static void decreaseByOne(Map<Integer, Integer> map, int key) {
          if(map.containsKey(key)) {
              map.put(key, map.get(key)-1);
          }
      }
      
      static void increaseByOne(Map<Integer, Integer> map, int key) {
          map.put(key, map.getOrDefault(key, 0)+1);
      }
          return output;
      
      }