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

## Advertisement

## 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

*. You can call this array as*

**the number of elements in your data structure with that frequency**`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.*

**2**People found this is helpful