# 4ms C++ solution, O(300) time, O(300) space, no complicated data structure

• My basic idea is when there is a timestamp, I fix the current valid cycle `[timestamp - 300, timestamp]`. In order to achieve this, I record last timestamp of hit `prev`.

• If `prev` is less than `timestamp - 300`, then obviously, nothing happened for last cycle
• Otherwise, `[pre + 1, timestamp]` should be reset to 0

For storage, I use vector to store 300 elements in a circular way. Since time starts at 1, so `(time - 1) % 300` can get the right position.

``````class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {
m_vHits.assign(300, 0);
m_iPrev = 0;
}

/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
fix_cycle(timestamp);
m_vHits[(timestamp - 1) % 300]++;
m_iPrev = timestamp;
}

/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
fix_cycle(timestamp);
return accumulate(m_vHits.begin(), m_vHits.end(), 0);
}
private:
vector<int> m_vHits;
int m_iPrev;//last timestamp of hit

void fix_cycle(int timestamp)
{
int start = timestamp - 300 + 1;//start of this valid cycle
if(start > m_iPrev)//nothing happend for last cycle, reset all
{
m_vHits.clear();
m_vHits.assign(300, 0);
}
else//[start--m_iPrev] should be kept, but nothing happened between [m_iPrev -- timestamp], reset as 0
{
for(int i = m_iPrev + 1; i <= timestamp; ++i)
m_vHits[(i - 1) % 300] = 0;
}
}
``````

};

/**

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

• Hang on, so if the previous timestamp is less than timestamp - 300, that means that everything up to m_iPrev is old entry and should be removed from the array, right?

• If the previous time is within timestamp - 300 and timestamp, shouldn't the entries from timestamp - 300 to prev be kept, since they are within 5 minutes? You should only be clearing out the entries older than 5 minutes, right? This is very confusing..

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