# Implement Router
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/implement-router)
Canonical: https://scaleengineer.com/dsa/problems/implement-router
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table, Ordered Set, Queue
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## Problem
Design a data structure that can efficiently manage data packets in a network router. Each data packet consists of the following attributes:

* `source`: A unique identifier for the machine that generated the packet.
* `destination`: A unique identifier for the target machine.
* `timestamp`: The time at which the packet arrived at the router.

Implement the `Router` class:

`Router(int memoryLimit)`: Initializes the Router object with a fixed memory limit.

* `memoryLimit` is the **maximum** number of packets the router can store at any given time.
* If adding a new packet would exceed this limit, the **oldest** packet must be removed to free up space.

`bool addPacket(int source, int destination, int timestamp)`: Adds a packet with the given attributes to the router.

* A packet is considered a duplicate if another packet with the same `source`, `destination`, and `timestamp` already exists in the router.
* Return `true` if the packet is successfully added (i.e., it is not a duplicate); otherwise return `false`.

`int[] forwardPacket()`: Forwards the next packet in FIFO (First In First Out) order.

* Remove the packet from storage.
* Return the packet as an array `[source, destination, timestamp]`.
* If there are no packets to forward, return an empty array.

`int getCount(int destination, int startTime, int endTime)`:

* Returns the number of packets currently stored in the router (i.e., not yet forwarded) that have the specified destination and have timestamps in the inclusive range `[startTime, endTime]`.

**Note** that queries for `addPacket` will be made in increasing order of `timestamp`.

**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**

Router router = new Router(3); // Initialize Router with memoryLimit of 3.  
router.addPacket(1, 4, 90); // Packet is added. Return True.  
router.addPacket(2, 5, 90); // Packet is added. Return True.  
router.addPacket(1, 4, 90); // This is a duplicate packet. Return False.  
router.addPacket(3, 5, 95); // Packet is added. Return True  
router.addPacket(4, 5, 105); // Packet is added, `[1, 4, 90]` is removed as number of packets exceeds memoryLimit. Return True.  
router.forwardPacket(); // Return `[2, 5, 90]` and remove it from router.  
router.addPacket(5, 2, 110); // Packet is added. Return True.  
router.getCount(5, 100, 110); // The only packet with destination 5 and timestamp in the inclusive range `[100, 110]` is `[4, 5, 105]`. Return 1.

**Example 2:**

**Input:**  
\["Router", "addPacket", "forwardPacket", "forwardPacket"\]  
\[\[2\], \[7, 4, 90\], \[\], \[\]\]

**Output:**  
\[null, true, \[7, 4, 90\], \[\]\] 

**Explanation**

Router router = new Router(2); // Initialize `Router` with `memoryLimit` of 2.  
router.addPacket(7, 4, 90); // Return True.  
router.forwardPacket(); // Return `[7, 4, 90]`.  
router.forwardPacket(); // There are no packets left, return `[]`.

**Constraints:**

* `2 <= memoryLimit <= 105`
* `1 <= source, destination <= 2 * 105`
* `1 <= timestamp <= 109`
* `1 <= startTime <= endTime <= 109`
* At most `105` calls will be made to `addPacket`, `forwardPacket`, and `getCount` methods altogether.
* queries for `addPacket` will be made in increasing order of `timestamp`.

# Approaches
## Brute Force with Queue and Set
This approach uses basic data structures to directly model the router's behavior. A queue is a natural fit for the First-In-First-Out (FIFO) nature of packet forwarding, and a set provides an efficient way to handle duplicate packet detection. While `addPacket` and `forwardPacket` operations are very fast, the `getCount` method requires a full scan of all stored packets, making it potentially slow.
**Time:** *   `addPacket`: O(1) average time.
*   `forwardPacket`: O(1) average time.
*   `getCount`: O(N) time, where N is the current number of packets in the router. · **Space:** O(N), where N is the `memoryLimit`. We store each packet in both a queue and a set.
**Pros:** Simple to understand and implement.; Extremely fast `addPacket` and `forwardPacket` operations, both running in O(1) average time.
**Cons:** `getCount` operation is inefficient with a time complexity of O(N), where N is the number of packets. This can lead to Time Limit Exceeded (TLE) errors for test cases with many `getCount` calls on a router with a large number of packets.
### Explanation
In this implementation, we use two main data structures: a `java.util.Queue` (specifically an `ArrayDeque` for efficiency) to maintain the order of packets and a `java.util.Set` (a `HashSet`) to keep track of existing packets for quick duplicate checks. A simple `Packet` record or class is defined to hold the packet's attributes.

- **Adding a packet**: We first check for duplicates using the `HashSet`. If the packet is unique, we check if the router is at its `memoryLimit`. If so, we evict the oldest packet by removing it from the front of the `Queue` and also from the `HashSet`. Finally, the new packet is added to the back of the `Queue` and to the `HashSet`.

- **Forwarding a packet**: This follows the FIFO principle. We simply remove the packet from the front of the `Queue` (if not empty) and also from the `HashSet` to keep the data structures synchronized.

- **Counting packets**: This is the brute-force part. The method iterates through every single packet currently in the `Queue` and checks if it meets the criteria (matching destination and timestamp within the specified range). While simple, this linear scan is the primary performance bottleneck of this approach.

```java
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;

class Router {
    // Using a record for an immutable Packet data carrier
    private record Packet(int source, int destination, int timestamp) {}

    private final int memoryLimit;
    private final Queue<Packet> packetQueue;
    private final Set<Packet> packetSet;

    public Router(int memoryLimit) {
        this.memoryLimit = memoryLimit;
        this.packetQueue = new LinkedList<>(); // LinkedList or ArrayDeque work well
        this.packetSet = new HashSet<>();
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        Packet newPacket = new Packet(source, destination, timestamp);
        if (packetSet.contains(newPacket)) {
            return false; // Duplicate packet
        }

        if (packetQueue.size() == memoryLimit) {
            Packet oldestPacket = packetQueue.poll();
            packetSet.remove(oldestPacket);
        }

        packetQueue.offer(newPacket);
        packetSet.add(newPacket);
        return true;
    }

    public int[] forwardPacket() {
        if (packetQueue.isEmpty()) {
            return new int[0];
        }
        Packet packetToForward = packetQueue.poll();
        packetSet.remove(packetToForward);
        return new int[]{packetToForward.source(), packetToForward.destination(), packetToForward.timestamp()};
    }

    public int getCount(int destination, int startTime, int endTime) {
        int count = 0;
        for (Packet packet : packetQueue) {
            if (packet.destination() == destination && packet.timestamp() >= startTime && packet.timestamp() <= endTime) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   **Data Structures**: Use a `java.util.Queue` (e.g., `ArrayDeque`) to store packets for FIFO order and a `java.util.Set` for O(1) duplicate checks.
*   **Packet Representation**: Create a custom `Packet` class or record with `source`, `destination`, and `timestamp` fields. Implement `equals()` and `hashCode()` for correct behavior in the `Set`.
*   **`addPacket(source, destination, timestamp)`**:
    1.  Create a `Packet` object.
    2.  Check if the packet exists in the `Set`. If yes, return `false`.
    3.  If the `Queue` size equals `memoryLimit`, remove the oldest packet by calling `poll()` on the `Queue` and `remove()` on the `Set`.
    4.  Add the new packet to the `Queue` using `offer()` and to the `Set` using `add()`.
    5.  Return `true`.
*   **`forwardPacket()`**:
    1.  If the `Queue` is empty, return an empty array.
    2.  Remove the oldest packet using `poll()` from the `Queue`.
    3.  Remove the same packet from the `Set`.
    4.  Return the packet's data.
*   **`getCount(destination, startTime, endTime)`**:
    1.  Initialize a counter to zero.
    2.  Iterate through every packet in the `Queue`.
    3.  For each packet, check if its destination and timestamp match the query parameters.
    4.  If they match, increment the counter.
    5.  Return the final count.

## Optimized with Per-Destination TreeMap
This approach enhances the brute-force solution by adding a more sophisticated data structure to accelerate `getCount` queries. We group packets by their destination using a `HashMap`, and for each destination, we store its timestamps in a `TreeMap`. A `TreeMap` is a sorted map, which allows for efficient updates and range-based queries. This makes `addPacket` and `forwardPacket` slightly slower (logarithmic time) but makes `getCount` significantly faster on average.
**Time:** *   `addPacket`: O(log N) time.
*   `forwardPacket`: O(log N) time.
*   `getCount`: O(M + log N) time, where M is the number of unique timestamps in the query range. Worst case is O(N). · **Space:** O(N), where N is the `memoryLimit`. The space is used by the queue, set, and the map of TreeMaps.
**Pros:** `addPacket` and `forwardPacket` are efficient, with O(log N) complexity.; `getCount` is much faster than the brute-force approach on average, especially for queries over small time intervals.; Provides a good balance between implementation complexity and performance.
**Cons:** The worst-case time complexity for `getCount` is still O(N) if the queried time range is large and covers all packets for a destination.; Slightly more complex to implement and uses more memory due to the additional map structure.
### Explanation
We keep the `Queue` for FIFO order and the `Set` for duplicate checks. The main enhancement is a `Map<Integer, TreeMap<Integer, Integer>> destTimestamps`. This structure organizes packets by destination, and for each destination, it keeps a sorted map of timestamps to their frequencies.

- **Adding/Forwarding Packets**: When a packet is added or removed, we perform the O(1) operations on the `Queue` and `Set`, but we also need to update our new map. We find the `TreeMap` for the packet's destination and update the count for its timestamp. Since `TreeMap` is a balanced binary search tree, adding, removing, or updating an entry takes O(log K) time, where K is the number of unique timestamps for that destination.

- **Counting Packets**: This is where the `TreeMap` shines. Instead of a linear scan of all packets, we first access the specific destination's `TreeMap` in O(1). Then, we use the `subMap` method to efficiently isolate only the timestamps within the `[startTime, endTime]` range. This operation takes O(log K). We then iterate only over this (typically much smaller) sub-map to sum the packet counts. While the worst-case still involves iterating over all K entries (making it O(K)), the average case for smaller time ranges is much improved.

```java
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;

class Router {
    private record Packet(int source, int destination, int timestamp) {}

    private final int memoryLimit;
    private final Queue<Packet> packetQueue;
    private final Set<Packet> packetSet;
    private final Map<Integer, TreeMap<Integer, Integer>> destTimestamps;

    public Router(int memoryLimit) {
        this.memoryLimit = memoryLimit;
        this.packetQueue = new LinkedList<>();
        this.packetSet = new HashSet<>();
        this.destTimestamps = new HashMap<>();
    }

    public boolean addPacket(int source, int destination, int timestamp) {
        Packet newPacket = new Packet(source, destination, timestamp);
        if (packetSet.contains(newPacket)) {
            return false;
        }

        if (packetQueue.size() == memoryLimit) {
            Packet oldestPacket = packetQueue.poll();
            packetSet.remove(oldestPacket);
            removeTimestamp(oldestPacket.destination(), oldestPacket.timestamp());
        }

        packetQueue.offer(newPacket);
        packetSet.add(newPacket);
        addTimestamp(destination, timestamp);
        return true;
    }

    public int[] forwardPacket() {
        if (packetQueue.isEmpty()) {
            return new int[0];
        }
        Packet packetToForward = packetQueue.poll();
        packetSet.remove(packetToForward);
        removeTimestamp(packetToForward.destination(), packetToForward.timestamp());
        return new int[]{packetToForward.source(), packetToForward.destination(), packetToForward.timestamp()};
    }

    public int getCount(int destination, int startTime, int endTime) {
        if (!destTimestamps.containsKey(destination)) {
            return 0;
        }
        TreeMap<Integer, Integer> timestamps = destTimestamps.get(destination);
        // Get a view of the map for the given range
        Map<Integer, Integer> subMap = timestamps.subMap(startTime, true, endTime, true);
        int count = 0;
        for (int freq : subMap.values()) {
            count += freq;
        }
        return count;
    }

    private void addTimestamp(int destination, int timestamp) {
        destTimestamps.computeIfAbsent(destination, k -> new TreeMap<>());
        TreeMap<Integer, Integer> timestamps = destTimestamps.get(destination);
        timestamps.put(timestamp, timestamps.getOrDefault(timestamp, 0) + 1);
    }

    private void removeTimestamp(int destination, int timestamp) {
        TreeMap<Integer, Integer> timestamps = destTimestamps.get(destination);
        timestamps.put(timestamp, timestamps.get(timestamp) - 1);
        if (timestamps.get(timestamp) == 0) {
            timestamps.remove(timestamp);
        }
        if (timestamps.isEmpty()) {
            destTimestamps.remove(destination);
        }
    }
}
```
### Algorithm
*   **Data Structures**: In addition to the `Queue` and `Set` from the brute-force approach, we add a `Map<Integer, TreeMap<Integer, Integer>>` named `destTimestamps`.
    *   The outer `Map`'s key is the `destination` ID.
    *   The inner `TreeMap`'s key is the `timestamp`, and its value is the count of packets for that destination at that exact timestamp.
*   **`addPacket(source, destination, timestamp)`**:
    1.  Perform duplicate check and memory limit eviction as before.
    2.  When evicting the oldest packet, locate its destination's `TreeMap` and decrement the count for its timestamp. If the count becomes zero, remove the timestamp entry from the `TreeMap`.
    3.  When adding the new packet, locate its destination's `TreeMap` (or create one) and increment the count for its timestamp.
*   **`forwardPacket()`**:
    1.  Remove the packet from the `Queue` and `Set`.
    2.  Update the `destTimestamps` map by decrementing/removing the packet's timestamp, similar to the eviction step in `addPacket`.
*   **`getCount(destination, startTime, endTime)`**:
    1.  Look up the destination in the `destTimestamps` map. If not found, return 0.
    2.  Get the corresponding `TreeMap`.
    3.  Use `TreeMap.subMap(startTime, true, endTime, true)` to get a view of the relevant timestamp range.
    4.  Iterate through the values (counts) of this sub-map and sum them up. Return the total.

## Optimal Solution with Order Statistic Tree
This represents the most theoretically efficient solution, achieving logarithmic time complexity for all router operations. It builds upon the per-destination structure of the previous approach but replaces the `TreeMap` with a more powerful data structure, an Order Statistic Tree (OST). This tree allows for counting elements within a range in logarithmic time, eliminating the final performance bottleneck of the `getCount` method.
**Time:** *   `addPacket`: O(log N) time.
*   `forwardPacket`: O(log N) time.
*   `getCount`: O(log N) time. · **Space:** O(N), where N is the `memoryLimit`.
**Pros:** Asymptotically optimal performance for all operations.; `getCount` runs in O(log N) time, which is a significant improvement over the O(N) worst-case of other approaches.; Guaranteed fast performance even with worst-case inputs.
**Cons:** High implementation complexity. Java's standard library does not provide an Order Statistic Tree, so it would need to be implemented from scratch or by using a third-party library.; The constant factors for operations might be higher than the simpler `TreeMap` approach.
### Explanation
The key to this optimal approach is using a data structure that can answer range-count queries in logarithmic time. An Order Statistic Tree is a perfect candidate.

We would structure our class with a `Map<Integer, OrderStatisticTree>`, where each destination maps to an OST that stores its timestamps. An OST, by keeping track of subtree sizes at each node, can determine the rank of any element (i.e., how many elements are smaller than or equal to it) in O(log K) time, where K is the number of elements in the tree.

With this `rank` function, `getCount` becomes trivial and fast. The number of packets with timestamps in the inclusive range `[startTime, endTime]` is simply the total count of packets with timestamps up to `endTime` minus the total count of packets with timestamps up to `startTime - 1`. This translates to `rank(endTime) - rank(startTime - 1)`.

Because both `addPacket` and `forwardPacket` also only require logarithmic-time updates to the OST, all three public methods of the `Router` class achieve a worst-case time complexity of O(log N), where N is the memory limit.

**Note**: Since `java.util` does not contain an OST, the code below is conceptual. In a competitive programming context, one might use a Fenwick Tree with coordinate compression or implement a custom balanced BST to achieve this.
### Algorithm
*   **Data Structure**: This approach replaces the `TreeMap` from the previous solution with an **Order Statistic Tree (OST)**. An OST is a balanced binary search tree (e.g., Red-Black Tree) where each node is augmented to store the size of its subtree.
*   **Core Operations of OST**: An OST supports standard BST operations (`add`, `remove`) in O(log K) time, plus a crucial `rank(x)` operation, which also runs in O(log K) and returns the number of elements in the tree less than or equal to `x`.
*   **`addPacket` / `forwardPacket`**: The logic is identical to the `TreeMap` approach, but operations are performed on the OST. Adding or removing a timestamp takes O(log K) time.
*   **`getCount(destination, startTime, endTime)`**:
    1.  Look up the destination's OST in the map.
    2.  The count of items in the range `[startTime, endTime]` is calculated as `ost.rank(endTime) - ost.rank(startTime - 1)`.
    3.  Since each `rank` query takes O(log K) time, the entire `getCount` operation is completed in O(log K) time, regardless of the range size.