Complexity Analysis:

• Time Complexity: $O(T)$ per query, where $T$ is the total number of tweets ever recorded across all users.
• Why it fails: While this might pass smaller test cases, it is inefficient. As the platform grows, iterating through millions of tweets for other users just to count tweets for one specific user wastes significant processing power. It fails to leverage the fact that queries are always specific to a single tweetName.

Core Insight for Tweet Counts Per Frequency

The core insight for an optimal solution is to organize data primarily by tweetName. By using a Hash Map (or Dictionary) where the key is the tweet name and the value is a list of timestamps, we isolate the data. A query for "tweet3" never needs to touch the data for "tweet1".

The second insight is the mathematical transformation required to map a timestamp to a specific "bucket" in the result list.

Since we are asked for chunks of time relative to startTime, the index of a tweet occurring at time in the result array can be calculated deterministically:

$\text{index} = \frac{\text{time} - \text{startTime}}{\text{interval}}$

Where interval is 60, 3600, or 86400 seconds. This invariant ensures that any tweet falling within the first chunk (e.g., [startTime, startTime + 59]) maps to index 0, the next chunk to index 1, and so on.

Visual Description: Imagine a timeline representing the query range [startTime, endTime]. The algorithm effectively overlays a grid on top of this timeline. The grid lines are spaced apart by the frequency interval (e.g., every 60 seconds). When we retrieve the list of timestamps for a user, we drop each timestamp onto this grid. The formula (time - startTime) / interval tells us exactly which grid cell (array index) the timestamp lands in.

Execution Flow

Let's trace the execution for getTweetCountsPerFrequency("minute", "tweet3", 0, 60) assuming tweet3 has timestamps [0, 10, 60].

1. Identify Interval: The frequency is "minute", so interval = 60.
2. Initialize Buckets:
   • The total duration is 60 - 0 = 60.
   • The number of buckets needed is (60 / 60) + 1 = 2.
   • Result list initialized to [0, 0].
3. Process Timestamp 0:
   • Is 0 in [0, 60]? Yes.
   • Index calculation: (0 - 0) / 60 = 0.
   • Result becomes [1, 0].
4. Process Timestamp 10:
   • Is 10 in [0, 60]? Yes.
   • Index calculation: (10 - 0) / 60 = 0.
   • Result becomes [2, 0].
5. Process Timestamp 60:
   • Is 60 in [0, 60]? Yes.
   • Index calculation: (60 - 0) / 60 = 1.
   • Result becomes [2, 1].
6. Return: The final list [2, 1] is returned.

Proof of Correctness

The correctness relies on the bucketing formula and the filtering logic.

1. Filtering: We strictly check startTime <= t <= endTime. This ensures no tweets outside the requested period affect the counts.
2. Bucketing: The integer division (t - startTime) / delta partitions the continuous timeline into discrete equivalence classes.
   • For delta = 60, any t in [startTime, startTime + 59] yields 0.
   • Any t in [startTime + 60, startTime + 119] yields 1. This mathematically guarantees that tweets are aggregated into the correct time chunks as defined by the problem statement.

Reference Implementation

C++ Solution for LeetCode 1348

cpp
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class TweetCounts {
private:
    // Map tweetName to a list of timestamps
    unordered_map<string, vector<int>> tweetMap;

public:
    TweetCounts() {
        // Constructor needed for initialization, map handles itself
    }
    
    void recordTweet(string tweetName, int time) {
        tweetMap[tweetName].push_back(time);
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int interval = 0;
        if (freq == "minute") interval = 60;
        else if (freq == "hour") interval = 3600;
        else interval = 86400; // day
        
        // Calculate number of buckets needed
        // The range is inclusive [startTime, endTime], so duration is endTime - startTime + 1?
        // Actually, the problem defines chunks starting from startTime.
        // The last chunk ends at endTime.
        // Size is (endTime - startTime) / interval + 1
        int size = (endTime - startTime) / interval + 1;
        vector<int> result(size, 0);
        
        // Retrieve tweets for this user
        vector<int>& tweets = tweetMap[tweetName];
        
        // Sorting allows us to process efficiently or use binary search, 
        // but given constraints (10^4 ops total), simple iteration is valid and robust.
        // We iterate all tweets for the user and filter those in range.
        for (int t : tweets) {
            if (t >= startTime && t <= endTime) {
                int bucketIndex = (t - startTime) / interval;
                if (bucketIndex >= 0 && bucketIndex < size) {
                    result[bucketIndex]++;
                }
            }
        }
        
        return result;
    }
};

Java Solution for LeetCode 1348

java
import java.util.*;

class TweetCounts {
    // Map tweetName to a list of timestamps
    private Map<String, List<Integer>> tweetMap;

    public TweetCounts() {
        tweetMap = new HashMap<>();
    }
    
    public void recordTweet(String tweetName, int time) {
        tweetMap.putIfAbsent(tweetName, new ArrayList<>());
        tweetMap.get(tweetName).add(time);
    }
    
    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        int interval = 60; // Default minute
        if (freq.equals("hour")) {
            interval = 3600;
        } else if (freq.equals("day")) {
            interval = 86400;
        }
        
        // Calculate bucket count
        int bucketCount = (endTime - startTime) / interval + 1;
        int[] buckets = new int[bucketCount];
        
        List<Integer> times = tweetMap.get(tweetName);
        if (times != null) {
            // Iterate through all stored times for this user
            for (int t : times) {
                if (t >= startTime && t <= endTime) {
                    int index = (t - startTime) / interval;
                    buckets[index]++;
                }
            }
        }
        
        // Convert array to List<Integer>
        List<Integer> result = new ArrayList<>();
        for (int count : buckets) {
            result.add(count);
        }
        return result;
    }
}

Python Solution for LeetCode 1348

python
from collections import defaultdict
from typing import List

class TweetCounts:

    def __init__(self):
        # Dictionary mapping tweetName to a list of timestamps
        self.tweets = defaultdict(list)

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

    def getTweetCountsPerFrequency(self, freq: str, tweetName: str, startTime: int, endTime: int) -> List[int]:
        if freq == "minute":
            interval = 60
        elif freq == "hour":
            interval = 3600
        else: # day
            interval = 86400
            
        # Determine the number of buckets
        # Range is [startTime, endTime], inclusive
        num_buckets = (endTime - startTime) // interval + 1
        result = [0] * num_buckets
        
        # Retrieve timestamps for the user
        user_tweets = self.tweets[tweetName]
        
        # Iterate and bucket
        # Note: Sorting user_tweets and using binary search (bisect) 
        # is an optimization, but linear scan passes comfortably.
        for t in user_tweets:
            if startTime <= t <= endTime:
                idx = (t - startTime) // interval
                result[idx] += 1
                
        return result