3508. Implement Router LeetCode Solution

In this guide, you will get 3508. Implement Router LeetCode Solution with the best time and space complexity. The solution to Implement Router problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Implement Router solution in C++
4. Implement Router solution in Java
5. Implement Router solution in Python
6. Additional Resources

Problem Statement of Implement Router

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.

Complexity Analysis

• Time Complexity: O(\log n)
• Space Complexity: int)}|)

3508. Implement Router LeetCode Solution in C++

struct Packet {
  int source;
  int destination;
  int timestamp;

  bool operator<(const Packet& other) const {
    return source < other.source ||
           (source == other.source && destination < other.destination) ||
           (source == other.source && destination == other.destination &&
            timestamp < other.timestamp);
  }
};

class Router {
 public:
  Router(int memoryLimit) : memoryLimit(memoryLimit) {}

  bool addPacket(int source, int destination, int timestamp) {
    const Packet packet{source, destination, timestamp};
    if (uniquePackets.find(packet) != uniquePackets.end())
      return false;
    if (packetQueue.size() == memoryLimit)
      forwardPacket();
    packetQueue.push(packet);
    uniquePackets.insert(packet);
    destinationTimestamps[destination].push_back(timestamp);
    return true;
  }

  vector<int> forwardPacket() {
    if (packetQueue.empty())
      return {};
    const Packet nextPacket = packetQueue.front();
    packetQueue.pop();
    uniquePackets.erase(nextPacket);
    ++processedPacketIndex[nextPacket.destination];
    return {nextPacket.source, nextPacket.destination, nextPacket.timestamp};
  }

  int getCount(int destination, int startTime, int endTime) {
    if (destinationTimestamps.find(destination) == destinationTimestamps.end())
      return 0;
    const vector<int>& timestamps = destinationTimestamps[destination];
    const int startIndex = processedPacketIndex[destination];
    const auto lowerBound = lower_bound(timestamps.begin() + startIndex,
                                        timestamps.end(), startTime);
    const auto upperBound =
        upper_bound(timestamps.begin() + startIndex, timestamps.end(), endTime);
    return upperBound - lowerBound;
  }

 private:
  const int memoryLimit;
  set<Packet> uniquePackets;
  queue<Packet> packetQueue;
  map<int, vector<int>> destinationTimestamps;
  map<int, int> processedPacketIndex;
};
/* code provided by PROGIEZ */

3508. Implement Router LeetCode Solution in Java

class Packet implements Comparable<Packet> {
  public int source;
  public int destination;
  public int timestamp;

  public Packet(int source, int destination, int timestamp) {
    this.source = source;
    this.destination = destination;
    this.timestamp = timestamp;
  }

  @Override
  public int compareTo(Packet other) {
    if (source != other.source)
      return Integer.compare(source, other.source);
    if (destination != other.destination)
      return Integer.compare(destination, other.destination);
    return Integer.compare(timestamp, other.timestamp);
  }

  @Override
  public boolean equals(Object o) {
    if (this == o)
      return true;
    if (o == null || getClass() != o.getClass())
      return false;
    Packet packet = (Packet) o;
    return source == packet.source && destination == packet.destination &&
        timestamp == packet.timestamp;
  }

  @Override
  public int hashCode() {
    return Objects.hash(source, destination, timestamp);
  }
}

class Router {
  public Router(int memoryLimit) {
    this.memoryLimit = memoryLimit;
  }

  public boolean addPacket(int source, int destination, int timestamp) {
    Packet packet = new Packet(source, destination, timestamp);
    if (uniquePackets.contains(packet))
      return false;
    if (packetQueue.size() == memoryLimit)
      forwardPacket();
    packetQueue.add(packet);
    uniquePackets.add(packet);
    destinationTimestamps.computeIfAbsent(destination, k -> new ArrayList<>()).add(timestamp);
    return true;
  }

  public List<Integer> forwardPacket() {
    if (packetQueue.isEmpty())
      return Collections.emptyList();
    Packet nextPacket = packetQueue.poll();
    uniquePackets.remove(nextPacket);
    processedPacketIndex.merge(nextPacket.destination, 1, Integer::sum);
    return Arrays.asList(nextPacket.source, nextPacket.destination, nextPacket.timestamp);
  }

  public int getCount(int destination, int startTime, int endTime) {
    if (!destinationTimestamps.containsKey(destination))
      return 0;
    List<Integer> timestamps = destinationTimestamps.get(destination);
    final int startIndex = processedPacketIndex.getOrDefault(destination, 0);
    final int lowerBoundIndex = firstGreaterEqual(timestamps, startIndex, startTime);
    final int upperBoundIndex = firstGreater(timestamps, lowerBoundIndex, endTime);
    return upperBoundIndex - lowerBoundIndex;
  }

  private final int memoryLimit;
  private final TreeSet<Packet> uniquePackets = new TreeSet<>();
  private final Queue<Packet> packetQueue = new LinkedList<>();
  private final Map<Integer, List<Integer>> destinationTimestamps = new HashMap<>();
  private final Map<Integer, Integer> processedPacketIndex = new HashMap<>();

  private int firstGreaterEqual(List<Integer> timestamps, int startIndex, int startTime) {
    int l = startIndex;
    int r = timestamps.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (timestamps.get(m) >= startTime)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }

  private int firstGreater(List<Integer> timestamps, int startIndex, int endTime) {
    int l = startIndex;
    int r = timestamps.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (timestamps.get(m) > endTime)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
// code provided by PROGIEZ

3508. Implement Router LeetCode Solution in Python

from dataclasses import dataclass


@dataclass(frozen=True)
class Packet:
  source: int
  destination: int
  timestamp: int


class Router:
  def __init__(self, memoryLimit: int):
    self.memoryLimit = memoryLimit
    self.uniquePackets: set[Packet] = set()
    self.packetQueue: collections.deque[Packet] = collections.deque()
    self.destinationTimestamps = collections.defaultdict(list)
    self.processedPacketIndex = collections.Counter()

  def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
    packet = Packet(source, destination, timestamp)
    if packet in self.uniquePackets:
      return False
    if len(self.packetQueue) == self.memoryLimit:
      self.forwardPacket()
    self.packetQueue.append(packet)
    self.uniquePackets.add(packet)
    if destination not in self.destinationTimestamps:
      self.destinationTimestamps[destination] = []
    self.destinationTimestamps[destination].append(timestamp)
    return True

  def forwardPacket(self) -> list[int]:
    if not self.packetQueue:
      return []
    nextPacket = self.packetQueue.popleft()
    self.uniquePackets.remove(nextPacket)
    self.processedPacketIndex[nextPacket.destination] += 1
    return [nextPacket.source, nextPacket.destination, nextPacket.timestamp]

  def getCount(self, destination: int, startTime: int, endTime: int) -> int:
    if destination not in self.destinationTimestamps:
      return 0
    timestamps = self.destinationTimestamps[destination]
    startIndex = self.processedPacketIndex.get(destination, 0)
    lowerBound = bisect.bisect_left(timestamps, startTime, startIndex)
    upperBound = bisect.bisect_right(timestamps, endTime, startIndex)
    return upperBound - lowerBound
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.