A C++ solution with O(n) hits and O(logn) getHits


  • 0
    G
    class HitCounter {
    private:
        deque<int> hits;
    public:
        /** Initialize your data structure here. */
        HitCounter() {}
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            // keep a deque with maximum size of 300 for scaling
            while (!hits.empty() && hits.front() <= timestamp - 300) hits.pop_front();
            hits.push_back(timestamp);
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
            return hits.size() - (upper_bound(hits.begin(), hits.end(), timestamp - 300) - hits.begin());
        }
    };

  • 0
    F

    Unfortunately, this solution is not O(1) hits, say we call hit(1) for 300 times, and then call hit(400), the following logic will iterate the entire deque, which causes the the complxity of hits to be O(n):

    while (!hits.empty() && hits.front() <= timestamp - 300) hits.pop_front();
    

  • 0
    G

    Yes. You are right. I didn't notice that several hits could be at the same time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.