python
# Pseudo-code for Brute Force
class HitCounter:
    def __init__(self):
        self.all_hits = []

    def hit(self, timestamp):
        self.all_hits.append(timestamp)

    def getHits(self, timestamp):
        count = 0
        limit = timestamp - 300
        # Iterate all history
        for t in self.all_hits:
            if t > limit:
                count += 1
        return count

Complexity Analysis:

• Time Complexity: hit is $O(1)$, but getHits is $O(N)$, where $N$ is the total number of hits recorded since the start.
• Space Complexity: $O(N)$ to store the history.

Why it fails: While this might pass small test cases, it is inefficient for high-throughput systems. If the system runs for a long time or receives millions of hits, the list grows indefinitely, causing memory issues. Even if we prune old hits, if a massive spike of hits occurs within a 5-minute window (e.g., 1 million hits at t=100), the getHits operation becomes linearly expensive relative to the number of hits in the window, potentially causing a Time Limit Exceeded (TLE) or high latency.

Core Insight for Design Hit Counter

The brute force approach fails because it treats every hit as a discrete, permanent entity. However, the problem imposes a rigid constraint: we only care about the last 300 seconds. This suggests a fixed-window approach.

Furthermore, multiple hits can occur at the exact same timestamp. Storing 1,000 identical timestamps (e.g., [100, 100, ..., 100]) is redundant. We can instead store a pair: {timestamp: 100, count: 1000}.

The Key Invariant: Since the window is fixed at 300 seconds, we can map any timestamp $t$ to an index in a fixed-size array using modulo arithmetic: index = t % 300.

This leads to a Circular Array (Bucket) design:

1. We maintain two arrays of size 300: times[] and hits[].
2. times[i] stores the specific timestamp associated with that bucket.
3. hits[i] stores the number of hits that occurred at that timestamp.
4. When a new hit comes in at timestamp, we look at index i = timestamp % 300.
   • If times[i] is strictly less than the current timestamp, the data in this bucket is stale (older than 300 seconds relative to the current time cycle). We overwrite it.
   • If times[i] equals the current timestamp, we simply increment the counter in hits[i].

Visual Description: Imagine a circular slots mechanism with 300 compartments. As time progresses, the "current" pointer moves around the circle. When the pointer returns to a specific slot after a full rotation (300 seconds), the old data in that slot is naturally expired. We clear the old count, write the new timestamp, and start counting for the new second. This ensures we never store more than 300 seconds of data, and we compress multiple hits at the same second into a single integer.

Execution Flow

Let's trace the algorithm with a simplified window size of 5 seconds (instead of 300) for clarity.

1. State: times = [0,0,0,0,0], hits = [0,0,0,0,0]
2. Call hit(1):
   • index = 1 % 5 = 1.
   • times[1] (0) != 1.
   • Update: times[1] = 1, hits[1] = 1.
   • State: times=[0,1,0,0,0], hits=[0,1,0,0,0]
3. Call hit(2):
   • index = 2 % 5 = 2.
   • Update: times[2] = 2, hits[2] = 1.
   • State: times=[0,1,2,0,0], hits=[0,1,1,0,0]
4. Call hit(2) (Another hit at same second):
   • index = 2 % 5 = 2.
   • times[2] (2) == 2.
   • Increment: hits[2] becomes 2.
   • State: times=[0,1,2,0,0], hits=[0,1,2,0,0]
5. Call hit(6) (Time wraps around):
   • index = 6 % 5 = 1.
   • times[1] (1) != 6.
   • Overwrite: times[1] = 6, hits[1] = 1.
   • State: times=[0,6,2,0,0], hits=[0,1,2,0,0]
   • Note: The data for timestamp 1 is now gone, which is correct as $6 - 1 = 5$ (window is strictly less than 5).
6. Call getHits(6):
   • Iterate i from 0 to 4.
   • i=0: times[0]=0. $6-0 \ge 5$. Ignore.
   • i=1: times[1]=6. $6-6 < 5$. Add (1). Total = 1.

Proof of Correctness

The correctness relies on the modulo operator mapping timestamps to 300 unique slots. Since the window of interest is exactly 300 seconds, any two timestamps $t_1$ and $t_2$ where $t_1 \equiv t_2 \pmod{300}$ must differ by a multiple of 300.

If $|t_1 - t_2| < 300$, they will map to different indices. If they map to the same index, one must be at least 300 seconds older than the other. Because timestamps are monotonically increasing, the value stored in times[i] will always be the most recent timestamp for that modulo slot. The check in getHits (timestamp - times[i] < 300) rigorously filters out any stale data that hasn't been overwritten yet, ensuring we only sum counts from the valid window.

Reference Implementation

C++ Solution for LeetCode 362

cpp
class HitCounter {
private:
    vector<int> times;
    vector<int> hits;

public:
    HitCounter() {
        // Resize to 300 to cover the 5-minute window
        times.resize(300, 0);
        hits.resize(300, 0);
    }
    
    void hit(int timestamp) {
        int index = timestamp % 300;
        
        if (times[index] != timestamp) {
            // New timestamp for this bucket; reset count and update time
            times[index] = timestamp;
            hits[index] = 1;
        } else {
            // Same timestamp; increment count
            hits[index]++;
        }
    }
    
    int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; ++i) {
            // Check if the bucket time is within the last 300 seconds
            if (timestamp - times[i] < 300) {
                total += hits[i];
            }
        }
        return total;
    }
};

Java Solution for LeetCode 362

java
class HitCounter {
    private int[] times;
    private int[] hits;

    public HitCounter() {
        // Fixed size arrays for the 300-second window
        times = new int[300];
        hits = new int[300];
    }
    
    public void hit(int timestamp) {
        int index = timestamp % 300;
        
        if (times[index] != timestamp) {
            // If the time in the bucket is different, it's stale or empty.
            // Reset with current timestamp and count 1.
            times[index] = timestamp;
            hits[index] = 1;
        } else {
            // Same timestamp, just increment.
            hits[index]++;
        }
    }
    
    public int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) {
            // Sum hits only if the recorded time is within the 300s window
            if (timestamp - times[i] < 300) {
                total += hits[i];
            }
        }
        return total;
    }
}

Python Solution for LeetCode 362

python
class HitCounter:

    def __init__(self):
        # Initialize buckets for timestamps and hit counts
        self.times = [0] * 300
        self.hits = [0] * 300

    def hit(self, timestamp: int) -> None:
        index = timestamp % 300
        
        if self.times[index] != timestamp:
            # New timestamp for this slot, reset logic
            self.times[index] = timestamp
            self.hits[index] = 1
        else:
            # Existing timestamp, aggregate hits
            self.hits[index] += 1

    def getHits(self, timestamp: int) -> int:
        total = 0
        for i in range(300):
            # Check if the stored time is within the valid window
            if timestamp - self.times[i] < 300:
                total += self.hits[i]
            
        return total

• Mistake: Storing counts in a hash map and cleaning up keys.
• Reason: While better than a list, you must manually manage key deletion (garbage collection) for old timestamps.
• Consequence: The map can grow indefinitely if cleanup isn't triggered frequently, leading to unbounded space usage over time.