Implement Router - Video Solutions
Implement Router | Detailed Analysis | Leetcode 3508 | codestorywithMIK
Implement Router - Video Solution
Watch 10 video solutions for Implement Router, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by codestorywithMIK has 8,120 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
memoryLimitis 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, andtimestampalready exists in the router. - Return
trueif the packet is successfully added (i.e., it is not a duplicate); otherwise returnfalse.
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 non-decreasing 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); // InitializeRouter 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 <= 1051 <= source, destination <= 2 * 1051 <= timestamp <= 1091 <= startTime <= endTime <= 109- At most
105calls will be made toaddPacket,forwardPacket, andgetCountmethods altogether. - queries for
addPacketwill be made in non-decreasing order oftimestamp.
Approach Overview
Problem Overview: Design a router that receives packets, processes them in order, and answers queries about packets routed to specific destinations within a time range. The challenge is maintaining insertion order for forwarding while also supporting fast lookups for historical queries.
Approach 1: Naive Packet Storage (O(n) query time, O(n) space)
The simplest implementation stores all packets in an array as they arrive. Each query scans the entire list and counts packets that match the destination and fall within the requested time window. Forwarding packets is easy because you process them in order using a pointer or by removing from the front. The downside is query performance—every query requires iterating through all stored packets, resulting in O(n) time per query and poor scalability when packet volume grows.
Approach 2: Hash Map + Queue + Binary Search (O(log n) query, O(n) space)
A more efficient design separates responsibilities across multiple data structures. A queue maintains packets in arrival order so forwarding operations always process the earliest packet in O(1) time. A hash table maps each destination to a sorted list of packet timestamps. When a packet arrives, push it into the queue and append its timestamp to the destination's list.
Queries become fast because timestamps for each destination are already sorted. Use binary search to find the first timestamp >= startTime and the first timestamp > endTime. The difference between these indices gives the number of packets in the requested range. Each query runs in O(log n) time while insertions remain O(1) amortized.
This structure also works well when packets are forwarded or removed. Since the queue tracks order and the timestamp arrays remain sorted by insertion time, the router can maintain consistency while keeping operations efficient.
Recommended for interviews: The Hash Map + Queue + Binary Search design is the expected solution. It demonstrates the ability to combine multiple data structures—queue for ordering, hash map for grouping, and binary search for fast range queries. A brute force scan shows baseline understanding, but the optimized structure highlights strong system design and algorithmic thinking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Array Scan | Insert: O(1), Query: O(n) | O(n) | Small datasets or quick prototype implementations |
| Hash Map + Queue + Binary Search | Insert: O(1), Query: O(log n) | O(n) | General case with frequent range queries and ordered packet processing |