Problem Overview
LeetCode 362 — Design Hit Counter — asks you to design a class with two methods: hit(timestamp) records a hit at the given timestamp (in seconds), and getHits(timestamp) returns the total number of hits in the past 300 seconds — that is, all hits where timestamp - 300 < t <= timestamp. Timestamps are always given in strictly increasing order, so you never need to handle out-of-order events.
The problem maps directly to a real-world rate limiting scenario: count how many API requests occurred in the last 5 minutes. This pattern appears in system design interviews, distributed systems, and backend engineering. Solving LeetCode 362 cleanly demonstrates your understanding of sliding window data structures, circular buffers, and the trade-offs between memory usage and time complexity.
There are two primary solutions with different trade-offs. The queue-based approach stores every individual timestamp and is simple to implement. The circular array approach uses exactly two arrays of size 300 and handles arbitrarily high traffic volumes in constant memory — making it the preferred solution when interviewers ask about high-traffic systems or follow up with thread safety questions.
- hit(timestamp): record a hit at the given timestamp (seconds granularity)
- getHits(timestamp): return total hits in the range (timestamp - 300, timestamp]
- Timestamps are non-decreasing — no out-of-order events
- Timestamps are in seconds, not milliseconds
- Follow-up: handle concurrent hits from multiple threads
Queue-Based Approach
The queue approach stores every incoming timestamp in a deque (double-ended queue). When hit(timestamp) is called, append the timestamp to the right end of the deque. When getHits(timestamp) is called, dequeue all entries from the left end that are older than 300 seconds — that is, all entries where entry <= timestamp - 300. After evicting stale entries, the length of the deque is the hit count.
Time complexity is O(1) amortized for both hit and getHits: each timestamp is added to the queue exactly once and removed at most once, so across n operations the total work is O(n). Space complexity is O(w) where w is the number of distinct hits within the current 300-second window. In the worst case (one hit per second for 300 seconds), the queue holds 300 entries. If multiple hits occur at the same timestamp, each is stored separately.
The queue approach is simple and correct, but its memory usage is proportional to the number of hits in the window — not the window size. Under high traffic (thousands of hits per second), the queue could hold millions of entries simultaneously. For interview purposes, the queue solution establishes baseline correctness before the interviewer asks the follow-up about optimizing for high-volume traffic.
The Queue Acts as a Sliding Window
The queue naturally acts as a sliding window: old timestamps are removed from the front when they fall outside the 300-second window, and new timestamps are added to the back on each hit. The queue length at any point equals the exact hit count for the current window — no separate counter variable is needed. This self-maintaining property is the key insight that makes the queue solution elegant despite its linear memory footprint.
Circular Array Optimization
The circular array solution uses exactly two fixed-size arrays of length 300: times[] stores the most recent timestamp that mapped to each bucket, and hits[] stores the hit count for that timestamp. The bucket index for a timestamp is computed as idx = timestamp % 300. This maps any timestamp into one of 300 fixed slots, cycling through them as time advances.
When hit(timestamp) is called: compute idx = timestamp % 300. If times[idx] == timestamp, the bucket belongs to the current timestamp — increment hits[idx] by 1. If times[idx] != timestamp, the bucket is stale (it was written 300+ seconds ago) — reset times[idx] = timestamp and hits[idx] = 1. This reset-on-mismatch is the key mechanism that recycles old entries without any explicit eviction loop.
When getHits(timestamp) is called: iterate over all 300 buckets. For each bucket i, if times[i] > timestamp - 300 (the entry is within the valid window), add hits[i] to the total. Return the total. This loop always runs exactly 300 iterations regardless of traffic volume, giving O(300) = O(1) constant time for getHits.
- 1Initialize: times = [0] * 300; hits = [0] * 300
- 2hit(timestamp): idx = timestamp % 300
- 3 if times[idx] == timestamp: hits[idx] += 1
- 4 else: times[idx] = timestamp; hits[idx] = 1
- 5getHits(timestamp): total = 0
- 6 for i in range(300): if times[i] > timestamp - 300: total += hits[i]
- 7 return total
Why Circular Array Is Better
The circular array solution has O(1) time for hit and O(300) = O(1) time for getHits — identical asymptotic performance to the queue but with strictly better constant factors. More importantly, it uses exactly 600 integers of memory regardless of hit volume. Whether the system receives 1 hit per second or 1 million hits per second, the circular array always uses the same 600-integer footprint.
The queue solution's memory scales with the number of hits in the active window. At 1,000,000 hits per second with a 300-second window, the queue must hold 300,000,000 entries simultaneously — roughly 2.4 GB of memory for 64-bit integers. The circular array holds the same data in 600 integers because it aggregates all hits sharing the same second into a single bucket.
This is why interviewers prefer the circular array answer for the follow-up question about high traffic. The circular array solution does not just perform better in theory — it is the only practical solution at scale. The queue solution is useful for establishing correctness and understanding the sliding window concept, but the circular array is the correct production answer.
Circular Array Wins at High Traffic
The circular array is the preferred approach for follow-up questions about high traffic: it uses constant memory even with millions of hits per second. The key insight is that timestamps in seconds granularity can only produce 300 distinct active buckets at any time — one per second in the window. No matter how many hits share the same second, they are aggregated into a single integer. This fixed-size aggregation is what keeps memory constant and is the core of all circular buffer designs in production rate limiters.
Thread Safety Follow-Up
Interviewers frequently ask: how would you handle concurrent hits from multiple threads? The queue approach requires synchronization on both the append (hit) and the dequeue+scan (getHits) operations. In Java, wrapping the deque with synchronized blocks or using a ConcurrentLinkedQueue handles concurrent appends, but getHits requires a full lock during eviction and counting to prevent torn reads.
The circular array approach requires atomic read-modify-write on the bucket level. For each bucket, the check-and-reset logic (if times[idx] != timestamp: reset) is a compound operation that must be atomic. In Java, AtomicIntegerArray for hits and a separate AtomicIntegerArray for times can support lock-free updates using compare-and-swap. In Python, the GIL provides basic protection but is insufficient for production concurrent code.
For distributed systems, a Redis-based implementation using ZADD (sorted set with timestamp as score) and ZREMRANGEBYSCORE (remove entries older than 300 seconds) provides a battle-tested sliding window rate limiter that works across multiple server instances. The LeetCode 362 problem is a simplified in-memory version of this canonical distributed rate limiter pattern.
- 1Queue approach: wrap deque with ReentrantLock in Java; use threading.Lock in Python
- 2Circular array: use AtomicIntegerArray for lock-free bucket reads/writes in Java
- 3For getHits with queue: acquire lock, evict stale entries, return size, release lock
- 4For hit with circular array: CAS loop on times[idx] to detect and reset stale buckets
- 5Distributed: Redis ZADD + ZREMRANGEBYSCORE + ZCARD for cross-instance rate limiting
- 6Consider time-bucketed counters (token bucket, leaky bucket) for smoother traffic shaping
Code Walkthrough: Python and Java
Python queue solution: from collections import deque; self.q = deque(). hit(t): self.q.append(t). getHits(t): while self.q and self.q[0] <= t - 300: self.q.popleft(); return len(self.q). Python circular array solution: self.times = [0]*300; self.hits = [0]*300. hit(t): idx = t % 300; self.times[idx] = t if self.times[idx] != t else self.times[idx]; self.hits[idx] = 1 if self.times[idx] != t else self.hits[idx] + 1. More cleanly: if self.times[idx] != t: self.times[idx] = t; self.hits[idx] = 1; else: self.hits[idx] += 1. getHits(t): return sum(self.hits[i] for i in range(300) if self.times[i] > t - 300).
Java queue solution: Deque<Integer> q = new ArrayDeque<>(). hit(t): q.offer(t). getHits(t): while (!q.isEmpty() && q.peek() <= t - 300) q.poll(); return q.size(). Java circular array solution: int[] times = new int[300]; int[] hits = new int[300]. hit(t): int idx = t % 300; if (times[idx] != t) { times[idx] = t; hits[idx] = 1; } else { hits[idx]++; }. getHits(t): int total = 0; for (int i = 0; i < 300; i++) if (times[i] > t - 300) total += hits[i]; return total. Both solutions are clean, concise, and interview-ready.
Time complexity summary: queue hit = O(1), queue getHits = O(k) amortized where k is evicted entries; circular hit = O(1), circular getHits = O(300) = O(1). Space complexity: queue = O(w) where w is hits in active window; circular = O(1) (fixed 600 integers). The circular array's constant space and constant time make it the clear winner for production code.
Always Check times[idx] Before Incrementing
In the circular array, always check if times[idx] matches the current timestamp before adding to hits[idx]. A stale entry — written 300 or more seconds ago — occupies the same bucket index due to modulo wraparound. If you skip the check and blindly increment hits[idx], you will count hits from a different second as part of the current second's total. The reset logic (times[idx] = timestamp; hits[idx] = 1) is not optional — it is the mechanism that makes the circular buffer correct across the full 300-second window.