Skip to main content
Talentd

Implement Router - Solution & Explanation

MediumArrayHash TableBinary SearchDesign17 min readAsked at: Amazon, Microsoft, Cisco +1
Practice this problem

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.

  • 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 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); // 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 non-decreasing order of timestamp.

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.

Solution

We use a hash map vis to store the hash values of packets that have already been added, a queue q to store the packets currently in the router, a hash map idx to record the number of packets already forwarded for each destination, and a hash map d to store the list of timestamps for each destination.

For the addPacket method, we compute the hash value of the packet. If it already exists in vis, we return false; otherwise, we add it to vis, check if the current queue size exceeds the memory limit, and if so, call the forwardPacket method to remove the oldest packet. Then, we add the new packet to the queue and append its timestamp to the corresponding destination's timestamp list, finally returning true. The time complexity is O(1).

For the forwardPacket method, if the queue is empty, we return an empty array; otherwise, we remove the packet at the head of the queue, delete its hash value from vis, update the number of forwarded packets for the corresponding destination, and return the packet. The time complexity is O(1).

For the getCount method, we get the timestamp list and the number of forwarded packets for the given destination, then use binary search to find the number of timestamps within the specified range, and return that count. The time complexity is O(log n), where n is the length of the timestamp list.

The space complexity is O(n).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Array ScanInsert: O(1), Query: O(n)O(n)Small datasets or quick prototype implementations
Hash Map + Queue + Binary SearchInsert: O(1), Query: O(log n)O(n)General case with frequent range queries and ordered packet processing

Video Solution

Implement Router | Detailed Analysis | Leetcode 3508 | codestorywithMIK • codestorywithMIK • 8,120 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Implement Router easy or hard?
Implement Router is generally considered a Medium difficulty problem. The operations themselves are straightforward, but choosing the correct combination of data structures—queue for ordering and binary search over timestamp lists for fast queries—makes the difference between a naive and optimal solution.
Implement Router Python/Java solution
Most implementations follow the same structure across languages. Maintain a queue for packet order and a hash map from destination to a list of timestamps. Use built-in binary search utilities such as bisect in Python or Collections.binarySearch / custom lowerBound logic in Java.
How to solve Implement Router in O(log n)?
Store packet timestamps per destination in a sorted list using a hash map. When answering a query for a time window, apply binary search to find the left boundary (first timestamp >= start) and right boundary (first timestamp > end). The difference between the indices gives the number of packets, producing O(log n) query time.
What is the best approach for Implement Router?
The most efficient approach uses a combination of Hash Map, Queue, and Binary Search. The queue maintains packet order for forwarding operations, while a hash map groups packet timestamps by destination. Binary search on the timestamp list allows counting packets in a time range in O(log n) time.
Is Implement Router asked at Google/Amazon/Meta?
Router-style design problems appear frequently in system design and data structure interviews at large tech companies. Variants involving queues, timestamp indexing, and efficient range queries are common at companies like Amazon and Meta because they test practical data structure composition.
What data structure is used in Implement Router?
The typical implementation combines several structures: a queue to process packets in arrival order, a hash table mapping destinations to packet timestamps, and binary search over sorted timestamp arrays to answer range queries efficiently.
What is the time complexity of Implement Router?
Using the optimized design, packet insertion is O(1) amortized because timestamps are appended to a list and packets are pushed into a queue. Range queries use binary search and run in O(log n). Space complexity is O(n) because all packet metadata must be stored.

Ready to solve this problem?

Practice Implement Router with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays