Practice/Google/Leetcode 1101. The Earliest Moment When Everyone Become Friends

Leetcode 1101. The Earliest Moment When Everyone Become Friends

CodingMust

Problem

You are analyzing a social network of n people numbered from 0 to n-1. You have a log of connection events where each event represents two people becoming acquainted at a specific timestamp.

Your task is to determine the earliest timestamp at which all n people become part of one interconnected network. If two people are connected directly or through a chain of mutual acquaintances, they are considered part of the same network.

Given a list of connection events and the total number of people, return the timestamp when everyone first becomes interconnected. If the network never becomes fully connected, return -1.

Requirements

1. Process connection events to build an interconnected network
2. Track when separate groups of people merge into larger networks
3. Identify the exact moment when all people become part of a single network
4. Return the timestamp of full connectivity, or -1 if it never occurs
5. Events may be provided in any order and need to be processed chronologically

Constraints

• 2 <= n <= 100
• 1 <= events.length <= 2500
• events[i].length == 3
• 0 <= timestamp <= 10^9
• 0 <= person1, person2 < n
• person1 != person2
• There are no duplicate events (same timestamp and same pair of people)
• Time complexity should be efficient for processing events in order
• Space complexity should be proportional to the number of people

Examples

Example 1:

` Input: events = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], n = 6 Output: 20190301 Explanation: Initially, everyone is isolated. As connections form:

• 20190101: {0,1}, {2}, {3}, {4}, {5}
• 20190104: {0,1}, {2}, {3,4}, {5}
• 20190107: {0,1}, {2,3,4}, {5}
• 20190211: {0,1,5}, {2,3,4}
• 20190224: {0,1,5}, {2,3,4} (already connected)
• 20190301: {0,1,2,3,4,5} (everyone is now connected!) `

Example 2:

Input: events = [[5,0,1],[10,2,3]], n = 5 Output: -1 Explanation: After all events, we have networks \{0,1\}, \{2,3\}, and \{4\}. Person 4 is never connected to anyone, so full connectivity is impossible.

Example 3:

Input: events = [[0,0,1],[0,1,2]], n = 3 Output: 0 Explanation: Both events occur at timestamp 0. After processing them, all 3 people are connected in one network.