Implement Router

Problem

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.

Examples

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 <= 10^5
• 1 <= source, destination <= 2 * 10^5
• 1 <= timestamp <= 10^9
• 1 <= startTime <= endTime <= 10^9
• 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.

Solution

Method 1 – Queue + Duplicate Set + Per-destination Timestamps (Offset + Binary Search)

Intuition

We must support three operations efficiently: insert packets in arrival order with duplicate detection, forward (pop) the oldest packet, and count how many current packets for a given destination have timestamps in a given inclusive range. Because addPacket calls come with non-decreasing timestamps, we can append timestamps per destination into a vector (or list). Removing arbitrary elements from the middle of those vectors would be expensive; instead we track how many leading timestamps have been logically removed for each destination (an "offset"). This lets us avoid expensive deletes and answer range queries by binary-searching the destination's timestamp list starting from the offset.

Key ideas:

• Use a queue for FIFO order and a hash-set for duplicate detection (constant-time checks).
• For each destination keep a list of timestamps appended in arrival order.
• On eviction/forward, increment the destination's offset counter instead of removing from the list.
• Implement getCount by performing binary search (lower/upper bound) on the per-destination timestamp list starting at the offset — this is O(log k) where k is the number of timestamps for that destination.

This matches the working Java approach and avoids TLE by preventing repeated O(n) deletions.

Approach (step-by-step)

1. Router(memoryLimit): store maxSize only.
2. addPacket(source, destination, timestamp):
   • If packet is duplicate (seen set), return false.
   • If capacity reached, pop from queue, remove its seen key, and increment that destination's removed counter.
   • Enqueue new packet, mark seen, and append timestamp to timestamps[destination].
3. forwardPacket(): pop from queue; if empty return empty array; otherwise remove seen key and increment that destination's removed counter; return the packet array.
4. getCount(destination, startTime, endTime):
   • If no timestamps for destination, return 0.
   • Let off = removed[destination] (default 0).
   • Do lo = lowerBound(list, startTime, off) and hi = upperBound(list, endTime, off); return max(0, hi - lo).

Code

C++

#include <bits/stdc++.h>
using namespace std;

class Router {
    int maxSize;
    queue<array<int,3>> q;
    unordered_set<string> seen;
    unordered_map<int, vector<int>> timestamps; // dest -> timestamps (non-decreasing)
    unordered_map<int, int> removed; // dest -> offset

    string key(int s, int d, int t) { return to_string(s)+"#"+to_string(d)+"#"+to_string(t); }
public:
    Router(int memoryLimit): maxSize(memoryLimit) {}

    bool addPacket(int source, int destination, int timestamp) {
        string k = key(source, destination, timestamp);
        if (seen.count(k)) return false;
        if ((int)q.size() == maxSize) {
            auto old = q.front(); q.pop();
            seen.erase(key(old[0], old[1], old[2]));
            removed[old[1]]++;
        }
        q.push({source, destination, timestamp});
        seen.insert(k);
        timestamps[destination].push_back(timestamp);
        return true;
    }

    vector<int> forwardPacket() {
        if (q.empty()) return {};
        auto p = q.front(); q.pop();
        seen.erase(key(p[0], p[1], p[2]));
        removed[p[1]]++;
        return {p[0], p[1], p[2]};
    }

    int getCount(int destination, int startTime, int endTime) {
        auto it = timestamps.find(destination);
        if (it == timestamps.end()) return 0;
        auto &vec = it->second;
        int off = removed[destination];
        int lo = lower_bound(vec.begin()+off, vec.end(), startTime) - vec.begin();
        int hi = upper_bound(vec.begin()+off, vec.end(), endTime) - vec.begin();
        return max(0, hi - lo);
    }
};

Go

package main

type packet struct{src, dst, ts int}

type Router struct {
    mem int
    q   []packet
    seen map[[3]int]struct{}
    timestamps map[int][]int // dest -> timestamps
    removed map[int]int // dest -> offset
}

func Constructor(memoryLimit int) Router {
    return Router{mem: memoryLimit, seen: map[[3]int]struct{}{}, timestamps: map[int][]int{}, removed: map[int]int{}}
}

func (r *Router) AddPacket(source, destination, timestamp int) bool {
    k := [3]int{source, destination, timestamp}
    if _, ok := r.seen[k]; ok { return false }
    if len(r.q) == r.mem {
        old := r.q[0]
        r.q = r.q[1:]
        delete(r.seen, [3]int{old.src, old.dst, old.ts})
        r.removed[old.dst]++
    }
    r.q = append(r.q, packet{source, destination, timestamp})
    r.seen[k] = struct{}{}
    r.timestamps[destination] = append(r.timestamps[destination], timestamp)
    return true
}

func (r *Router) ForwardPacket() []int {
    if len(r.q) == 0 { return []int{} }
    p := r.q[0]
    r.q = r.q[1:]
    delete(r.seen, [3]int{p.src, p.dst, p.ts})
    r.removed[p.dst]++
    return []int{p.src, p.dst, p.ts}
}

func lowerBound(a []int, target, start int) int {
    l := start; r := len(a)
    for l < r {
        m := (l + r) / 2
        if a[m] < target { l = m + 1 } else { r = m }
    }
    return l
}

func upperBound(a []int, target, start int) int {
    l := start; r := len(a)
    for l < r {
        m := (l + r) / 2
        if a[m] <= target { l = m + 1 } else { r = m }
    }
    return l
}

func (r *Router) GetCount(destination, startTime, endTime int) int {
    vec, ok := r.timestamps[destination]
    if !ok { return 0 }
    off := r.removed[destination]
    lo := lowerBound(vec, startTime, off)
    hi := upperBound(vec, endTime, off)
    if hi < lo { return 0 }
    return hi - lo
}

Java

import java.util.*;

class Router {
    private int maxSize;
    private Queue<int[]> queue = new LinkedList<>();
    private Set<String> seen = new HashSet<>(); // duplicate check using string key
    private Map<Integer, List<Integer>> timestamps = new HashMap<>(); // destination -> list of timestamps
    private Map<Integer, Integer> removed = new HashMap<>(); // destination -> how many leading timestamps were removed

    private String key(int s, int d, int t) { return s + "#" + d + "#" + t; }

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

    public boolean addPacket(int source, int destination, int timestamp) {
        String k = key(source, destination, timestamp);
        if (seen.contains(k)) return false;
        if (queue.size() == maxSize) {
            int[] old = queue.poll();
            seen.remove(key(old[0], old[1], old[2]));
            removed.put(old[1], removed.getOrDefault(old[1], 0) + 1);
        }
        queue.offer(new int[]{source, destination, timestamp});
        seen.add(k);
        timestamps.computeIfAbsent(destination, x -> new ArrayList<>()).add(timestamp);
        return true;
    }

    public int[] forwardPacket() {
        if (queue.isEmpty()) return new int[0];
        int[] p = queue.poll();
        seen.remove(key(p[0], p[1], p[2]));
        removed.put(p[1], removed.getOrDefault(p[1], 0) + 1);
        return p;
    }

    public int getCount(int destination, int startTime, int endTime) {
        List<Integer> list = timestamps.get(destination);
        if (list == null) return 0;
        int off = removed.getOrDefault(destination, 0);
        int lo = lowerBound(list, startTime, off);
        int hi = upperBound(list, endTime, off);
        return Math.max(0, hi - lo);
    }

    private int lowerBound(List<Integer> a, int target, int start) {
        int l = start, r = a.size();
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a.get(m) < target) l = m + 1; else r = m;
        }
        return l;
    }

    private int upperBound(List<Integer> a, int target, int start) {
        int l = start, r = a.size();
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a.get(m) <= target) l = m + 1; else r = m;
        }
        return l;
    }
}

Kotlin

class Router(private val mem: Int) {
    private val q = ArrayDeque<Triple<Int, Int, Int>>()
    private val s = mutableSetOf<Triple<Int, Int, Int>>()
    private val timestamps = mutableMapOf<Int, MutableList<Int>>()
    private val removed = mutableMapOf<Int, Int>()

    fun addPacket(source: Int, destination: Int, timestamp: Int): Boolean {
        val key = Triple(source, destination, timestamp)
        if (key in s) return false
        if (q.size == mem) {
            val old = q.removeFirst()
            s.remove(old)
            removed[old.second] = removed.getOrDefault(old.second, 0) + 1
        }
        q.addLast(key)
        s.add(key)
        timestamps.computeIfAbsent(destination) { mutableListOf() }.add(timestamp)
        return true
    }

    fun forwardPacket(): IntArray {
        if (q.isEmpty()) return IntArray(0)
        val pkt = q.removeFirst()
        s.remove(pkt)
        removed[pkt.second] = removed.getOrDefault(pkt.second, 0) + 1
        return intArrayOf(pkt.first, pkt.second, pkt.third)
    }

    fun getCount(destination: Int, startTime: Int, endTime: Int): Int {
        val vec = timestamps[destination] ?: return 0
        val off = removed.getOrDefault(destination, 0)
        val lo = lowerBound(vec, startTime, off)
        val hi = upperBound(vec, endTime, off)
        return maxOf(0, hi - lo)
    }

    private fun lowerBound(a: List<Int>, target: Int, start: Int): Int {
        var l = start; var r = a.size
        while (l < r) {
            val m = (l + r) ushr 1
            if (a[m] < target) l = m + 1 else r = m
        }
        return l
    }

    private fun upperBound(a: List<Int>, target: Int, start: Int): Int {
        var l = start; var r = a.size
        while (l < r) {
            val m = (l + r) ushr 1
            if (a[m] <= target) l = m + 1 else r = m
        }
        return l
    }
}

Python

from collections import deque, defaultdict

class Router:
    def __init__(self, memoryLimit: int):
        self.mem = memoryLimit
        self.q = deque()
        self.seen = set()
        self.timestamps = defaultdict(list)  # dest -> list of timestamps
        self.removed = defaultdict(int)      # dest -> offset

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        key = (source, destination, timestamp)
        if key in self.seen: return False
        if len(self.q) == self.mem:
            old = self.q.popleft()
            self.seen.remove(old)
            _, dst_o, _ = old
            self.removed[dst_o] += 1
        self.q.append(key)
        self.seen.add(key)
        self.timestamps[destination].append(timestamp)
        return True

    def forwardPacket(self) -> list:
        if not self.q: return []
        src, dst, t = self.q.popleft()
        self.seen.remove((src, dst, t))
        self.removed[dst] += 1
        return [src, dst, t]

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        vec = self.timestamps.get(destination)
        if not vec: return 0
        off = self.removed.get(destination, 0)
        lo = self._lower_bound(vec, startTime, off)
        hi = self._upper_bound(vec, endTime, off)
        return max(0, hi - lo)

    def _lower_bound(self, a, target, start):
        l, r = start, len(a)
        while l < r:
            m = (l + r) // 2
            if a[m] < target: l = m + 1
            else: r = m
        return l

    def _upper_bound(self, a, target, start):
        l, r = start, len(a)
        while l < r:
            m = (l + r) // 2
            if a[m] <= target: l = m + 1
            else: r = m
        return l

Rust

use std::collections::{VecDeque, HashMap, HashSet};

pub struct Router {
    mem: usize,
    q: VecDeque<(i32, i32, i32)>,
    seen: HashSet<(i32, i32, i32)>,
    timestamps: HashMap<i32, Vec<i32>>,
    removed: HashMap<i32, usize>,
}

impl Router {
    pub fn new(memory_limit: i32) -> Self {
        let mem = if memory_limit < 0 { 0usize } else { memory_limit as usize };
        Router {
            mem,
            q: VecDeque::new(),
            seen: HashSet::new(),
            timestamps: HashMap::new(),
            removed: HashMap::new(),
        }
    }

    pub fn add_packet(&mut self, source: i32, destination: i32, timestamp: i32) -> bool {
        let key = (source, destination, timestamp);
        if self.seen.contains(&key) { return false; }
        if self.q.len() == self.mem {
            if let Some(old) = self.q.pop_front() {
                self.seen.remove(&old);
                *self.removed.entry(old.1).or_insert(0) += 1;
            }
        }
        self.q.push_back(key);
        self.seen.insert(key);
        self.timestamps.entry(destination).or_default().push(timestamp);
        true
    }

    pub fn forward_packet(&mut self) -> Vec<i32> {
        if let Some((s,d,t)) = self.q.pop_front() {
            self.seen.remove(&(s,d,t));
            *self.removed.entry(d).or_insert(0) += 1;
            vec![s, d, t]
        } else { vec![] }
    }

    pub fn get_count(&self, destination: i32, start_time: i32, end_time: i32) -> i32 {
        let vec = match self.timestamps.get(&destination) { Some(v) => v, None => return 0 };
        let off = *self.removed.get(&destination).unwrap_or(&0);
        let lo = lower_bound(vec, start_time, off);
        let hi = upper_bound(vec, end_time, off);
        ((hi.saturating_sub(lo)) as i32).max(0)
    }
}

fn lower_bound(a: &Vec<i32>, target: i32, start: usize) -> usize {
    let mut l = start; let mut r = a.len();
    while l < r {
        let m = (l + r) / 2;
        if a[m] < target { l = m + 1 } else { r = m; }
    }
    l
}

fn upper_bound(a: &Vec<i32>, target: i32, start: usize) -> usize {
    let mut l = start; let mut r = a.len();
    while l < r {
        let m = (l + r) / 2;
        if a[m] <= target { l = m + 1 } else { r = m; }
    }
    l
}

TypeScript

class Router {
    private mem: number;
    private q: [number, number, number][] = [];
    private seen = new Set<string>();
    private timestamps = new Map<number, number[]>();
    private removed = new Map<number, number>();
    private key(a: number, b: number, c: number) { return `${a}#${b}#${c}`; }
    constructor(memoryLimit: number) { this.mem = memoryLimit; }

    addPacket(source: number, destination: number, timestamp: number): boolean {
        const k = this.key(source, destination, timestamp);
        if (this.seen.has(k)) return false;
        if (this.q.length === this.mem) {
            const [oa, ob, oc] = this.q.shift()!;
            this.seen.delete(this.key(oa, ob, oc));
            this.removed.set(ob, (this.removed.get(ob) ?? 0) + 1);
        }
        this.q.push([source, destination, timestamp]);
        this.seen.add(k);
        if (!this.timestamps.has(destination)) this.timestamps.set(destination, []);
        this.timestamps.get(destination)!.push(timestamp);
        return true;
    }

    forwardPacket(): number[] {
        if (this.q.length === 0) return [];
        const [a,b,c] = this.q.shift()!;
        this.seen.delete(this.key(a,b,c));
        this.removed.set(b, (this.removed.get(b) ?? 0) + 1);
        return [a,b,c];
    }

    getCount(destination: number, startTime: number, endTime: number): number {
        const vec = this.timestamps.get(destination);
        if (!vec) return 0;
        const off = this.removed.get(destination) ?? 0;
        const lo = lowerBound(vec, startTime, off);
        const hi = upperBound(vec, endTime, off);
        return Math.max(0, hi - lo);
    }
}

function lowerBound(a: number[], target: number, start: number): number {
    let l = start, r = a.length;
    while (l < r) {
        const m = (l + r) >>> 1;
        if (a[m] < target) l = m + 1; else r = m;
    }
    return l;
}

function upperBound(a: number[], target: number, start: number): number {
    let l = start, r = a.length;
    while (l < r) {
        const m = (l + r) >>> 1;
        if (a[m] <= target) l = m + 1; else r = m;
    }
    return l;
}

Complexity

• ⏰ Time complexity: O(1)
  • addPacket: amortized O(1) (append + hash/queue ops).
  • forwardPacket: O(1).
  • getCount: O(log k) where k is number of timestamps stored for the destination (binary search).
• 🧺 Space complexity: O(m) — Where m is the memory limit (number of packets stored).