Design Hit Counter

LeetCode 362: Design Hit Counter Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a fixed-size circular buffer (buckets) to aggregate hit counts per second, ensuring both storage and retrieval operations occur in constant time relative to the total number of hits.

The LeetCode 362 problem, "Design Hit Counter," requires us to design a data structure that tracks incoming "hits" (requests or events) stamped with a time in seconds. We must support two operations: recording a hit at a specific timestamp and retrieving the total number of hits that occurred in the last 5 minutes (300 seconds). A crucial constraint is that timestamps are received in chronological order.

Brute Force Approach for Design Hit Counter

The naive approach involves storing every single hit's timestamp in a dynamically growing list or array.

1. Data Structure: A dynamic array (e.g., ArrayList in Java, vector in C++).
2. hit(timestamp): Append the incoming timestamp to the end of the list.
3. getHits(timestamp): Iterate through the entire list. For every element, check if it falls within the range [timestamp - 299, timestamp]. Count the valid elements and return the sum. Alternatively, one might remove elements strictly smaller than timestamp - 299 to keep the list size manageable.

1# Pseudo-code for Brute Force
2class HitCounter:
3    def __init__(self):
4        self.all_hits = []
5
6    def hit(self, timestamp):
7        self.all_hits.append(timestamp)
8
9    def getHits(self, timestamp):
10        count = 0
11        limit = timestamp - 300
12        # Iterate all history
13        for t in self.all_hits:
14            if t > limit:
15                count += 1
16        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.

Algorithm Strategy: Design Patterns

We will implement the circular bucket strategy to ensure scalability. This approach handles massive bursts of traffic at the same timestamp efficiently.

1. Initialization:

   • Initialize times array of size 300 with 0.
   • Initialize hits array of size 300 with 0.

2. hit(timestamp):

   • Compute index = timestamp % 300.
   • Check the value at times[index].
   • Case 1 (Same Time): If times[index] == timestamp, increment hits[index]. This aggregates concurrent hits.
   • Case 2 (New Time): If times[index] != timestamp, it means the bucket holds data from a previous 5-minute cycle (e.g., timestamp 1 vs timestamp 301). Update times[index] = timestamp and reset hits[index] = 1.

3. getHits(timestamp):

   • Initialize total = 0.
   • Iterate through the array from i = 0 to 299.
   • For each bucket, check validity: if timestamp - times[i] < 300, the data is within the 5-minute window.
   • If valid, add hits[i] to total.
   • Return total.

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 hits[1] (1). Total = 1.
   • i=2: times[2]=2. $6-2 < 5$. Add hits[2] (2). Total = 3.
   • i=3,4: Empty/Old. Ignore.
   • Result: 3.

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.

Pattern Reuse Notes

The Design pattern, specifically involving circular buffers or bucket aggregation, applies to several other LeetCode problems:

• LeetCode 146: LRU Cache: Requires designing a structure (HashMap + Doubly Linked List) to manage capacity constraints efficiently.
• LeetCode 155: Min Stack: Involves designing a stack that retrieves the minimum element in $O(1)$ by maintaining auxiliary state.
• LeetCode 225: Implement Stack using Queues: Focuses on adapting one data structure behavior to another.
• LeetCode 232: Implement Queue using Stacks: Similar to 225, focusing on internal state management to satisfy interface contracts.

These problems all share the requirement of manipulating standard data structures or creating composite ones to satisfy strict time complexity constraints for specific operations.

Reference Implementation

C++ Solution for LeetCode 362

1class HitCounter {
2private:
3    vector<int> times;
4    vector<int> hits;
5
6public:
7    HitCounter() {
8        // Resize to 300 to cover the 5-minute window
9        times.resize(300, 0);
10        hits.resize(300, 0);
11    }
12    
13    void hit(int timestamp) {
14        int index = timestamp % 300;
15        
16        if (times[index] != timestamp) {
17            // New timestamp for this bucket; reset count and update time
18            times[index] = timestamp;
19            hits[index] = 1;
20        } else {
21            // Same timestamp; increment count
22            hits[index]++;
23        }
24    }
25    
26    int getHits(int timestamp) {
27        int total = 0;
28        for (int i = 0; i < 300; ++i) {
29            // Check if the bucket time is within the last 300 seconds
30            if (timestamp - times[i] < 300) {
31                total += hits[i];
32            }
33        }
34        return total;
35    }
36};

Java Solution for LeetCode 362

1class HitCounter {
2    private int[] times;
3    private int[] hits;
4
5    public HitCounter() {
6        // Fixed size arrays for the 300-second window
7        times = new int[300];
8        hits = new int[300];
9    }
10    
11    public void hit(int timestamp) {
12        int index = timestamp % 300;
13        
14        if (times[index] != timestamp) {
15            // If the time in the bucket is different, it's stale or empty.
16            // Reset with current timestamp and count 1.
17            times[index] = timestamp;
18            hits[index] = 1;
19        } else {
20            // Same timestamp, just increment.
21            hits[index]++;
22        }
23    }
24    
25    public int getHits(int timestamp) {
26        int total = 0;
27        for (int i = 0; i < 300; i++) {
28            // Sum hits only if the recorded time is within the 300s window
29            if (timestamp - times[i] < 300) {
30                total += hits[i];
31            }
32        }
33        return total;
34    }
35}

Python Solution for LeetCode 362

1class HitCounter:
2
3    def __init__(self):
4        # Initialize buckets for timestamps and hit counts
5        self.times = [0] * 300
6        self.hits = [0] * 300
7
8    def hit(self, timestamp: int) -> None:
9        index = timestamp % 300
10        
11        if self.times[index] != timestamp:
12            # New timestamp for this slot, reset logic
13            self.times[index] = timestamp
14            self.hits[index] = 1
15        else:
16            # Existing timestamp, aggregate hits
17            self.hits[index] += 1
18
19    def getHits(self, timestamp: int) -> int:
20        total = 0
21        for i in range(300):
22            # Check if the stored time is within the valid window
23            if timestamp - self.times[i] < 300:
24                total += self.hits[i]
25            
26        return total