NeetCode #647LC-2127HardAdvanced Graphs
← Back to All Problems#647 · #2127 · Maximum Employees to Be Invited to a Meeting(参加会议的最多员工数)
📌 Problem Statement & Constraints
There are
n employees, each with one favourite colleague given in favorite[i]. Seating is circular and each person must sit next to their favourite. Return the maximum number who can be seated. Constraints: 2 <= n <= 10^5, 0 <= favorite[i] < n, favorite[i] != i.💡 Core Algorithmic Approaches
- The favourite relation is a functional graph: each node has exactly one outgoing edge, so every component has exactly one cycle.
- Case 1 -- cycle of length 2: the two people can sit next to each other, and each can additionally bring the longest chain pointing into them. Sum all such 2-cycles' chains.
- Case 2 -- longer cycle: only the cycle itself can be seated (chains cannot attach), so the answer is the longest cycle.
- Peel in-degree-0 nodes first to identify the cycle nodes and the chain depths.
💻 Benchmark Python3 Implementation
class Solution:
def maximumInvitations(self, favorite: List[int]) -> int:
from collections import deque
n = len(favorite)
indeg = [0] * n
for f in favorite:
indeg[f] += 1
# peel nodes not on a cycle, tracking the longest chain depth into each
depth = [1] * n
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
node = q.popleft()
nxt = favorite[node]
depth[nxt] = max(depth[nxt], depth[node] + 1) # chain length
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
# remaining nodes (indeg > 0) are exactly the cycle nodes
seen = [False] * n
pairs_total = 0 # sum over 2-cycles
max_cycle = 0 # the longest cycle
for i in range(n):
if indeg[i] > 0 and not seen[i]:
cycle = []
cur = i
while not seen[cur]:
seen[cur] = True
cycle.append(cur)
cur = favorite[cur]
if len(cycle) == 2:
# both can bring their longest chains
pairs_total += depth[cycle[0]] + depth[cycle[1]]
else:
max_cycle = max(max_cycle, len(cycle))
return max(pairs_total, max_cycle)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): the peeling and the cycle walk each visit every node once.
💾 Space Complexity
O(n) for the in-degree and depth arrays.
⚠️ Interview Pitfalls & Follow-ups
- Summing all cycle lengths: only 2-cycles can absorb chains; longer cycles are taken alone.
- Forgetting to peel the non-cycle nodes: the cycle detection would be ambiguous.
- Using
depthinitialised to 0: a node alone has chain depth 1. - Taking the maximum of a single 2-cycle instead of the sum: all 2-cycles contribute additively.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.