Frequency Queries (Hackerrank)

Question

This is the problem:

You are given queries. Each query is of the form two integers described below:

• 1 x: Insert x in your data structure.
• 2 y: Delete one occurrence of y from your data structure, if present.
• 3 z: Check if any integer is present whose frequency is exactly z. If yes, print 1 else 0.

The queries are given in the form of a 2-D array queries of size q where queries[i][0] contains the operation, and queries[i][1] contains the data element. For example, you are given array queries = [[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]]
…

Return an array with the output=[0,1].

I am getting a "Time Limit Exceeded" error on only one Test Case. How can I optimize and improve my code?

Here is my code in JavaScript:

function freqQuery(queries) {
    const resultArray = [] 
    const frequencyArray = [];
  for(let i=0 ; i<queries.length ; i++){ 
      const arr = queries[i]
      if(arr[0]== 1){
          frequencyArray[arr[1]] = (frequencyArray[arr[1]] || 0) + 1
      }
      else if(arr[0] == 2){
          if(frequencyArray[arr[1]]){
              frequencyArray[arr[1]] = frequencyArray[arr[1]] -1;
          }
      }
      else if(arr[0] == 3){
          resultArray.push(frequencyArray.includes(arr[1]) ? 1 : 0 );
      }
  }
  return resultArray;
}

Answer 1

There's a few general code hygiene things that I'll look at first, and then I'll comment on the algorithm design.

First, const should mean constant. I know that in Javascript you don't get in trouble for changing the contents of a const array but it's still confusing to use it with a variable whose job is to change. const arr I like but const resultArray I don't.

Second, although I appreciate that these practice challenges don't always give a huge amount of context to inform your purpose, it's important to think about variable names. In particular, arr is a very vague name at the best of times, and a moderately misinforming one in this context. I'd go for something like "instruction".

Third, three if statements checking the same expression for fixed values just screams "use a switch statement". Efficiency questions notwithstanding, switch will immediately clue anyone reading the code into there being one value to check against several options. (Whereas with long else if chains we have to focus on each condition because they could be different)

Fourth, avoid this little trick: if(frequencyArray[arr[1]]). Yes, Javascript will silently do all sorts of funky conversions, and this old implicit cast bool seems tame in comparison. But those conversions are hard to read and bug prone. If you want to check first whether it exists and then whether it is positive, check first whether it exists and then whether it is positive.

Fifth, tiny style thing, but consistency is often more important than what decision you come to. So with Javascript, you can leave off semicolons, or you can add them in. Either works. Some people insist one way or the other, and I won't do that. But if you do use them, use them. As is, 4 statements end with semicolons and 3 end without semicolons, with nothing to tell them apart.

As to the algorithm efficiency, you're making good use of the fact that Javascript "arrays" are dictionaries, so you can directly refer to frequencyArray[arr[1]] without having to worry about whether arr[1] being enormous. With that direct value lookup, your cases for 1 and 2 both consist of very quick operations. Case 3 is the one that will take time, even though it looks just as simple as the others. It's the includes function that's killing you. While the other cases just check one value in the array, includes has to check every single value. What you'll want to do is remember your frequency count as you go, taking a bit of extra time in your 1 and 2 cases to update an additional array/dictionary, so that in your 3 case you can just look up that already calculated value and output it.

Answer 2

Josiah's answer covers most stuff pretty well. The only additional suggestion I have is an alternative to a switch statement: a lookup table of actions.

Something like:

const query_types = {
  1: (x)=>{
      frequencyArray[arr[1]] = (frequencyArray[arr[1]] || 0) + 1;
    },
  2: (y)=>{
      ...
    },
  3: (z)=>{
      ...
    }
};

for(let i=0 ; i<queries.length ; i++){ 
  query_types[queries[i][0]](queries[i][1]);
}
```