Implement router

Array Hash Table Binary Search Design Queue Ordered Set

39.1% acceptance

Feb 24, 2026

479

116

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.

Solution

Rust

Time O(log n)

Space O(n)

LeetCode

solution.rs

// Optimization: since addPacket timestamps are globally non-decreasing, each
// per-destination VecDeque is also sorted. Binary search replaces BTreeMap,
// eviction is O(1) pop_front, and insert is O(1) push_back with better cache
// locality. Duplicate key is packed into u64 for faster hashing.
use std::collections::{HashMap, HashSet, VecDeque};

struct Router {
  memory_limit: usize,
  queue: VecDeque<(i32, i32, i32)>,
  seen: HashSet<u64>,
  per_dest: HashMap<i32, VecDeque<i32>>,
}

#[inline]
fn pack(source: i32, destination: i32, timestamp: i32) -> u64 {
  // source, destination <= 2*10^5 < 2^18; timestamp <= 10^9 < 2^30
  // pack: [ts 30 bits][dest 18 bits][src 17 bits] — safe since src/dest <= 200000 < 2^18
  (source as u64) | ((destination as u64) << 18) | ((timestamp as u64) << 36)
}

#[inline]
fn range_count(dq: &VecDeque<i32>, lo: i32, hi: i32) -> i32 {
  let (s0, s1) = dq.as_slices();
  slice_count(s0, lo, hi) + slice_count(s1, lo, hi)
}

#[inline]
fn slice_count(s: &[i32], lo: i32, hi: i32) -> i32 {
  let l = s.partition_point(|&x| x < lo);
  let r = s.partition_point(|&x| x <= hi);
  (r - l) as i32
}

impl Router {
  fn new(memory_limit: i32) -> Self {
    Self {
      memory_limit: memory_limit as usize,
      queue: VecDeque::new(),
      seen: HashSet::new(),
      per_dest: HashMap::new(),
    }
  }

  fn add_packet(&mut self, source: i32, destination: i32, timestamp: i32) -> bool {
    if !self.seen.insert(pack(source, destination, timestamp)) {
      return false;
    }
    if self.queue.len() == self.memory_limit {
      let (os, od, ot) = self.queue.pop_front().unwrap();
      self.seen.remove(&pack(os, od, ot));
      if let Some(dq) = self.per_dest.get_mut(&od) {
        dq.pop_front();
      }
    }
    self.queue.push_back((source, destination, timestamp));
    self.per_dest.entry(destination).or_default().push_back(timestamp);
    true
  }

  fn forward_packet(&mut self) -> Vec<i32> {
    if let Some((src, dest, ts)) = self.queue.pop_front() {
      self.seen.remove(&pack(src, dest, ts));
      if let Some(dq) = self.per_dest.get_mut(&dest) {
        dq.pop_front();
      }
      vec![src, dest, ts]
    } else {
      vec![]
    }
  }

  fn get_count(&self, destination: i32, start_time: i32, end_time: i32) -> i32 {
    self.per_dest
      .get(&destination)
      .map(|dq| range_count(dq, start_time, end_time))
      .unwrap_or(0)
  }
}