A simple queue-based O(1) Hits O(1) GetHits O(300) Space Scale-able Solution


  • 0
    F
    class HitCounter {
        queue<pair<int, int>> m_q;
        int total_count = 0;
    public:
        void hit(int timestamp) {
            total_count ++;
            if (m_q.size() && m_q.back().first == timestamp)
            {
                m_q.back().second ++;
                return;
            }
            if (m_q.size() >= 300) //There can't be >300 distinct timestamps;
            {
                total_count -= m_q.front().second;
                m_q.pop();
            }
            m_q.emplace(timestamp, 1);
        }
        int getHits(int timestamp) {
            while(m_q.size() && m_q.front().first <= timestamp - 300)
            {
                total_count -= m_q.front().second;
                m_q.pop();
            }
            return total_count;
        }
    };

Log in to reply
 

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