# Tweet Counts Per Frequency
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/tweet-counts-per-frequency)
Canonical: https://scaleengineer.com/dsa/problems/tweet-counts-per-frequency
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, Ordered Set
**Companies:** [X](https://scaleengineer.com/companies/x)
---
## Problem
A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be partitioned into smaller **time chunks** based on a certain frequency (every **minute**, **hour**, or **day**).

For example, the period `[10, 10000]` (in **seconds**) would be partitioned into the following **time chunks** with these frequencies:

* Every **minute** (60-second chunks): `[10,69]`, `[70,129]`, `[130,189]`, `...`, `[9970,10000]`
* Every **hour** (3600-second chunks): `[10,3609]`, `[3610,7209]`, `[7210,10000]`
* Every **day** (86400-second chunks): `[10,10000]`

Notice that the last chunk may be shorter than the specified frequency's chunk size and will always end with the end time of the period (`10000` in the above example).

Design and implement an API to help the company with their analysis.

Implement the `TweetCounts` class:

* `TweetCounts()` Initializes the `TweetCounts` object.
* `void recordTweet(String tweetName, int time)` Stores the `tweetName` at the recorded `time` (in **seconds**).
* `List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime)` Returns a list of integers representing the number of tweets with `tweetName` in each **time chunk** for the given period of time `[startTime, endTime]` (in **seconds**) and frequency `freq`.  
  * `freq` is one of `"minute"`, `"hour"`, or `"day"` representing a frequency of every **minute**, **hour**, or **day** respectively.

**Example:**

**Input**
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

**Output**
[null,null,null,null,[2],[2,1],null,[4]]

**Explanation**
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);                              // New tweet "tweet3" at time 0
tweetCounts.recordTweet("tweet3", 60);                             // New tweet "tweet3" at time 60
tweetCounts.recordTweet("tweet3", 10);                             // New tweet "tweet3" at time 10
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]; chunk [0,59] had 2 tweets
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2,1]; chunk [0,59] had 2 tweets, chunk [60,60] had 1 tweet
tweetCounts.recordTweet("tweet3", 120);                            // New tweet "tweet3" at time 120
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]; chunk [0,210] had 4 tweets

**Constraints:**

* `0 <= time, startTime, endTime <= 109`
* `0 <= endTime - startTime <= 104`
* There will be at most `104` calls **in total** to `recordTweet` and `getTweetCountsPerFrequency`.

# Approaches
## Optimized Query with Sorted List (Sort on Demand)
This approach attempts to optimize the `getTweetCountsPerFrequency` method by avoiding a full scan of all timestamps. It maintains a list of timestamps for each tweet, similar to the brute-force method. However, to speed up queries, it sorts the list of timestamps on demand and then uses binary search to quickly find the start of the relevant time range `[startTime, endTime]`. After finding the starting point, it only iterates through the tweets within the specified range.
**Time:** - `recordTweet`: `O(1)` amortized time.
- `getTweetCountsPerFrequency`: `O(N log N + M)` in the worst case for a single call if a sort is needed, where `N` is the number of tweets for the given name and `M` is the number of tweets in the query range. If the list is already sorted, it's `O(log N + M)`. The overall performance across many calls can be poor due to repeated sorting. · **Space:** O(T), where T is the total number of tweets recorded. We need to store every timestamp.
**Pros:** `recordTweet` operation is very fast, taking `O(1)` time.; If `getTweetCountsPerFrequency` is called many times for the same set of tweets and the query ranges are small, subsequent calls after the initial sort are fast (`O(log N + M)`).
**Cons:** The sorting step (`O(N log N)`) can be a significant performance bottleneck, especially if `getTweetCountsPerFrequency` is called frequently after new tweets are recorded.; The overall performance is unpredictable and highly dependent on the sequence of calls. In many common scenarios (like interleaved `recordTweet` and `get` calls), it performs worse than the simpler brute-force approach.; Standard `Collections.binarySearch` may not find the first occurrence of a timestamp if there are duplicates, requiring extra logic to find the true starting index.
### Explanation
The core idea is to trade a cheap `recordTweet` operation for a potentially expensive, but more targeted, `getTweetCountsPerFrequency` operation. We store timestamps in a `List` and use a separate flag to track whether the list is sorted.

When `recordTweet` is called, we simply append the new time to the list and set the `isSorted` flag for that `tweetName` to `false`. This makes recording a tweet an `O(1)` operation.

When `getTweetCountsPerFrequency` is called, we first check the `isSorted` flag. If it's `false`, we sort the entire list of timestamps, which takes `O(N log N)` time, where `N` is the number of tweets for that name. Once the list is sorted, we can efficiently find the first tweet in the `[startTime, endTime]` range using binary search in `O(log N)` time. From there, we iterate only through the relevant tweets until we pass `endTime`. This part of the process is efficient if the number of tweets in the range (`M`) is much smaller than the total number of tweets (`N`).

```java
class TweetCounts {
    private Map<String, List<Integer>> tweets;
    private Map<String, Boolean> isSorted;

    public TweetCounts() {
        tweets = new HashMap<>();
        isSorted = new HashMap<>();
    }

    public void recordTweet(String tweetName, int time) {
        tweets.computeIfAbsent(tweetName, k -> new ArrayList<>()).add(time);
        isSorted.put(tweetName, false);
    }

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

        if (timestamps == null || timestamps.isEmpty()) {
            return new ArrayList<>(Collections.nCopies(numChunks, 0));
        }

        if (!isSorted.getOrDefault(tweetName, false)) {
            Collections.sort(timestamps);
            isSorted.put(tweetName, true);
        }
        
        int startIdx = Collections.binarySearch(timestamps, startTime);
        if (startIdx < 0) {
            startIdx = -startIdx - 1;
        } else {
            // Handle duplicates, find the first occurrence
            while (startIdx > 0 && timestamps.get(startIdx - 1).equals(startTime)) {
                startIdx--;
            }
        }

        for (int i = startIdx; i < timestamps.size(); i++) {
            int time = timestamps.get(i);
            if (time > endTime) {
                break;
            }
            int index = (time - startTime) / delta;
            counts[index]++;
        }

        List<Integer> result = new ArrayList<>(numChunks);
        for (int count : counts) {
            result.add(count);
        }
        return result;
    }
}
```
### Algorithm
- **Data Structure**: Use a `HashMap<String, List<Integer>>` to store tweet timestamps for each `tweetName`, and a `HashMap<String, Boolean>` to track if a list is sorted.
- **`recordTweet(tweetName, time)`**:
  - Add the `time` to the list corresponding to `tweetName`.
  - Mark this list as unsorted.
- **`getTweetCountsPerFrequency(freq, tweetName, startTime, endTime)`**:
  - Retrieve the list of timestamps for `tweetName`.
  - If the list is marked as unsorted, sort it using `Collections.sort()` and mark it as sorted.
  - Determine the time chunk `delta` based on `freq`.
  - Calculate the number of chunks and initialize a result array/list with zeros.
  - Use binary search (e.g., `Collections.binarySearch`) to find the index of the first timestamp that is greater than or equal to `startTime`.
  - Iterate through the timestamps from this starting index.
  - For each timestamp up to `endTime`, calculate which time chunk it belongs to and increment the corresponding counter.
  - Stop iterating when a timestamp exceeds `endTime`.
  - Return the list of counts.

## Brute-Force with Unsorted List
This is a straightforward, brute-force approach. It uses a `HashMap` to associate each `tweetName` with an unsorted `List` of its recorded timestamps. When a tweet is recorded, its timestamp is simply appended to the corresponding list. When counts are requested, the method iterates through the entire list of timestamps for the given `tweetName`, checks if each timestamp falls within the `[startTime, endTime]` range, and if so, increments the count for the appropriate time chunk.
**Time:** - `recordTweet`: `O(1)` amortized time.
- `getTweetCountsPerFrequency`: `O(N)`, where `N` is the number of tweets recorded for the given `tweetName`. This is because we must iterate through all of its timestamps. · **Space:** O(T), where T is the total number of tweets recorded across all names. Each timestamp is stored.
**Pros:** Simple to understand and implement.; The `recordTweet` operation is very fast (`O(1)` amortized time).; Performance is predictable, unlike approaches that involve conditional sorting.
**Cons:** `getTweetCountsPerFrequency` can be inefficient if a `tweetName` has a very large number of recorded tweets, as it must iterate through all of them, even those outside the query time range.
### Explanation
The implementation relies on a `HashMap` to store data, mapping tweet names to lists of integer timestamps. The `recordTweet` method is highly efficient, as adding an element to the end of an `ArrayList` is an amortized constant time operation.

The `getTweetCountsPerFrequency` method contains the main logic. First, it translates the frequency string (`"minute"`, `"hour"`, `"day"`) into a chunk size in seconds. It then creates an integer array, `counts`, to hold the tweet counts for each chunk. The size of this array is determined by the total time span `(endTime - startTime)` and the chunk size. The method then performs a linear scan through all timestamps associated with the `tweetName`. For each timestamp, it verifies if it's within the query bounds. If it is, it computes the index of the chunk the tweet belongs to and increments the counter at that index. Finally, it converts the `counts` array into a `List` and returns it.

```java
class TweetCounts {
    private Map<String, List<Integer>> tweets;

    public TweetCounts() {
        tweets = new HashMap<>();
    }

    public void recordTweet(String tweetName, int time) {
        tweets.computeIfAbsent(tweetName, k -> new ArrayList<>()).add(time);
    }

    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        int delta;
        if (freq.equals("minute")) {
            delta = 60;
        } else if (freq.equals("hour")) {
            delta = 3600;
        } else { // "day"
            delta = 86400;
        }

        int numChunks = (endTime - startTime) / delta + 1;
        int[] counts = new int[numChunks];

        List<Integer> timestamps = tweets.get(tweetName);
        if (timestamps != null) {
            for (int time : timestamps) {
                if (time >= startTime && time <= endTime) {
                    int index = (time - startTime) / delta;
                    counts[index]++;
                }
            }
        }

        List<Integer> result = new ArrayList<>(numChunks);
        for (int count : counts) {
            result.add(count);
        }
        return result;
    }
}
```
### Algorithm
- **Data Structure**: Use a `HashMap<String, List<Integer>>` where the key is the `tweetName` and the value is a list of all timestamps for that tweet. The list is not kept in any specific order.
- **`recordTweet(tweetName, time)`**:
  - Retrieve the list for the given `tweetName`. If it doesn't exist, create a new one.
  - Add the `time` to the list.
- **`getTweetCountsPerFrequency(freq, tweetName, startTime, endTime)`**:
  - Determine the time chunk `delta` (60 for minute, 3600 for hour, 86400 for day).
  - Calculate the number of chunks required for the interval `[startTime, endTime]` and initialize a result array (or list) of that size with all zeros.
  - Retrieve the list of timestamps for the given `tweetName`.
  - Iterate through every timestamp in the list.
  - For each timestamp, check if it falls within the `[startTime, endTime]` range.
  - If it does, calculate which time chunk it belongs to using the formula `index = (timestamp - startTime) / delta`.
  - Increment the count for that chunk in the result array.
  - After checking all timestamps, return the result array as a list.

## Efficient Approach with TreeMap
This is the most efficient and robust approach. It leverages a `TreeMap`, which is a sorted map implementation based on a Red-Black Tree. By storing timestamps as keys in a `TreeMap`, we get two key benefits: timestamps are automatically kept in sorted order, and we can efficiently query for a range of timestamps.

`recordTweet` involves an `O(log N)` insertion into the `TreeMap`. `getTweetCountsPerFrequency` becomes highly efficient because `TreeMap` provides a `subMap` method to get a view of the map for the range `[startTime, endTime]` in `O(log N)` time. We then only need to iterate over the `M` tweets that are actually in this range.
**Time:** - `recordTweet`: `O(log N)`, where `N` is the number of distinct timestamps for the `tweetName`.
- `getTweetCountsPerFrequency`: `O(log N + M)`, where `N` is the number of distinct timestamps for the `tweetName` and `M` is the number of distinct timestamps within the `[startTime, endTime]` range. · **Space:** O(D), where D is the total number of *distinct* timestamps recorded. If many tweets occur at the same time, this can be more space-efficient than storing every single timestamp.
**Pros:** Efficient for both `recordTweet` and `getTweetCountsPerFrequency` operations.; Scales well as the number of tweets increases due to logarithmic time complexity.; Best approach for handling queries over small time ranges within a large dataset of tweets.
**Cons:** Slightly more complex to implement compared to list-based approaches.; `TreeMap` has a higher memory overhead per entry than an `ArrayList`.
### Explanation
This approach uses a `HashMap` to map `tweetName` to a `TreeMap`. The `TreeMap` is the key to efficiency here. It stores timestamps as its keys and the number of tweets at that specific timestamp as its values. Since `TreeMap` is a balanced binary search tree, it maintains its keys in sorted order.

When `recordTweet` is called, we find the correct `TreeMap` for the `tweetName` and update the count for the given `time`. This `put` or `merge` operation on a `TreeMap` takes `O(log N)` time, where `N` is the number of distinct timestamps for that tweet name.

When `getTweetCountsPerFrequency` is called, we first get the `TreeMap` of timestamps. The crucial step is calling `timestamps.subMap(startTime, true, endTime, true)`. This method returns a view of the portion of the map whose keys are in the specified range, without copying any data. The operation itself is fast (`O(log N)`). We then iterate only over this smaller sub-map. For each timestamp and its associated count in the sub-map, we calculate its chunk index and update our result array. This avoids scanning irrelevant timestamps, making the query very fast.

```java
class TweetCounts {
    private Map<String, TreeMap<Integer, Integer>> tweets;

    public TweetCounts() {
        tweets = new HashMap<>();
    }

    public void recordTweet(String tweetName, int time) {
        tweets.computeIfAbsent(tweetName, k -> new TreeMap<>())
              .merge(time, 1, Integer::sum);
    }

    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        int delta;
        if (freq.equals("minute")) {
            delta = 60;
        } else if (freq.equals("hour")) {
            delta = 3600;
        } else { // "day"
            delta = 86400;
        }

        int numChunks = (endTime - startTime) / delta + 1;
        int[] counts = new int[numChunks];

        TreeMap<Integer, Integer> timestamps = tweets.get(tweetName);
        if (timestamps != null) {
            Map<Integer, Integer> subMap = timestamps.subMap(startTime, true, endTime, true);
            for (Map.Entry<Integer, Integer> entry : subMap.entrySet()) {
                int time = entry.getKey();
                int count = entry.getValue();
                int index = (time - startTime) / delta;
                counts[index] += count;
            }
        }

        List<Integer> result = new ArrayList<>(numChunks);
        for (int count : counts) {
            result.add(count);
        }
        return result;
    }
}
```
### Algorithm
- **Data Structure**: Use a `HashMap<String, TreeMap<Integer, Integer>>`. The outer `HashMap` maps a `tweetName` to a `TreeMap`. The `TreeMap` stores timestamps as keys and the count of tweets at that exact time as values. `TreeMap` automatically keeps the keys (timestamps) sorted.
- **`recordTweet(tweetName, time)`**:
  - Get the `TreeMap` for the `tweetName`.
  - Insert or update the entry for the given `time`, incrementing its count. This operation is efficient due to the balanced binary search tree structure of the `TreeMap`.
- **`getTweetCountsPerFrequency(freq, String tweetName, int startTime, int endTime)`**:
  - Get the `delta` and initialize the `counts` array as in other approaches.
  - Retrieve the `TreeMap` for the `tweetName`.
  - Use the `TreeMap.subMap(startTime, true, endTime, true)` method to get a view of only the entries within the desired time range. This is a very efficient operation.
  - Iterate through the entries in this sub-map.
  - For each entry (timestamp and its count), calculate the chunk index and add the count to the `counts` array.
  - Return the list of counts.

# Solutions
### Java

```java
class TweetCounts { private Map < String , TreeMap < Integer , Integer >> data = new HashMap <>(); public TweetCounts () { } public void recordTweet ( String tweetName , int time ) { data . putIfAbsent ( tweetName , new TreeMap <>()); var tm = data . get ( tweetName ); tm . put ( time , tm . getOrDefault ( time , 0 ) + 1 ); } public List < Integer > getTweetCountsPerFrequency ( String freq , String tweetName , int startTime , int endTime ) { int f = 60 ; if ( "hour" . equals ( freq )) { f = 3600 ; } else if ( "day" . equals ( freq )) { f = 86400 ; } var tm = data . get ( tweetName ); List < Integer > ans = new ArrayList <>(); for ( int i = startTime ; i <= endTime ; i += f ) { int s = 0 ; int end = Math . min ( i + f , endTime + 1 ); for ( int v : tm . subMap ( i , end ). values ()) { s += v ; } ans . add ( s ); } return ans ; } } /** * Your TweetCounts object will be instantiated and called as such: * TweetCounts obj = new TweetCounts(); * obj.recordTweet(tweetName,time); * List<Integer> param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime); */
```

### CPP

```cpp
class TweetCounts { public: TweetCounts () { } void recordTweet ( string tweetName , int time ) { data [ tweetName ]. insert ( time ); } vector < int > getTweetCountsPerFrequency ( string freq , string tweetName , int startTime , int endTime ) { int f = 60 ; if ( freq == "hour" ) f = 3600 ; else if ( freq == "day" ) f = 86400 ; vector < int > ans (( endTime - startTime ) / f + 1 ); auto l = data [ tweetName ]. lower_bound ( startTime ); auto r = data [ tweetName ]. upper_bound ( endTime ); for (; l != r ; ++ l ) { ++ ans [( * l - startTime ) / f ]; } return ans ; } private: unordered_map < string , multiset < int >> data ; }; /** * Your TweetCounts object will be instantiated and called as such: * TweetCounts* obj = new TweetCounts(); * obj->recordTweet(tweetName,time); * vector<int> param_2 = obj->getTweetCountsPerFrequency(freq,tweetName,startTime,endTime); */
```

### Python

```python
from sortedcontainers import SortedList class TweetCounts : def __init__ ( self ): self . d = { "minute" : 60 , "hour" : 3600 , "day" : 86400 } self . data = defaultdict ( SortedList ) def recordTweet ( self , tweetName : str , time : int ) -> None : self . data [ tweetName ]. add ( time ) def getTweetCountsPerFrequency ( self , freq : str , tweetName : str , startTime : int , endTime : int ) -> List [ int ]: f = self . d [ freq ] tweets = self . data [ tweetName ] t = startTime ans = [] while t <= endTime : l = tweets . bisect_left ( t ) r = tweets . bisect_left ( min ( t + f , endTime + 1 )) ans . append ( r - l ) t += f return ans # Your TweetCounts object will be instantiated and called as such: # obj = TweetCounts() # obj.recordTweet(tweetName,time) # param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime)
```