1348. Tweet Counts Per Frequency

• Time:
  • Constructor: $O(1)$
  • recordTweet(tweetName: str, time: int): $O(1)$ (C++/Java) | $O(\log |\texttt{times}|)$ (Python)
  • getTweetCountsPerFrequency(freq: str, tweetName: str, startTime: int, endTime: int): $O(n\log n)$, where $n = |\texttt{timeCount}|$ (C++/Java) | $O(\frac{\texttt{endTime} - \texttt{startTime}}{\texttt{chunkSize}} \cdot \log |\texttt{times}|)$
• Space: $O(|\texttt{recordTweet()}|)$

C++JavaPython

class TweetCounts {
 public:
  void recordTweet(string tweetName, int time) {
    ++tweetNameToTimeCount[tweetName][time];
  }

  vector<int> getTweetCountsPerFrequency(string freq, string tweetName,
                                         int startTime, int endTime) {
    const int chunkSize = freq == "minute" ? 60 : freq == "hour" ? 3600 : 86400;
    vector<int> counts((endTime - startTime) / chunkSize + 1);
    const map<int, int>& timeCount = tweetNameToTimeCount[tweetName];
    const auto lo = timeCount.lower_bound(startTime);
    const auto hi = timeCount.upper_bound(endTime);

    for (auto it = lo; it != hi; ++it) {
      const int index = (it->first - startTime) / chunkSize;
      counts[index] += it->second;
    }

    return counts;
  }

 private:
  unordered_map<string, map<int, int>> tweetNameToTimeCount;
};

class TweetCounts {
  public void recordTweet(String tweetName, int time) {
    tweetNameToTimeCount.putIfAbsent(tweetName, new TreeMap<>());
    tweetNameToTimeCount.get(tweetName).merge(time, 1, Integer::sum);
  }

  public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime,
                                                  int endTime) {
    final int chunkSize = freq.equals("minute") ? 60 : freq.equals("hour") ? 3600 : 86400;
    int[] counts = new int[(endTime - startTime) / chunkSize + 1];
    TreeMap<Integer, Integer> timeCount = tweetNameToTimeCount.get(tweetName);

    for (Map.Entry<Integer, Integer> entry : timeCount.subMap(startTime, endTime + 1).entrySet()) {
      final int index = (entry.getKey() - startTime) / chunkSize;
      counts[index] += entry.getValue();
    }

    return Arrays.stream(counts).boxed().collect(Collectors.toList());
  }

  private Map<String, TreeMap<Integer, Integer>> tweetNameToTimeCount = new HashMap<>();
}

from sortedcontainers import SortedList


class TweetCounts:
  def __init__(self):
    self.tweetNameToTimes = collections.defaultdict(SortedList)

  def recordTweet(self, tweetName: str, time: int) -> None:
    self.tweetNameToTimes[tweetName].add(time)

  def getTweetCountsPerFrequency(self, freq: str, tweetName: str,
                                 startTime: int, endTime: int) -> list[int]:
    counts = []
    times = self.tweetNameToTimes[tweetName]
    chunk = 60 if freq == 'minute' else 3600 if freq == 'hour' else 86400

    # I := startTime of each chunk
    for i in range(startTime, endTime + 1, chunk):
      j = min(i + chunk, endTime + 1)  # EndTime of each chunk
      counts.append(bisect_left(times, j) - bisect_left(times, i))

    return counts