Hacker Rank Frequency Queries [closed]

Tags: algorithm, hashmap, java

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){
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)){
}else{
}
break;
}

}

return freqCount;
}

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]
int number = queries[i]

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.

Source: stackoverflow