Hacker Rank Frequency Queries [closed]

I am doing the Hacker Rank Frequency Queries question and all my test cases pass but one for Time limit exceeded. What can I do to make my program more efficient.

static List<Integer> freqQuery(List<List<Integer>> queries) {
    List<Integer> freqCount = new ArrayList();
    HashMap<Integer, Integer> data = new HashMap<>();
    
    for(List q : queries){
        int op = (Integer)q.get(0);
        int num = (Integer)q.get(1);
        
        switch (op){
            case 1:
                if(data.get(num) == null){
                    //Add new value to hashmap
                    data.put(num, 1);
                }else{
                    data.put(num, data.get(num) + 1);
                }
            break;
            case 2:
                if(data.get(num) != null){
                    if(data.get(num) == 0){
                        //data.remove(num);
                    }else{
                       data.put(num, data.get(num) - 1); 
                    }
                }
            break;
            case 3:
                if(data.containsValue(num)){
                    freqCount.add(1);
                }else{
                    freqCount.add(0);
                }
            break;
        }

    }
    
    return freqCount;
}

Answer

The time complexity of boolean containsValue(Object value) of class HashMap<K,V> is O(n). If in case 3, you can do a constant time look up – O(1), your code will be quite efficient.

According to the constraints mentioned in the problem statement:

• Maximum number of queries:

  1 <= q <= 10^5

• Maximum possible value of x, y and z:

  1 <= x, y, z <= 10^9

In order to check if any integer is present in your data structure whose frequency is exactly z in O(1), you can use an simple array.

If there is an element e in your array at an index z, then it will denote that there are e elements in your data structure with frequency z. The index of your array denotes frequency and the value at that index denotes the number of elements in your data structure with that frequency. You can call this array as nestedFrequency since it stores the frequency of frequencies. The size of the array will be 100001. Since the maximum number of possible queries are 100000, there can be no element whose frequency is greater than 100000.

Pseudocode:

for i = 1 to queries.length
    int choice = queries[i][0]
    int number = queries[i][1]
    
    switch (choice)
        case 1:
            Add the number in hashMap and map it to a value of 0 if not already 
            present.

            //Obtain the previous frequency of that number in hashMap
            int oldFre = hashMap.get(number)
            
            //Update the nested frequency array
            nestedFrequency[oldFre]--
            nestedFrequency[oldFre+1]++

            //Update the frequency of that number in hashmap
            Increase the frequency of that number in hashMap 
        case 2:
            if there is a mapping present of the given number in hashMap
                //Obtain the previous frequency of that number in hashMap
                int oldFre = hashMap.get(number)

                //Update the nested frequency array
                nestedFrequency[oldFre]--
                if (oldFre-1 != 0) nestedFrequency[oldFre-1]++
                
                //Update the frequency of that number in hashmap
                if (oldFre-1 == 0) remove the mapping of that element in hashmap
                else decrease its old frequency
        case 3:
            if number < 100001 and nestedFrequncy[number] > 0
                print 1
            else 
                print 0

I hope I have helped you. Do comment for any further problems.