0ms solution using deque and unordered_map


  • 0
    Y

    The idea is using deque to record timestamps and using unordered_map to record number of hits of each timestamp in deque. Then only pop queue when getHits is called.

    class HitCounter {
        deque<int> q;
        unordered_map<int,int> qm;
        int count;
    public:
        /** Initialize your data structure here. */
        HitCounter() {
            this->count = 0; 
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        void hit(int timestamp) {
            count++;
            if(qm.find(timestamp) == qm.end())
                q.push_back(timestamp);
            qm[timestamp]++;
        }
        
        /** Return the number of hits in the past 5 minutes.
            @param timestamp - The current timestamp (in seconds granularity). */
        int getHits(int timestamp) {
            while(!q.empty() && timestamp-q.front()>=300){
                this->count -= qm[q.front()];
                qm.erase(qm.find(q.front()));
                q.pop_front();
            } 
            return this->count;
        }
    };
    
    
    

Log in to reply
 

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