Skip to main content
Talentd

Design Hit Counter - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchDesignQueue8 min readAsked at: Amazon, Microsoft, Apple +22
Practice this problem

Problem Statement

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

  • HitCounter() Initializes the object of the hit counter system.
  • void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
  • int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

 

Example 1:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

 

Constraints:

  • 1 <= timestamp <= 2 * 109
  • All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).
  • At most 300 calls will be made to hit and getHits.

 

Follow up: What if the number of hits per second could be huge? Does your design scale?

Approach Overview

Problem Overview: Design a data structure that records hits at specific timestamps and returns how many hits occurred in the last 5 minutes (300 seconds). The API exposes two operations: hit(timestamp) to record a hit and getHits(timestamp) to count hits within the sliding 300‑second window.

Approach 1: Queue / Sliding Window (O(n) worst case per query, O(n) space)

Store every hit timestamp in a queue. Each call to hit() pushes the timestamp into the queue. When getHits() runs, remove timestamps from the front while they are older than timestamp - 300. The remaining queue size equals the number of valid hits. This works because timestamps arrive in chronological order, so outdated entries always appear at the front. The approach relies on a simple sliding window using a queue, which keeps operations intuitive and efficient for moderate traffic streams.

Approach 2: Binary Search on Timestamp Array (O(log n) query, O(n) space)

Store timestamps in a dynamic array as hits arrive. Because timestamps are inserted in sorted order, the array remains sorted automatically. When getHits(timestamp) is called, compute the lower boundary timestamp - 299 and use binary search to find the first index whose timestamp falls within the 5‑minute window. The result equals total_hits - index. Recording a hit remains O(1), while queries run in O(log n). This approach works well for high query frequency since it avoids repeatedly popping elements.

The key insight is that timestamps are naturally ordered because the data stream is chronological. That property allows efficient searching over an array without additional sorting. Binary search quickly finds the earliest valid hit in the 300‑second window.

Recommended for interviews: The binary search design is usually the strongest answer. It demonstrates awareness of ordered data streams and efficient querying with logarithmic complexity. Mentioning the queue sliding‑window approach first shows you understand the problem constraints, but implementing the binary search solution highlights stronger algorithmic reasoning for scalable systems.

Solution

Since timestamp is monotonically increasing, we can use an array ts to store all timestamps. Then in the getHits method, we use binary search to find the first position that is greater than or equal to timestamp - 300 + 1, and then return the length of ts minus this position.

In terms of time complexity, the time complexity of the hit method is O(1), and the time complexity of the getHits method is O(log n). Where n is the length of ts.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Queue / Sliding WindowO(1) hit, O(n) worst‑case getHitsO(n)Simple implementation when hit frequency is moderate and removing outdated timestamps is acceptable.
Binary Search on Timestamp ArrayO(1) hit, O(log n) getHitsO(n)Best when queries are frequent and timestamps remain sorted from the data stream.

Video Solution

DESIGN HIT COUNTER | LEETCODE 362 | PYTHON BINARY SEARCH SOLUTION • Cracking FAANG • 12,184 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Hit Counter easy or hard?
Design Hit Counter is generally rated Medium difficulty. The logic is straightforward, but interviewers expect an efficient design that handles continuous data streams and performs fast range queries within the 5‑minute window.
Design Hit Counter Python/Java solution
A typical Python or Java solution stores timestamps in a list or array. hit(timestamp) appends the value, and getHits(timestamp) performs binary search to find the first valid timestamp within the last 300 seconds, returning the count of remaining elements.
How to solve Design Hit Counter in O(log n)?
Store all hit timestamps in a sorted array. When getHits(timestamp) is called, compute timestamp - 299 and perform binary search to find the first timestamp >= that value. The number of hits equals total timestamps minus that index.
What is the best approach for Design Hit Counter?
Binary search on a sorted timestamp list is a strong solution. Each hit is appended in O(1) time, and getHits uses binary search to locate the first timestamp within the last 300 seconds, giving O(log n) query complexity.
Is Design Hit Counter asked at Google/Amazon/Meta?
Design Hit Counter is commonly associated with Meta (Facebook) interview question sets and appears frequently in system design and data stream discussions. It tests understanding of sliding windows, queues, and efficient querying in time‑based data streams.
What data structure is used in Design Hit Counter?
Common implementations use either a queue for a sliding window or a dynamic array combined with binary search. The queue approach removes outdated timestamps, while the array approach keeps timestamps sorted for efficient search.
What is the time complexity of Design Hit Counter?
With the binary search design, hit() runs in O(1) because timestamps are appended to the array. getHits() runs in O(log n) using binary search to find the boundary of the 5‑minute window. Space complexity is O(n) for storing timestamps.

Ready to solve this problem?

Practice Design Hit Counter with our built-in code editor and test cases.

Practice on FleetCode
Previous

Logger Rate Limiter