Design Hit Counter LeetCode Solution

Table of Contents

Problem Statement

Design Hit Counter LeetCode Solution – 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

Test Case 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); //gets hits at timestamp 4, return 3.

hitCounter.hit(300); // hit at timestamp 300.

hitCounter.getHits(300); //gets hits at timestamp 300, return 4.

hitCounter.getHits(301); //gets hits at timestamp 301, return 3.

Explanation

O(s) s is the total seconds in the given time interval, in this case, 300.
the basic idea is using buckets. 1 bucket for every second because we only need to keep the recent hits info for 300 seconds. hit[] array is wrapped around by mod operation. Each hit bucket is associated with times[] bucket which records the current time. If it is not the current time, it means it is 300s or 600s… ago and needs to reset to 1.

Code for Design Hit Counter

Java Program

class HitCounter {

    private int[] times;
    private int[] hits;
    /** Initialize your data structure here. */
    public HitCounter() {
        times = new int[300];
        hits = new int[300];
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        int index = timestamp % 300;
        if (times[index] != timestamp) {
            times[index] = timestamp;
            hits[index] = 1;
        } else {
            hits[index]++;
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) {
            if (timestamp - times[i] < 300) {
                total += hits[i];
            }
        }
        return total;
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */

C++ Program

class HitCounter {
    struct Hit {
        int timestamp;
        int count;
    };
    vector<Hit> hits;
public:
    /** Initialize your data structure here. */
    HitCounter() {
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        if (hits.empty())
            hits.push_back(Hit{timestamp, 0});
        else
            hits.push_back(Hit{timestamp, hits.back().count + 1});
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int l = timestamp - 60*5;
        
        auto lb = upper_bound(hits.begin(), hits.end(), Hit{l, {}}, [](const auto &a, const auto &b) {
            return a.timestamp < b.timestamp; 
        });
                
        if (lb == hits.end()) 
            return 0;
        
        auto ub = upper_bound(lb, hits.end(), Hit{timestamp, {}}, [](const auto &a, const auto &b) {
            return a.timestamp < b.timestamp;
        });
        
        ub -= 1;
        return ub->count - lb->count + 1;
    }
};

Complexity Analysis for Design Hit Counter LeetCode Solution

Time Complexity will be $O (t),$ $where t is the time interval. In this case, t = 300.$

Space Complexity will be $O (t),$ $where t is the time interval. In this case, t = 300.$

Reference: https://en.wikipedia.org/wiki/hit_counter