Problem statement

A network router stores data packets until it forwards them. A packet is the triple (source, destination, timestamp); two packets with the same three values are duplicates. The router holds at most memoryLimit packets and forwards them first-in, first-out.

Write the class Router:

• Router(int memoryLimit) creates an empty router.
• boolean addPacket(int source, int destination, int timestamp) stores the packet and returns true, unless a duplicate is already stored, in which case it stores nothing and returns false. If the router is full when a new packet is stored, the oldest stored packet is dropped first.
• int[] forwardPacket() removes the oldest stored packet and returns it as [source, destination, timestamp], or returns [] if the router is empty.
• int getCount(int destination, int startTime, int endTime) returns how many stored packets (not yet forwarded or dropped) have this destination and a timestamp in [startTime, endTime], both ends included.

Calls to addPacket come with non-decreasing timestamps.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["Router","addPacket","addPacket","addPacket","addPacket","addPacket","forwardPacket","addPacket","getCount"]
[[3],[1,4,90],[2,5,90],[1,4,90],[3,5,95],[4,5,105],[],[5,2,110],[5,100,110]]
Output: [null,true,true,false,true,true,[2,5,90],true,1]
Explanation: The second [1, 4, 90] is a duplicate. Adding [4, 5, 105] to a full router drops the oldest, [1, 4, 90]. Forwarding sends [2, 5, 90]. After [5, 2, 110] arrives, the stored packets for destination 5 are at 95 and 105, and only 105 is in [100, 110].

Example 2

Input: ["Router","addPacket","forwardPacket","forwardPacket","getCount"]
[[2],[7,4,1],[],[],[4,1,1000000000]]
Output: [null,true,[7,4,1],[],0]
Explanation: Once the only packet is forwarded the router is empty: the next forward returns [], and nothing is left to count.

Constraints

• 2 <= memoryLimit <= 10^5
• 1 <= source, destination <= 2 * 10^5
• 1 <= timestamp <= 10^9
• 1 <= startTime <= endTime <= 10^9
• At most 10^5 calls are made in total to addPacket, forwardPacket and getCount
• addPacket is called with timestamps in non-decreasing order

Hints for Implement Router

1. Hint 1

   Three questions need three structures: arrival order (a queue), duplicate detection (a hash set of triples), and per-destination counting.

2. Hint 2

   Because timestamps only grow, each destination's stored timestamps, in arrival order, are already sorted. A range count is two binary searches.

3. Hint 3

   Packets leave only from the front of the global queue — so for their destination they are also the earliest one stored. Keep per destination a list of timestamps plus a count of how many at its front have left.

How to solve Implement Router

Store the packets in a FIFO queue, their triples in a hash set, and for every destination the list of its timestamps in arrival order with a moving start index. Timestamps arrive sorted, so each list is sorted and getCount is a pair of binary searches over its live part.

Approach

1. addPacket(s, d, t): if (s, d, t) is in the set, return false. If the queue holds memoryLimit packets, remove the oldest (see below). Push the packet, add its triple to the set, append t to list[d], return true.
2. Removing the oldest packet (for a drop or forwardPacket): pop it from the queue, delete its triple from the set, and advance start[d] of its destination by one.
3. forwardPacket(): return [] if the queue is empty; otherwise remove the oldest packet as above and return it.
4. getCount(d, a, b): in list[d] from start[d] onwards, count the timestamps in [a, b] with a lower bound of a and an upper bound of b.

Why it works

Within one destination, packets join in arrival order and arrival order is timestamp order, so list[d] is sorted. Packets leave strictly in arrival order, so the ones of destination d that have left are exactly the first start[d] entries of list[d]; the rest are the stored ones, still sorted, which is what the binary searches need.

Complexity

• Time — O(1) for addPacket and forwardPacket (expected, for the hash set), O(log n) for getCount
• Space — O(n) for n packets added

Pitfalls

• A dropped or forwarded packet is no longer a duplicate — remove its triple from the set.
• getCount counts only stored packets; forgetting to advance the destination's start index counts packets that already left.
• The duplicate check comes before the eviction: a duplicate must not push the oldest packet out.

Reference solution

Python

from bisect import bisect_left, bisect_right
from collections import deque

class Router:

    def __init__(self, memoryLimit: int):
        self.limit = memoryLimit
        self.queue = deque()  # stored packets, oldest first
        self.keys = set()     # their (source, destination, timestamp)
        self.times = {}       # destination -> its timestamps in arrival order
        self.start = {}       # destination -> how many of those have left

    def _drop_oldest(self):
        p = self.queue.popleft()
        self.keys.discard(p)
        self.start[p[1]] += 1
        return p

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        p = (source, destination, timestamp)
        if p in self.keys:
            return False
        if len(self.queue) == self.limit:
            self._drop_oldest()
        self.queue.append(p)
        self.keys.add(p)
        self.times.setdefault(destination, []).append(timestamp)
        self.start.setdefault(destination, 0)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.queue:
            return []
        return list(self._drop_oldest())

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        ts = self.times.get(destination)
        if not ts:
            return 0
        lo = self.start[destination]
        return bisect_right(ts, endTime, lo) - bisect_left(ts, startTime, lo)

Java

class Router {
    private int limit;
    private ArrayDeque<int[]> queue = new ArrayDeque<>();       // stored packets, oldest first
    private HashSet<String> keys = new HashSet<>();               // their triples
    private HashMap<Integer, ArrayList<Integer>> times = new HashMap<>(); // destination -> timestamps
    private HashMap<Integer, Integer> start = new HashMap<>();    // destination -> how many left

    public Router(int memoryLimit) {
        limit = memoryLimit;
    }

    private static String key(int s, int d, int t) { return s + "," + d + "," + t; }

    private int[] dropOldest() {
        int[] p = queue.pollFirst();
        keys.remove(key(p[0], p[1], p[2]));
        start.merge(p[1], 1, Integer::sum);
        return p;
    }

    private static int bound(ArrayList<Integer> a, int lo, int x, boolean upper) {
        int hi = a.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            int v = a.get(mid);
            if (upper ? v <= x : v < x) lo = mid + 1; else hi = mid;
        }
        return lo;
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        if (!keys.add(key(source, destination, timestamp))) return false;
        if (queue.size() == limit) dropOldest();
        queue.addLast(new int[]{source, destination, timestamp});
        times.computeIfAbsent(destination, k -> new ArrayList<>()).add(timestamp);
        start.putIfAbsent(destination, 0);
        return true;
    }

    public int[] forwardPacket() {
        if (queue.isEmpty()) return new int[0];
        return dropOldest();
    }

    public int getCount(int destination, int startTime, int endTime) {
        ArrayList<Integer> ts = times.get(destination);
        if (ts == null) return 0;
        int lo = start.get(destination);
        return bound(ts, lo, endTime, true) - bound(ts, lo, startTime, false);
    }
}

C++

class Router {
    int limit;
    deque<array<int, 3>> q;                  // stored packets, oldest first
    set<array<int, 3>> keys;                 // their triples
    unordered_map<int, vector<int>> times;   // destination -> timestamps in arrival order
    unordered_map<int, int> start;           // destination -> how many of those have left

    array<int, 3> dropOldest() {
        array<int, 3> p = q.front();
        q.pop_front();
        keys.erase(p);
        start[p[1]]++;
        return p;
    }
public:
    Router(int memoryLimit) : limit(memoryLimit) {}

    bool addPacket(int source, int destination, int timestamp) {
        array<int, 3> p = {source, destination, timestamp};
        if (keys.count(p)) return false;
        if ((int)q.size() == limit) dropOldest();
        q.push_back(p);
        keys.insert(p);
        times[destination].push_back(timestamp);
        return true;
    }

    vector<int> forwardPacket() {
        if (q.empty()) return {};
        array<int, 3> p = dropOldest();
        return {p[0], p[1], p[2]};
    }

    int getCount(int destination, int startTime, int endTime) {
        auto it = times.find(destination);
        if (it == times.end()) return 0;
        auto b = it->second.begin() + start[destination];
        auto e = it->second.end();
        return (int)(upper_bound(b, e, endTime) - lower_bound(b, e, startTime));
    }
};

JavaScript

var Router = function(memoryLimit) {
    this.limit = memoryLimit;
    this.queue = [];      // stored packets, oldest at index head
    this.head = 0;
    this.keys = new Set(); // "source,destination,timestamp" of stored packets
    this.times = new Map(); // destination -> its timestamps in arrival order
    this.start = new Map(); // destination -> how many of those have left
};

function rtBound(a, lo, x, upper) { // first index >= lo with a[i] > x (upper) or >= x
    var hi = a.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (upper ? a[mid] <= x : a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

Router.prototype.dropOldest = function() {
    var p = this.queue[this.head++];
    this.keys.delete(p[0] + "," + p[1] + "," + p[2]);
    this.start.set(p[1], this.start.get(p[1]) + 1);
    return p;
};

Router.prototype.addPacket = function(source, destination, timestamp) {
    var key = source + "," + destination + "," + timestamp;
    if (this.keys.has(key)) return false;
    if (this.queue.length - this.head === this.limit) this.dropOldest();
    this.queue.push([source, destination, timestamp]);
    this.keys.add(key);
    if (!this.times.has(destination)) { this.times.set(destination, []); this.start.set(destination, 0); }
    this.times.get(destination).push(timestamp);
    return true;
};

Router.prototype.forwardPacket = function() {
    if (this.head === this.queue.length) return [];
    return this.dropOldest();
};

Router.prototype.getCount = function(destination, startTime, endTime) {
    var ts = this.times.get(destination);
    if (!ts) return 0;
    var lo = this.start.get(destination);
    return rtBound(ts, lo, endTime, true) - rtBound(ts, lo, startTime, false);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium
• Simple Bank System Medium