362. Design Hit Counter - cocoder39/coco39_LC GitHub Wiki

362. Design Hit Counter

amortized time complexity is O(1) since each element can be pushed and popped only twice. space complexity is O(1)

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {
        
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        dq.push_back(timestamp);
        getHits(timestamp);
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (! dq.empty() && dq.front() <= timestamp - 300) {
            dq.pop_front();
        }
        return dq.size();
    }
private:
    deque<int> dq;
};
⚠️ **GitHub.com Fallback** ⚠️