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

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

    • adekoya + 0 comments

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

    • avinash_mv + 0 comments

      Ultimate :)

    • chrislucas + 0 comments

      Nice solution.

    • yangls + 1 comment

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

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

    • amitava_basu + 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;
}
      • manan_shah77 + 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.

    • tarunaggarwal437 + 0 comments

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

    • fromtheast1 + 5 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
      • salas__ + 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!

      • jayjunkyu + 0 comments
        [deleted]
      • jayjunkyu + 0 comments
        [deleted]
      • qayum_khan_usa + 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 = defaultdict(int) ; f = defaultdict(set)

    for (c,v) in queries:
        if c==3 : yield int( len(f[v])>0 ) ; continue

        f[d[v]].discard(v)
        if c==1 : d[v] += 1
        elif d[v]>0 : d[v] -= 1
        f[d[v]].add(v)
      • richeshchouksey + 0 comments

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

    • durgapramodh10d1 + 0 comments

      awesome