Solution

Method 1 – Queue + Duplicate Set + Per-destination Timestamps (Offset + Binary Search)

Intuition

We must support three operations efficiently: insert packets in arrival order with duplicate detection, forward (pop) the oldest packet, and count how many current packets for a given destination have timestamps in a given inclusive range. Because addPacket calls come with non-decreasing timestamps, we can append timestamps per destination into a vector (or list). Removing arbitrary elements from the middle of those vectors would be expensive; instead we track how many leading timestamps have been logically removed for each destination (an "offset"). This lets us avoid expensive deletes and answer range queries by binary-searching the destination's timestamp list starting from the offset.

Key ideas:

Use a queue for FIFO order and a hash-set for duplicate detection (constant-time checks).
For each destination keep a list of timestamps appended in arrival order.
On eviction/forward, increment the destination's offset counter instead of removing from the list.
Implement getCount by performing binary search (lower/upper bound) on the per-destination timestamp list starting at the offset — this is O(log k) where k is the number of timestamps for that destination.

This matches the working Java approach and avoids TLE by preventing repeated O(n) deletions.

Approach (step-by-step)

Router(memoryLimit): store maxSize only.
addPacket(source, destination, timestamp):
- If packet is duplicate (seen set), return false.
- If capacity reached, pop from queue, remove its seen key, and increment that destination's removed counter.
- Enqueue new packet, mark seen, and append timestamp to timestamps[destination].

Related Tags