LeetCode Solutions Blog

Implement Router

Number: 3827

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Design a Router data structure that stores data packets with attributes source, destination, and timestamp. The router has a fixed memory limit; if adding a new packet exceeds this limit, the oldest packet is removed. Duplicate packets (with the same source, destination, and timestamp) should not be added. In addition, the router supports forwarding (removing the oldest packet in FIFO order) and counting how many packets with a given destination have timestamps in a specified inclusive range.

Key Insights

Use a FIFO queue to store packets in the order they arrive.
Maintain a set of packet identifiers (source, destination, timestamp) for quick duplicate detection.
Use an auxiliary mapping from destination to a sorted list of timestamps to support range queries efficiently.
When the memory limit is reached, remove the oldest packet from both the queue and the auxiliary data structures.
Since packets are added in increasing order of timestamp, the timestamp lists for each destination will naturally be sorted.

Space and Time Complexity

Time Complexity:

addPacket: O(1) for addition + O(log n) for insertion in the destination list (if using binary search for insertion, but here we append since timestamps are non-decreasing) = O(1)
forwardPacket: O(1) for queue removal, O(1) for removal from auxiliary structure if done from the beginning.
getCount: O(log m) per query on the list for the given destination where m is the number of packets with that destination. Space Complexity:
O(memoryLimit) for storing the packets in the queue, set, and auxiliary mapping.

Solution

We maintain three main data structures:

A FIFO queue (e.g. deque) to store the packets.
A set that holds tuples (source, destination, timestamp) to quickly check for duplicates.
A dictionary (or hashmap) mapping each destination to a list of timestamps. Since packets are added in non-decreasing order of timestamp, we can simply append new timestamps. For delete operations (which always remove the oldest packet), we remove from the beginning of the list. When adding a new packet, if the memory limit is reached, we remove the oldest packet from all three data structures. The getCount function uses binary search over the list of timestamps for the specified destination to count packets within the given time range.

Code Solutions

from collections import deque
import bisect

class Router:
    def __init__(self, memoryLimit: int):
        # Initialize the router with a fixed memory limit.
        self.memory_limit = memoryLimit
        # Queue to store packets in FIFO order. Each element is a tuple (source, destination, timestamp).
        self.packet_queue = deque()
        # Set to store unique packets for duplicate detection.
        self.packet_set = set()
        # Dictionary mapping destination -> list of timestamps (sorted as they are added in non-decreasing order).
        self.dest_dict = {}
        
    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        # Create a key for the packet.
        packet_key = (source, destination, timestamp)
        # If the packet is already present, it's a duplicate.
        if packet_key in self.packet_set:
            return False
        
        # Check if adding the new packet would exceed memory limit.
        if len(self.packet_queue) >= self.memory_limit:
            # Remove the oldest packet.
            self._remove_oldest_packet()
            
        # Add the packet to the queue and set.
        self.packet_queue.append(packet_key)
        self.packet_set.add(packet_key)
        
        # Add the timestamp to the dictionary mapping for the destination.
        if destination not in self.dest_dict:
            self.dest_dict[destination] = []
        # Since packets arrive in non-decreasing timestamp order, we can simply append.
        self.dest_dict[destination].append(timestamp)
        
        return True
        
    def forwardPacket(self) -> list:
        # If there are no packets to forward, return an empty list.
        if not self.packet_queue:
            return []
        # Remove the oldest packet from the queue.
        source, destination, timestamp = self.packet_queue.popleft()
        packet_key = (source, destination, timestamp)
        # Remove from duplicate set.
        self.packet_set.remove(packet_key)
        
        # Remove the timestamp from the destination dictionary.
        # Since the timestamps are stored in order, the oldest should be at index 0.
        if destination in self.dest_dict and self.dest_dict[destination]:
            # Remove from the start of the list.
            if self.dest_dict[destination][0] == timestamp:
                self.dest_dict[destination].pop(0)
            else:
                # In a rare case if the timestamp is not at start (should not happen in FIFO order), remove by value.
                self.dest_dict[destination].remove(timestamp)
                
        return [source, destination, timestamp]
    
    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        if destination not in self.dest_dict:
            return 0
        timestamps = self.dest_dict[destination]
        
        # Use bisect to find left and right indices.
        left = bisect.bisect_left(timestamps, startTime)
        right = bisect.bisect_right(timestamps, endTime)
        return right - left
    
    def _remove_oldest_packet(self):
        # Helper function to remove the oldest packet when memory limit is reached.
        if self.packet_queue:
            source, destination, timestamp = self.packet_queue.popleft()
            packet_key = (source, destination, timestamp)
            self.packet_set.remove(packet_key)
            # Remove the timestamp from the corresponding destination list.
            if destination in self.dest_dict and self.dest_dict[destination]:
                if self.dest_dict[destination][0] == timestamp:
                    self.dest_dict[destination].pop(0)
                else:
                    self.dest_dict[destination].remove(timestamp)

# Example usage:
# router = Router(3)
# print(router.addPacket(1, 4, 90))  # True
# print(router.addPacket(2, 5, 90))  # True
# print(router.addPacket(1, 4, 90))  # False (duplicate)
# print(router.addPacket(3, 5, 95))  # True
# print(router.addPacket(4, 5, 105)) # True, and oldest packet removed.
# print(router.forwardPacket())      # [2, 5, 90]
# print(router.addPacket(5, 2, 110))  # True
# print(router.getCount(5, 100, 110)) # 1