#3508

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Implement Router

Efficiently design a Router class to manage network packets with memory limits using array scanning and hash lookups.

array hash table binary search design queue

Problem Statement

Design a Router class that simulates network packet management under a fixed memory limit. Each packet has a source, destination, and timestamp. The Router must efficiently add packets, forward packets in memory order, and count active packets within a time window. Duplicate packets exceeding the memory limit should be rejected.

Implement the following operations: Router(int memoryLimit) to initialize the router, addPacket(source, destination, timestamp) to store a packet respecting memory limits, forwardPacket() to send the earliest packet and remove it from memory, and getCount(startTime, endTime) to return the number of packets within a timestamp range. Ensure all operations are optimized using array scanning combined with hash lookups.

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

Example details omitted.

Example 2

Input: ["Router", "addPacket", "forwardPacket", "forwardPacket"] [[2], [7, 4, 90], [], []]

Output: [null, true, [7, 4, 90], []] Explanation

Example details omitted.

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.

Solution Approach

Use deque for ordered packet storage

Store packets in a deque to maintain the order they arrive, enabling O(1) removal from the front for forwarding. This avoids costly shifting of array elements and aligns with the problem pattern of array scanning.

Use hash map for duplicate detection

Maintain a hash map keyed by (source, destination) pairs to quickly detect duplicates before insertion. This ensures addPacket operations respect memory limits and supports constant-time lookup, directly addressing the hash lookup pattern.

Implement range count with binary search

Keep packets sorted by timestamp and use binary search to count packets within a time range for getCount. This leverages the array scanning plus hash lookup pattern to efficiently retrieve counts without scanning all packets.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity: addPacket and forwardPacket are O(1) amortized due to deque and hash map usage; getCount is O(log n) for binary search over timestamps. Space complexity: O(n) for storing packets in deque and hash map.

What Interviewers Usually Probe

Ask about handling memory limits when adding duplicate packets.
Check if forwarding maintains correct packet order under constraints.
Probe for efficient counting of packets within timestamp ranges.

Common Pitfalls or Variants

Common pitfalls

Not removing packets from the hash map when forwarding, causing false duplicates.
Scanning the entire array for counts instead of using binary search.
Failing to respect memory limits, leading to incorrect addPacket results.

Follow-up variants

Router with priority-based packet forwarding instead of FIFO order.
Router supporting dynamic memory resizing with the same addPacket logic.
Router allowing bulk forwarding of multiple packets in one operation.

FAQ

What is the main pattern used in Implement Router problem?

The key pattern is array scanning combined with hash lookup, allowing efficient packet ordering and duplicate detection.

How do I handle memory limits when adding packets?

Use a deque to store packets and a hash map for lookups; reject new packets if memory is full, maintaining consistent memory tracking.

Can getCount be optimized instead of scanning all packets?

Yes, keep packets sorted by timestamp and use binary search to find the range, which avoids scanning the entire array.

Why is deque preferred over array for packet storage?

Deque allows O(1) insertion at the back and removal from the front, matching FIFO forwarding without shifting elements.

What common mistakes occur in Implement Router?

Forgetting to update the hash map on forwarding, scanning linearly for counts, or exceeding memory limits are frequent errors.

terminal

Solution

Solution 1: Hash Map + Queue + Binary Search

We use a hash map $\textit{vis}$ to store the hash values of packets that have already been added, a queue $\textit{q}$ to store the packets currently in the router, a hash map $\textit{idx}$ to record the number of packets already forwarded for each destination, and a hash map $\textit{d}$ to store the list of timestamps for each destination.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

class Router:

    def __init__(self, memoryLimit: int):
        self.lim = memoryLimit
        self.vis = set()
        self.q = deque()
        self.idx = defaultdict(int)
        self.d = defaultdict(list)

    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        x = self.f(source, destination, timestamp)
        if x in self.vis:
            return False
        self.vis.add(x)
        if len(self.q) >= self.lim:
            self.forwardPacket()
        self.q.append((source, destination, timestamp))
        self.d[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if not self.q:
            return []
        s, d, t = self.q.popleft()
        self.vis.remove(self.f(s, d, t))
        self.idx[d] += 1
        return [s, d, t]

    def f(self, a: int, b: int, c: int) -> int:
        return a << 46 | b << 29 | c

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        ls = self.d[destination]
        k = self.idx[destination]
        i = bisect_left(ls, startTime, k)
        j = bisect_left(ls, endTime + 1, k)
        return j - i


# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #3507 minimum pair removal to sort array i #3510 minimum pair removal to sort array ii