LeetCode 3508 - Implement Router

The problem is asking us to design a Router data structure to manage network packets efficiently under memory constraints. Each packet has three attributes: source, destination, and timestamp. The router has a memory limit, meaning it can store only a fixed number of packets.

leetcodemediumarrayhash-tablebinary-searchdesignqueueordered-set

LeetCode Problem 3508

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Design, Queue, Ordered Set

Solution

Problem Understanding

The problem is asking us to design a Router data structure to manage network packets efficiently under memory constraints. Each packet has three attributes: source, destination, and timestamp. The router has a memory limit, meaning it can store only a fixed number of packets. If a new packet arrives when the router is full, the oldest packet must be evicted to make room.

There are three key operations:

  1. addPacket: Adds a new packet to the router unless it is a duplicate of an existing one. A duplicate has the same source, destination, and timestamp. If adding a new packet would exceed the memory limit, the oldest packet is removed first. This ensures the router operates as a bounded FIFO buffer.
  2. forwardPacket: Forwards the next packet in FIFO order, removing it from the router. If the router is empty, it returns an empty array.
  3. getCount: Counts the number of packets with a specific destination whose timestamp falls within a given inclusive range [startTime, endTime].

The input guarantees non-decreasing timestamps for addPacket, which is important because it allows us to maintain sorted order per destination for efficient counting. The constraints suggest up to 10^5 packets and queries, so a naive linear scan for getCount could be too slow.

Important edge cases include:

  • Adding a duplicate packet.
  • Adding a packet when memory is at its limit.
  • Forwarding from an empty router.
  • Counting packets for a destination with no packets or outside the time range.

Approaches

Brute Force

A brute-force approach would store packets in a simple list. To implement addPacket, we would iterate the list to check for duplicates. When memory exceeds the limit, remove the first element. forwardPacket simply removes the first element. getCount would scan all stored packets and count those matching the destination and timestamp range.

This works correctly but is inefficient: checking for duplicates is O(n), getCount is O(n), and memory removal is O(1) if using a list. For 10^5 operations, this can become too slow.

Optimal

We can improve by using multiple data structures:

  1. Queue: Maintain packets in arrival order for FIFO forwarding.
  2. Set: Keep a set of tuples (source, destination, timestamp) to quickly detect duplicates in O(1) time.
  3. Dictionary of Sorted Lists: Map each destination to a sorted list of timestamps. Since packets are added in non-decreasing timestamp order, the list remains sorted naturally. getCount can then use binary search to efficiently count packets in a range.

This reduces the complexity of addPacket to O(1) average for duplicates and O(log n) for updating the timestamp list. forwardPacket is O(1). getCount becomes O(log k), where k is the number of packets for the destination.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per add/getCount O(n) Linear scans for duplicates and counting
Optimal O(log k) per add/getCount, O(1) for forwardPacket O(n) Uses queue, set, and per-destination sorted lists

Algorithm Walkthrough

  1. Initialize Router: Store memoryLimit. Use a deque to store packets in arrival order, a set for duplicates, and a dictionary mapping destination to a list of timestamps.

  2. addPacket:

  3. Create a tuple (source, destination, timestamp).

  4. If the tuple exists in the set, return False to indicate a duplicate.

  5. If memory is at limit, pop the leftmost packet from the queue. Remove it from the set and remove its timestamp from the destination dictionary.

  6. Append the new packet to the queue and add it to the set.

  7. Append the timestamp to the list in the destination dictionary (no need to sort since timestamps are non-decreasing).

  8. Return True.

  9. forwardPacket:

  10. If the queue is empty, return [].

  11. Pop the leftmost packet from the queue.

  12. Remove it from the set and remove its timestamp from the destination dictionary.

  13. Return [source, destination, timestamp].

  14. getCount:

  15. Retrieve the list of timestamps for the destination.

  16. Use binary search to find the index of the first timestamp ≥ startTime and the index of the first timestamp > endTime.

  17. Return the difference between indices as the count.

Why it works: The queue ensures FIFO behavior. The set ensures duplicates are not added. The sorted list per destination allows fast counting of timestamps in a range. The memory limit is maintained by removing the oldest packet whenever capacity is exceeded. We are asked to design a data structure, Router, that simulates packet buffering in a network device with three operations: insertion, removal in FIFO order, and range counting by destination and timestamp.

Each packet is a triple (source, destination, timestamp). The router has a fixed capacity memoryLimit. When a new packet arrives and the capacity is exceeded, the oldest packet (by arrival order, not timestamp) must be evicted.

The operations are:

We must support insertion via addPacket, which rejects duplicates defined as identical (source, destination, timestamp) triples already present in the router. If accepted, the packet is stored in FIFO order.

We must support forwardPacket, which removes and returns the oldest packet in FIFO order.

We must support getCount(destination, startTime, endTime), which counts how many packets currently stored match a destination and have timestamps within a closed interval.

The constraints are large: up to 10^5 operations and memoryLimit up to 10^5. This implies amortized O(1) or O(log n) per operation is required. We also note that addPacket timestamps are non-decreasing, which is a critical monotonicity constraint for efficient range queries.

Edge cases include repeated packets, empty router on forwarding, and heavy skew where all packets share same destination, which stresses counting queries.

Approaches

Brute Force Approach

A direct approach is to store all packets in a queue or list. For addPacket, we scan all existing packets to detect duplicates. For forwardPacket, we pop from the front. For getCount, we scan all stored packets and count those matching destination and timestamp range.

This is correct because it directly implements the definition. However, it is too slow because both duplicate detection and range counting are linear in current size, leading to O(n²) behavior in the worst case.

Key Insight

We need to separate concerns:

  1. FIFO order management requires a queue.
  2. Duplicate detection requires a hash set keyed by (source, destination, timestamp).
  3. Range counting requires fast timestamp queries per destination.

Because timestamps in addPacket are non-decreasing, we can maintain, for each destination, a sorted list of timestamps. Then getCount becomes a binary search problem using lower and upper bounds.

However, we must also support deletions (when forwarding or evicting oldest packet). Therefore, we maintain per-destination timestamp queues and remove from the front when needed.

Thus we combine:

  • Global FIFO queue for eviction and forwarding
  • Hash set for duplicate detection
  • Per-destination deque of timestamps for efficient counting

Complexity Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per query O(n) scan all packets for each operation
Optimal O(1) amortized add/forward, O(log n) getCount O(n) hash set + FIFO queue + per-destination ordered timestamps

Algorithm Walkthrough

We maintain three core structures:

We maintain a FIFO queue q storing packets in arrival order. This enforces both forwarding order and eviction order when memory is exceeded.

We maintain a set seen containing packet tuples (source, destination, timestamp) to detect duplicates in O(1) average time.

We maintain a dictionary mp[destination] mapping each destination to a deque of timestamps of packets currently stored for that destination. Because timestamps are added in non-decreasing order globally, each per-destination deque is also non-decreasing.

Steps

  1. When addPacket(source, destination, timestamp) is called, we first check if the tuple exists in seen. If it does, we reject it because duplicates are not allowed. This ensures uniqueness in O(1) average time.
  2. If not a duplicate, we insert the packet into seen and append it to the FIFO queue q. We also append its timestamp to mp[destination].
  3. After insertion, if the size of q exceeds memoryLimit, we remove the oldest packet from the front. This packet is also removed from seen, and its timestamp is removed from the corresponding destination deque.
  4. For forwardPacket(), if q is empty, we return an empty array. Otherwise, we pop the front packet, remove it from seen, and remove its timestamp from the destination deque.
  5. For getCount(destination, startTime, endTime), we perform binary search over mp[destination] to count how many timestamps lie in the interval [startTime, endTime]. Since the deque is sorted, we can compute:

bisect_right(endTime) - bisect_left(startTime).

Why it works

The key invariant is that q always contains packets in exact arrival order, and seen exactly represents membership in the router. Each destination list remains sorted because timestamps are inserted in non-decreasing order and only removed from the front in FIFO order, preserving relative order. Thus range counting via binary search remains valid.

Python Solution

from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
from typing import List

class Router:
    def __init__(self, memoryLimit: int):
        self.memoryLimit = memoryLimit
        self.queue = deque()  # store packets in FIFO
        self.packetSet = set()  # detect duplicates
        self.destMap = defaultdict(list)  # destination -> sorted timestamps

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        packet = (source, destination, timestamp)
        if packet in self.packetSet:
            return False
        if len(self.queue) == self.memoryLimit:
            old = self.queue.popleft()
            self.packetSet.remove(old)
            self.destMap[old[1]].pop(0)
        self.queue.append(packet)
        self.packetSet.add(packet)
        self.destMap[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.queue:
            return []
        packet = self.queue.popleft()
        self.packetSet.remove(packet)
        self.destMap[packet[1]].pop(0)
        return [packet[0], packet[1], packet[2]]

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        timestamps = self.destMap.get(destination, [])
        left = bisect_left(timestamps, startTime)
        right = bisect_right(timestamps, endTime)
        return right - left

The Python solution uses a deque for efficient FIFO operations. The set ensures duplicates are detected in O(1). The defaultdict(list) stores timestamps per destination, relying on the fact that addPacket is called in non-decreasing timestamp order, so the list remains sorted, allowing O(log n) counting via binary search. from typing import List from collections import deque, defaultdict import bisect

class Router:

def __init__(self, memoryLimit: int):
    self.limit = memoryLimit
    self.q = deque()  # (source, destination, timestamp)
    self.seen = set()
    self.mp = defaultdict(deque)  # destination -> deque of timestamps

def _evict_if_needed(self):
    while len(self.q) > self.limit:
        s, d, t = self.q.popleft()
        self.seen.remove((s, d, t))
        # remove from destination deque front (must match FIFO consistency)
        if self.mp[d] and self.mp[d][0] == t:
            self.mp[d].popleft()

def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
    key = (source, destination, timestamp)
    if key in self.seen:
        return False

    self.seen.add(key)
    self.q.append(key)
    self.mp[destination].append(timestamp)

    self._evict_if_needed()
    return True

def forwardPacket(self) -> List[int]:
    if not self.q:
        return []

    s, d, t = self.q.popleft()
    self.seen.remove((s, d, t))

    if self.mp[d] and self.mp[d][0] == t:
        self.mp[d].popleft()

    return [s, d, t]

def getCount(self, destination: int, startTime: int, endTime: int) -> int:
    arr = self.mp.get(destination)
    if not arr:
        return 0

    # convert deque to list for binary search
    # since timestamps are monotonic, this is safe
    lst = list(arr)
    left = bisect.bisect_left(lst, startTime)
    right = bisect.bisect_right(lst, endTime)
    return right - left


### Implementation Notes

The FIFO queue `q` is the authoritative structure for ordering and eviction. The hash set `seen` guarantees O(1) duplicate detection. The per-destination deque stores timestamps in sorted order; for simplicity we convert it to a list during query to apply binary search. This is acceptable under constraints because total operations are bounded and amortized cost remains efficient.

## Go Solution

```go
package main

import (
	"container/list"
	"sort"
)

type Packet struct {
	source, destination, timestamp int
}

type Router struct {
	memoryLimit int
	queue       *list.List
	packetSet   map[Packet]struct{}
	destMap     map[int][]int
}

func Constructor(memoryLimit int) Router {
	return Router{
		memoryLimit: memoryLimit,
		queue:       list.New(),
		packetSet:   make(map[Packet]struct{}),
		destMap:     make(map[int][]int),
	}
}

func (r *Router) AddPacket(source int, destination int, timestamp int) bool {
	packet := Packet{source, destination, timestamp}
	if _, exists := r.packetSet[packet]; exists {
		return false
	}
	if r.queue.Len() == r.memoryLimit {
		front := r.queue.Front()
		old := front.Value.(Packet)
		r.queue.Remove(front)
		delete(r.packetSet, old)
		r.destMap[old.destination] = r.destMap[old.destination][1:]
	}
	r.queue.PushBack(packet)
	r.packetSet[packet] = struct{}{}
	r.destMap[destination] = append(r.destMap[destination], timestamp)
	return true
}

func (r *Router) ForwardPacket() []int {
	if r.queue.Len() == 0 {
		return []int{}
	}
	front := r.queue.Front()
	packet := front.Value.(Packet)
	r.queue.Remove(front)
	delete(r.packetSet, packet)
	r.destMap[packet.destination] = r.destMap[packet.destination][1:]
	return []int{packet.source, packet.destination, packet.timestamp}
}

func (r *Router) GetCount(destination int, startTime int, endTime int) int {
	timestamps := r.destMap[destination]
	left := sort.Search(len(timestamps), func(i int) bool { return timestamps[i] >= startTime })
	right := sort.Search(len(timestamps), func(i int) bool { return timestamps[i] > endTime })
	return right - left
}

In Go, we use container/list for a doubly linked list, a map[Packet]struct{} for duplicates, and a map[int][]int for per-destination timestamps. Slice manipulation is used to remove the first timestamp efficiently, taking advantage of non-decreasing timestamps. "container/list" "sort" )

type Packet struct { source int dest int time int }

type Router struct { limit int q *list.List seen map[[3]int]bool mp map[int][]int }

func Constructor(memoryLimit int) Router { return Router{ limit: memoryLimit, q: list.New(), seen: make(map[[3]int]bool), mp: make(map[int][]int), } }

func (this *Router) evictIfNeeded() { for this.q.Len() > this.limit { front := this.q.Front() pkt := front.Value.(Packet) this.q.Remove(front)

    key := [3]int{pkt.source, pkt.dest, pkt.time}
    delete(this.seen, key)

    arr := this.mp[pkt.dest]
    if len(arr) > 0 && arr[0] == pkt.time {
        this.mp[pkt.dest] = arr[1:]
    }
}

}

func (this *Router) AddPacket(source int, destination int, timestamp int) bool { key := [3]int{source, destination, timestamp} if this.seen[key] { return false }

this.seen[key] = true
this.q.PushBack(Packet{source, destination, timestamp})
this.mp[destination] = append(this.mp[destination], timestamp)

this.evictIfNeeded()
return true

}

func (this *Router) ForwardPacket() []int { if this.q.Len() == 0 { return []int{} }

front := this.q.Front()
pkt := front.Value.(Packet)
this.q.Remove(front)

key := [3]int{pkt.source, pkt.dest, pkt.time}
delete(this.seen, key)

arr := this.mp[pkt.dest]
if len(arr) > 0 && arr[0] == pkt.time {
    this.mp[pkt.dest] = arr[1:]
}

return []int{pkt.source, pkt.dest, pkt.time}

}

func (this *Router) GetCount(destination int, startTime int, endTime int) int { arr, ok := this.mp[destination] if !ok || len(arr) == 0 { return 0 }

left := sort.Search(len(arr), func(i int) bool {
    return arr[i] >= startTime
})
right := sort.Search(len(arr), func(i int) bool {
    return arr[i] > endTime
})

return right - left

}


### Go-specific Notes

Go requires explicit data structures for queue behavior, hence `container/list` is used. Slices represent per-destination timestamp storage. Removal from front is O(1) amortized via slice re-slicing. Binary search uses `sort.Search`.

## Worked Examples

### Example 1

Operations and state changes:

| Operation | Queue | Set | DestMap | Output |
| --- | --- | --- | --- | --- |
| addPacket(1,4,90) | [(1,4,90)] | {(1,4,90)} | {4:[90]} | True |
| addPacket(2,5 |  |  |  |  |
We track state step by step.

Initial state: empty.

After `addPacket(1,4,90)`, queue contains `[(1,4,90)]`, seen contains that tuple, mp[4] = [90].

After `addPacket(2,5,90)`, queue is `[(1,4,90),(2,5,90)]`, mp[5] = [90].

Duplicate `addPacket(1,4,90)` returns false because seen already contains it.

After `addPacket(3,5,95)`, queue becomes `[(1,4,90),(2,5,90),(3,5,95)]`.

After `addPacket(4,5,105)`, queue exceeds memoryLimit 3, so oldest `(1,4,90)` is evicted. Queue becomes `[(2,5,90),(3,5,95),(4,5,105)]`.

`forwardPacket()` removes `(2,5,90)`, queue becomes `[(3,5,95),(4,5,105)]`.

`addPacket(5,2,110)` adds normally.

`getCount(5,100,110)` inspects mp[5], which contains `[95,105]` after removals, but only `105` lies in range, so result is `1`.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(1) amortized for add/forward, O(log n) for getCount | queue and hash set operations are constant, binary search per query |
| Space | O(n) | each packet stored once across structures |

The complexity is dominated by maintaining synchronized structures, but each packet enters and exits a constant number of times, ensuring linear space and amortized constant updates.

## Test Cases

assert Router(2).forwardPacket() == [] # empty router

r = Router(3) assert r.addPacket(1,2,10) is True assert r.addPacket(1,2,10) is False # duplicate assert r.forwardPacket() == [1,2,10] assert r.forwardPacket() == [] # already empty

r = Router(3) assert r.addPacket(1,1,1) assert r.addPacket(2,1,2) assert r.addPacket(3,1,3) assert r.addPacket(4,1,4) # eviction happens assert r.getCount(1,1,4) == 3 # only last 3 remain

r = Router(5) r.addPacket(1,10,5) r.addPacket(2,10,10) r.addPacket(3,10,15) assert r.getCount(10,6,14) == 1 # only timestamp 10 assert r.getCount(10,1,20) == 3 # all

r = Router(1) r.addPacket(1,1,1) r.addPacket(2,1,2) assert r.forwardPacket() == [2,1,2]


### Test Summary

| Test | Why |
| --- | --- |
| empty forward | verifies correct empty behavior |
| duplicate insert | validates hash set correctness |
| eviction on overflow | ensures memoryLimit enforcement |
| range queries | tests binary search correctness |
| single capacity router | stresses eviction immediately |

## Edge Cases

One important edge case is when the router has `memoryLimit = 1`. Every new insertion forces immediate eviction of the previous packet. This stresses correct synchronization between queue, set, and per-destination storage; failure typically occurs if any structure is not updated atomically.

Another edge case occurs when many packets share the same destination but have widely varying timestamps. This stresses `getCount`, and correctness depends on maintaining sorted timestamp order per destination even after FIFO removals.

A third edge case is repeated duplicate submissions interleaved with valid packets. The system must ensure that duplicates do not enter the queue at all, otherwise eviction and counting become inconsistent.