LeetCode 362: Design Hit Counter Solution in Python – A Step-by-Step Guide

What Is LeetCode 362: Design Hit Counter?

LeetCode 362: Design Hit Counter asks you to create a HitCounter class that records hits at specific timestamps and reports the number of hits in the past 5 minutes (300 seconds). It’s a design problem focused on efficiently handling time windows—perfect for real-time analytics!

Problem Statement

• Class: HitCounter
• Methods:
• __init__(): Initialize the counter.
• hit(timestamp): Record a hit at the given timestamp.
• getHits(timestamp): Return the number of hits in the past 300 seconds.
• Rules:
• Timestamps are in seconds, non-decreasing.
• Hits within [timestamp - 299, timestamp] are counted.
• Multiple hits can occur at the same timestamp.

Constraints

• 1 <= timestamp <= 2 * 10⁹
• Timestamps are non-decreasing.
• At most 3 * 10⁴ calls to hit and getHits.

Examples

• Input: ["HitCounter","hit","hit","hit","getHits","getHits"], [[],[1],[2],[3],[4],[300]]
• Output: [null,null,null,null,3,3]
• 1s: Hit → 1 hit.
• 2s: Hit → 2 hits.
• 3s: Hit → 3 hits.
• 4s: getHits → 3 hits (1,2,3 within [4-299,4] = [-295,4]).
• 300s: getHits → 3 hits (1,2,3 within [1,300]).
• Input: ["HitCounter","hit","getHits","hit","getHits"], [[],[1],[300],[301],[301]]
• Output: [null,null,1,null,2]
• 1s: Hit → 1.
• 300s: getHits → 1 (1 within [1,300]).
• 301s: Hit → 2.
• 301s: getHits → 2 (1,301 within [2,301]).

These show the 5-minute window—let’s solve it!

Understanding the Problem: Counting Hits in a Window

To tackle LeetCode 362 in Python, we need a class that: 1. Records hits with timestamps. 2. Counts hits in the last 300 seconds for any given timestamp. 3. Handles non-decreasing timestamps efficiently.

A naive approach might store all hits and scan them, but that’s slow. Instead, we’ll use:

• Best Solution: Deque—O(1) amortized time, O(n) space—flexible and efficient.
• Alternative Solution: Fixed-size array—O(1) worst-case time, O(1) space—simple but less scalable.

Let’s count with the best solution!

Best Solution: Deque

Why This Is the Best Solution

The deque (double-ended queue) approach offers O(1) amortized time for both hit and getHits by storing timestamps in a queue and removing old ones as needed. It’s memory-efficient for sparse hits and adapts to any window size—making it the top choice for this design!

How It Works

Think of it like a sliding window:

• Setup: Use a deque to store timestamps of hits.
• Hit: Add the new timestamp to the queue.
• GetHits: Remove timestamps older than 300 seconds, return queue length.
• Result: Queue length is the hit count in the window.

It’s like keeping a rolling log of recent hits!

Step-by-Step Example

For calls: hit(1), hit(2), hit(3), getHits(4), getHits(300):

• Init: queue = deque().
• hit(1): queue = [1].
• hit(2): queue = [1, 2].
• hit(3): queue = [1, 2, 3].
• getHits(4):
• Window: [4-299, 4] = [-295, 4].
• All (1,2,3) within, return 3.
• getHits(300):
• Window: [300-299, 300] = [1, 300].
• All (1,2,3) within, return 3.

For hit(1), getHits(300), hit(301), getHits(301):

• hit(1): queue = [1].
• getHits(300): Window [1, 300], return 1.
• hit(301): queue = [1, 301].
• getHits(301): Window [2, 301], return 2.

Output: [null, null, 1, null, 2].

Code with Explanation

Here’s the Python code using a deque:

from collections import deque

class HitCounter:
    def __init__(self):
        # Initialize a deque to store hit timestamps
        self.queue = deque()

    def hit(self, timestamp: int) -> None:
        # Add the timestamp to the queue
        self.queue.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        # Remove hits older than 300 seconds
        while self.queue and timestamp - self.queue[0] >= 300:
            self.queue.popleft()
        # Return the number of hits in the window
        return len(self.queue)

Explanation

• Lines 3-5: __init__: Create an empty deque to store timestamps.
• Lines 7-9: hit: Append the new timestamp to the queue—O(1).
• Lines 11-15: getHits:
• Line 12-13: While the oldest timestamp is outside the 300-second window (timestamp - oldest ≥ 300), remove it—O(1) amortized.
• Line 15: Return queue length, representing hits in [timestamp-299, timestamp]—O(1).

• Time Complexity:
• hit: O(1)—append is constant.
• getHits: O(1) amortized—each timestamp is added and removed once over all calls.
• Space Complexity: O(n)—where n is the number of hits within 300 seconds (up to 3*10⁴).

This is like a dynamic hit tracker—fast and adaptable!

Alternative Solution: Fixed-Size Array

Why an Alternative Approach?

The fixed-size array solution uses a 300-slot array to track hits per second, offering O(1) worst-case time for both operations. It’s space-efficient (O(1)) but assumes timestamps fit within a cyclic 300-second window—great for simplicity and bounded scenarios!

How It Works

• Setup: Use a 300-element array for timestamps (0-299) and counts.
• Hit: Increment count at timestamp % 300, update cycle if needed.
• GetHits: Sum counts, adjusting for cycle mismatches.

Step-by-Step Example

For hit(1), hit(2), hit(3), getHits(4), getHits(300):

• Init: times = [0]*300, counts = [0]*300.
• hit(1): times[1]=1, counts[1]=1.
• hit(2): times[2]=1, counts[2]=1.
• hit(3): times[3]=1, counts[3]=1.
• getHits(4): Sum counts where times match cycle (1), all 3 hits, return 3.
• getHits(300): Cycle=1, times[1-3]=1, counts=3, return 3.

For hit(301) after 300:

• hit(301): 301 % 300 = 1, times[1]=301//300=1, counts[1]+=1 → 2.

Code with Explanation

class HitCounter:
    def __init__(self):
        # Fixed-size arrays for 300 seconds
        self.times = [0] * 300  # Last cycle timestamp appeared
        self.counts = [0] * 300  # Hits at each second

    def hit(self, timestamp: int) -> None:
        idx = timestamp % 300
        # If timestamp cycle doesn’t match, reset count
        if self.times[idx] != timestamp // 300:
            self.times[idx] = timestamp // 300
            self.counts[idx] = 1
        else:
            self.counts[idx] += 1

    def getHits(self, timestamp: int) -> int:
        total = 0
        cycle = timestamp // 300
        for i in range(300):
            # Count hits if within 300s (same or previous cycle)
            if cycle - self.times[i] <= 1:
                total += self.counts[i]
        return total

Explanation

• Lines 3-5: __init__: Two arrays: times tracks cycle (timestamp//300), counts tracks hits.
• Lines 7-13: hit:
• Compute index as timestamp % 300.
• If cycle (timestamp//300) differs, reset count to 1 and update time.
• Else, increment count—O(1).
• Lines 15-21: getHits:
• Sum counts where cycle difference ≤ 1 (current or last 300s)—O(1).
• Time: O(1) worst-case for both (300 iterations constant).
• Space: O(1)—fixed 300 slots.

It’s like a cyclic hit counter—simple and bounded!

Comparing the Two Solutions

• Deque (Best):
• Time: O(1) amortized—dynamic cleanup.
• Space: O(n)—grows with hits.
• Pros: Flexible, exact window.
• Cons: More memory for sparse hits.
• Array (Alternative):
• Time: O(1) worst-case—fixed iterations.
• Space: O(1)—constant 300 slots.
• Pros: Predictable, memory-efficient.
• Cons: Assumes cyclic time, less precise for sparse data.

Deque wins for flexibility and real-world use!

Additional Examples and Edge Cases

• hit(1), hit(1): Counts multiple hits.
• getHits(600): Deque cleans up, array cycles.
• No hits: Both return 0.

Both handle these, deque is more adaptable.

Complexity Breakdown

• Deque:
• Time: O(1) amortized.
• Space: O(n).
• Array:
• Time: O(1) worst-case.
• Space: O(1).

Deque balances speed and flexibility.

Key Takeaways

• Deque: Dynamic window—top efficiency!
• Array: Fixed slots—simple and steady!
• Time Windows: Design matters.
• Python Tip: Deques rock—see [Python Basics](/python/basics).

Final Thoughts: Count Those Hits

LeetCode 362: Design Hit Counter in Python is a time-window challenge. The deque solution is the versatility champ, while the array offers simplicity. Want more? Try LeetCode 359: Logger Rate Limiter or LeetCode 346: Moving Average. Ready to track? Visit Solve LeetCode 362 on LeetCode and count those hits today!