This is a premium problem. We're working on making it available for free soon.
Use these hints if you're stuck. Try solving on your own first.
Sort the log items by their timestamp.
How can we model this problem as a graph problem?
Let's use a union-find data structure. At the beginning we have a graph with N nodes but no edges.
Then we loop through the events and unite each node until the number of connected components reach to 1. Notice that each time two different connected components are united the number of connected components decreases by 1.
Solutions for this premium problem will be available for free soon.
Browse Free ProblemsWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting ensures that friendship events are processed in chronological order. This allows us to simulate the growth of the social network over time and correctly identify the earliest moment when everyone becomes connected.
Yes, problems involving Union Find and dynamic connectivity frequently appear in FAANG-style interviews. This question tests understanding of graph connectivity, sorting, and efficient set merging techniques.
Union Find (Disjoint Set Union) is the best data structure for this problem. It efficiently tracks connected components and supports fast union and find operations with path compression and union by rank.
The optimal approach is to sort all friendship logs by timestamp and process them using a Union Find data structure. Each log merges two people into the same connected component. The earliest time when only one component remains is the answer.