Hacker Rank Frequency Queries

Question

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

Why not make a list of the operations inside your main loop, and estimate the performance of each? Does one look a lot slower than the others? — tgdavies, Feb 23 '21 at 03:18
Can you link to the original Hack Rank question? The one I found it doesn't look like this would work at all. — NovaPenguin, Feb 23 '21 at 03:26
The `time complexity` of `boolean containsValue(Object value)` is `O(n)`. *You can make it more efficient if you make that check in `case 3` in `O(1)`.* — AKSingh, Feb 23 '21 at 12:58
@Grzegorz this question would be even worse fit over there than here. Please abstain of recommending sites you're not familiar with. See **[What goes on Software Engineering (previously known as Programmers)? A guide for Stack Overflow](https://softwareengineering.meta.stackexchange.com/a/7183/31260)** — gnat, Feb 24 '21 at 21:55

score 2 · Accepted Answer · answered Feb 23 '21 at 19:46

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.

Hacker Rank Frequency Queries

1 Answers1