In this problem, we need some way to maintain all the messages in the last 10 seconds so that we can tell whether each new message would send the number over 5. In that case, we would reject it, but otherwise we could accept it. To do this, we can maintain a queue of integers, where each integer is a time. This will be a monotonic queue in time, where the front of the queue is the oldest element, and the back of the queue is the newest. Every time we get a new message, we should first pop all messages older than 10 seconds, as we only care about the number within that range. Then, we can check the size of our queue. If it is more than 5, we can print DENIED, otherwise print ACCEPTED. Finally, we can push the new time to the end of the queue.

Additionally, instead of using a collections.dequeue or queue.Queue, many Python competitors chose to use a list along with pop(0) to remove from the front. It should be noted that popping from the front of a list is ~O(n)~, which is slower than ~O(1)~ with a queue, but it still worked in this case.

The time complexity of the queue solution is ~O(n)~. While we might pop out ~n~ old messages from the queue and there are ~n~ iterations, this will still be ~O(n)~ amortized as each of the ~n~ messages are only pushed and popped once. The space complexity is ~O(1)~, as the queue never has reason to grow beyond 5 in size.

C++ solution:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;

    queue<int> q;
    int x;
    while (n--) {
        cin >> x;
        while (!q.empty() && x - q.front() > 10)
            q.pop();
        if (q.size() < 5) {
            cout << "ACCEPTED\n";
            q.push(x);
        }
        else
            cout << "DENIED\n";
    }
}

Python solution:

from collections import deque

q = deque() 

n = int(input())

for _ in range(n):
    x = int(input())
    while q and x - q[0] > 10:
        q.popleft()
    if len(q) < 5:
        print("ACCEPTED")
        q.append(x)
    else:
        print("DENIED")