How do you solve Implement Router on LeetCode?

Implement Router (LeetCode #3508) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(n) space complexity. Key insight: Use a deque for efficient FIFO management.

What is the time complexity of Implement Router?

The optimal solution for Implement Router runs in O(1) time and uses O(n) space. Adding and removing packets from deque and checking duplicates in a set are O(1) operations.

What is the brute force solution for Implement Router?

The brute force approach for Implement Router is Brute Force, with O(n²) time complexity and O(n) space complexity. Check each packet for duplicates and manage the list of packets directly. This approach is straightforward but inefficient due to repeated checks. The optimal Optimal Solution approach improves this to O(1).

What are the interview tips for Implement Router?

Explain your thought process clearly. Discuss trade-offs between different data structures. Practice coding on a whiteboard or online editor.

What are common mistakes when solving Implement Router?

Not managing memory limit correctly. Forgetting to check for duplicates before adding.

#3508

Implement Router

Medium

ArrayHash TableBinary SearchDesignQueueOrdered SetHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(n)	O(n)

💡

Intuition

Time O(1)Space O(n)

Use a deque for efficient packet management and a hash set for quick duplicate checks. This allows for O(1) operations for adding and removing packets.

⚙️

Algorithm

3 steps

1Step 1: Use a deque to store packets in order of arrival.
2Step 2: Use a hash set to track unique packets for quick duplicate checks.
3Step 3: When adding a packet, check the hash set; if it's unique, add it to the deque and hash set, and remove the oldest if necessary.

solution.py17 lines

1from collections import deque
2class Router:
3    def __init__(self, memoryLimit):
4        self.memoryLimit = memoryLimit
5        self.packets = deque()
6        self.packetSet = set()
7
8    def addPacket(self, source, destination, timestamp):
9        packet = (source, destination, timestamp)
10        if packet in self.packetSet:
11            return False
12        if len(self.packets) >= self.memoryLimit:
13            old_packet = self.packets.popleft()
14            self.packetSet.remove(old_packet)
15        self.packets.append(packet)
16        self.packetSet.add(packet)
17        return True

ℹ

Complexity note: Adding and removing packets from deque and checking duplicates in a set are O(1) operations.

1Use a deque for efficient FIFO management.
2Hash sets provide O(1) average time complexity for duplicate checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.