Leetcode: Frequency Tracker

Problem: https://leetcode.com/contest/weekly-contest-344/problems/frequency-tracker/

Initially I thought a dictionary will suffice, but the brute-force solution got us a TLE, because hasFrequency could be run at most 20000 times, and every time we have to run through the dictionary to check the frequencies:

public boolean hasFrequency(int frequency) { // TLE
  for(Map.Entry<Integer, Integer> entry: f.entrySet()) {
      int occurrence = entry.getValue();
      if (occurrence == frequency ) return true;
  }
  return false;
}

Let’s trade space for time, because add and delete are already performing well: O(1). Can we add a new data structure to reduce the complexity of hasFrequency, let’s just a dumb array and make its length a little bigger than 5–6 digits. We realize that we can already prepare the data in add and deleteOne methods.

Map<Integer, Integer> map;
int[] f = new int[1000000];
public FrequencyTracker() {
  map = new HashMap<>();
}

public void add(int number) {
  if (map.containsKey(number)) {
      int occurence = map.get(number);
      map.replace(number, occurence + 1);
      f[occurence]--;
      f[occurence+1]++;
  } else {
      map.put(number, 1);
      f[1]++;
  }
}
public void deleteOne(int number) {
  if (map.containsKey(number)) {
      if ( map.get(number) > 1) {
          int occurence = map.get(number);
          map.replace(number, occurence - 1);
          f[occurence]--;
          f[occurence-1]++;
      } else {
          map.remove(number);
          f[1]--;
      }
  }
}
public boolean hasFrequency(int frequency) { // O(1)
  return f[frequency] > 0;
}