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.
Loading...
  1. Frequency Queries
  2. Discussions

Frequency Queries

  • tuliobraga + 6 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 + 0 comments

      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;
}
    • tarunaggarwal437 + 0 comments

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