Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The router needs insertion order for forwarding, exact packet identity for duplicate detection, and timestamp order within each destination for range counts. Maintain those three views together. Nondecreasing arrival timestamps make each destination's timestamp sequence sorted automatically.

Approach

Keep a global FIFO queue, a set of currently stored packet triples, and a FIFO timestamp sequence per destination. Reject an added packet if its full triple is already in the set. Otherwise, if storage is full, evict the global oldest packet and remove its set entry and the first timestamp for its destination. Then insert the new packet into all three structures.

Forwarding performs the same oldest-packet removal and returns its fields in the requested order, or an empty list when no packet exists. For getCount, subtract the lower-bound position of startTime from the upper-bound position of endTime in that destination's live timestamps. This includes both range endpoints and counts equal timestamps separately.

Global FIFO removal also removes the oldest packet for its destination, keeping the timestamp sequences synchronized. Duplicate checks apply only to packets still stored.

class Router:
    def __init__(self, memoryLimit: int):
        self.mx = memoryLimit
        self.all = deque()
        self.unique = set()
        self.dest_t = defaultdict(deque)

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        key = (destination, timestamp, source)
        if key in self.unique: return False
        
        if len(self.all) == self.mx:
            d, t, s = self.all.popleft()
            self.unique.remove((d, t, s))
            self.dest_t[d].popleft()

        self.all.append((key))
        self.unique.add(key)
        self.dest_t[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.all: return []
        d, t, s = self.all.popleft()
        self.unique.remove((d, t, s))
        self.dest_t[d].popleft()
        return [s, d, t]

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        arr = self.dest_t[destination]
        l = bisect_left(arr, startTime)
        r = bisect_right(arr, endTime)
        return r - l

# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)

Complexity analysis

Let M be the memory limit, f the live timestamp count for one destination, and D the number of destination keys. In both versions, addPacket and forwardPacket take amortized O(1) time. JavaScript getCount takes O(log(f + 1)) time using direct array indexing during binary search. The unchanged Python version bisects a deque, whose middle access can take linear time, giving O(f log(f + 1)) worst-case query time. Persistent auxiliary space is O(M + D).