
Problem Statement
In this scenario, we are given a total of n
individuals, each represented by unique indices ranging from 0
to n-1
. A data structure, specifically a 2D array, denotes meetings among these individuals. Each entry in this array, [xi, yi, timei]
, represents a meeting between persons xi
and yi
at a specific time timei
. Notably, multiple meetings can occur simultaneously involving the same individuals.
Initially, person 0
is privy to a secret and shares it with firstPerson
immediately at time 0
. The sharing of secrets does not stop here, as during each meeting, any participant who knows the secret will share it with their counterpart. This process of secret sharing is instantaneous, meaning that if an individual learns a secret, they can immediately relay it to others in concurrent meetings within the same time frame.
Ultimately, the task is to determine which individuals are aware of the secret after all described meetings have concluded, and output their indices in any sequence.
Examples
Example 1
Input:
n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output:
[0,1,2,3,5]
Explanation: At time 0, person 0 shares the secret with person 1. At time 5, person 1 shares the secret with person 2. At time 8, person 2 shares the secret with person 3. At time 10, person 1 shares the secret with person 5. Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.
Example 2
Input:
n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output:
[0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3. At time 2, neither person 1 nor person 2 know the secret. At time 3, person 3 shares the secret with person 0 and person 1. Thus, people 0, 1, and 3 know the secret after all the meetings.
Example 3
Input:
n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output:
[0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1. At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3. Note that person 2 can share the secret at the same time as receiving it. At time 2, person 3 shares the secret with person 4. Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.
Constraints
2 <= n <= 105
1 <= meetings.length <= 105
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 105
1 <= firstPerson <= n - 1
Approach and Intuition
The mechanics of this problem revolve around efficiently propagating information through a network of meetings, adhering to the meeting schedules. The process can be visualized and tackled using graph theory concepts, where individuals represent nodes and meetings act as edges connecting these nodes. Here is an intuitive and systematic approach to solve the problem:
Initialization
- Start by noting that individuals
0
andfirstPerson
know the secret at the outset (time0
). - Maintain a set or list to record the indices of people who become informed of the secret.
- Start by noting that individuals
Sort Meetings by Time
- Organize meetings based on their time to ensure that sharing happens in a chronological order.
Simulate the Meetings
- Traverse through the sorted list of meetings.
- For each meeting:
- Check if either of the participants already knows the secret.
- If yes, the other participant is also informed about the secret at that time point.
- Update the list or set of informed individuals.
Iterate until Completion
- Continue processing until all meetings are accounted for.
- Even if an individual learns the secret at the same time as another meeting they are involved in, they can propagate the secret due to the instantaneous nature of sharing.
Output
- Once all meetings are processed, the final list or set contains the indices of all informed individuals.
By using a union-find data structure or graph traversal techniques such as Breadth-First Search (BFS), we can efficiently manage and simulate the dissemination of the secret within the constraints given. This visualization helps ensure that each informed individual can spread the secret, respecting the sequence and timing of the meetings.
Solutions
- C++
- Java
- Python
class DisjointSet {
private:
// Arrays to hold the parent node and rank of each node
vector<int> parent;
vector<int> rank;
public:
// Constructor initializes the disjoint set arrays
DisjointSet(int n) {
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
// Return the representative node for x
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// Connect the subsets containing nodes x and y
void connect(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// Check if two nodes are in the same subset
bool isConnected(int x, int y) {
return find(x) == find(y);
}
// Reset the properties of node x to its initial state
void reinitialize(int x) {
parent[x] = x;
rank[x] = 0;
}
};
class Solution {
public:
vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
// Sort meetings by the meeting time
sort(meetings.begin(), meetings.end(),
[](const auto& a, const auto& b) { return a[2] < b[2]; });
// Group meetings that happen at the same time
map<int, vector<pair<int, int>>> chronologicalMeetings;
for (const auto& meeting : meetings) {
int x = meeting[0], y = meeting[1], time = meeting[2];
chronologicalMeetings[time].emplace_back(x, y);
}
DisjointSet disjointSet(n);
disjointSet.connect(firstPerson, 0); // firstPerson knows the secret
for (auto& [time, currentMeetings] : chronologicalMeetings) {
for (auto& [x, y] : currentMeetings) {
disjointSet.connect(x, y);
}
for (auto& [x, y] : currentMeetings) {
if (!disjointSet.isConnected(x, 0)) {
disjointSet.reinitialize(x);
disjointSet.reinitialize(y);
}
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
if (disjointSet.isConnected(i, 0)) {
result.push_back(i);
}
}
return result;
}
};
This CPP implementation provides a solution to identify all individuals who know a secret after certain meetings using the Disjoint Set (Union-Find) data structure. The solution consists of two main classes: DisjointSet
and Solution
.
DisjointSet:
- Maintains two arrays,
parent
andrank
for the union-find operations. find()
method discovers the representative of a node using path compression.connect()
method unites two subsets into a single subset based on rank, ensuring trees remain relatively shallow.isConnected()
method checks if two nodes are in the same subset by comparing their representatives.reinitialize()
method resets the properties of a node to its initial state.
- Maintains two arrays,
Solution:
- Receives inputs: the number of people
n
, a list of meetings with their times[x, y, time]
, andfirstPerson
who initially knows a secret. - Meetings are sorted based on time to process them chronologically.
- Uses a map
chronologicalMeetings
to group meetings that happen at the same time. - Processes meetings by time slice. For each time slice, after all connections for that time are processed, it checks and disconnects any person not connected to person
0
. - Finally, it traverses all nodes, and those connected to person
0
are added to the result list.
- Receives inputs: the number of people
The code navigates through meetings in chronological order integrating the disjoint set methods. Each individual found connected to person 0
at the end of all meetings is implied to know the secret. This efficient handling of union-find operations ensures minimal depth of trees, making find and union operations fast, which are crucial for performance given potential large inputs represented by n
and the number of meetings. The modern C++ features such as ranged-for loops, lambda expressions for sorting, and the use of map and vector data structures aid in achieving a clean and performant solution.
By the end, this code returns a list of all persons who know the secret after all meetings have been processed. This solution emphasizes the powerful combination of chronologically structuring data and the use of efficient data structures to maintain and update connections between entities.
class Solution {
public List<Integer> discoverAllPeople(
int n,
int[][] meetings,
int firstPerson
) {
// Sorting meeting times
Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
// Group meetings by time
Map<Integer, List<int[]>> groupedMeetings = new TreeMap<>();
for (int[] meeting : meetings) {
int p1 = meeting[0], p2 = meeting[1], time = meeting[2];
groupedMeetings
.computeIfAbsent(time, k -> new ArrayList<>())
.add(new int[] { p1, p2 });
}
// Graph initialization
UnionFind unionFindSystem = new UnionFind(n);
unionFindSystem.unite(firstPerson, 0);
// Process meetings by time
for (int time : groupedMeetings.keySet()) {
// Connect participants of a meeting
for (int[] meeting : groupedMeetings.get(time)) {
int p1 = meeting[0], p2 = meeting[1];
unionFindSystem.unite(p1, p2);
}
// Decide who retains the secret
for (int[] meeting : groupedMeetings.get(time)) {
int p1 = meeting[0], p2 = meeting[1];
if (!unionFindSystem.connected(p1, 0)) {
unionFindSystem.reset(p1);
unionFindSystem.reset(p2);
}
}
}
// Gather all people who know the secret
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (unionFindSystem.connected(i, 0)) {
result.add(i);
}
}
return result;
}
}
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX] += 1;
}
}
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public void reset(int x) {
parent[x] = x;
rank[x] = 0;
}
}
The solution provided addresses the problem by utilizing a union-find data structure, which is key to solving problems related to network connectivity. Here's the breakdown of the approach:
Sorting Meetings: The meetings are sorted by their scheduled times to ensure they are processed in chronological order.
Grouping Meetings: Meetings are categorized based on their time slots into a
TreeMap
, which naturally orders keys and allows for easy retrieval and iteration by meeting time.Initializing Union-Find Data Structure: A union-find structure, specifically for this problem, is designed to manage the connection states between people, starting with the first person who knows a secret.
Processing Meetings: For each set of simultaneous meetings (meetings that occur at the same time), the Union-Find structure is used to connect people who meet. After updating connections for each group of meetings, a second pass ensures only those still connected to the person initially with the secret keep knowing it.
Resetting Connections: Connections between people not knowing the secret directly or indirectly through others connected to the originally informed person are reset, marking them disconnected.
Collecting Results: The final step involves iterating over all individuals and collecting those who are still connected to the person originally with the secret.
This method effectively uses the properties of Union-Find operations (find, unite, and connected) to manage and query connections. By sorting and grouping the various meetings, the algorithm efficiently handles scheduling and ensures reliability in determining who has the secret at the end of all meetings.
class Solution:
def getAllKnownPeople(
self, total: int, interactions: List[List[int]], secondPerson: int
) -> List[int]:
# Sorting interactions based on the time of happening
interactions.sort(key=lambda x: x[2])
# Grouping interactions at the same time
grouped_interactions = defaultdict(list)
for person1, person2, time in interactions:
grouped_interactions[time].append((person1, person2))
# Structure to manage and merge groups
union_structure = UnionFind(total)
union_structure.unite(secondPerson, 0)
# Go through each time's interactions
for time in grouped_interactions:
# Merge groups for each interaction
for person1, person2 in grouped_interactions[time]:
union_structure.unite(person1, person2)
# Reset nodes that are not connected to the known secret holder
for person1, person2 in grouped_interactions[time]:
if not union_structure.connected(person1, 0):
union_structure.reset(person1)
union_structure.reset(person2)
# Find all nodes connected to the node 0
return [i for i in range(total) if union_structure.connected(i, 0)]
class UnionFind:
def __init__(self, size: int):
# Initialize nodes' parent and ranking data
self.parent = [i for i in range(size)]
self.rank = [0] * size
def find(self, x: int) -> int:
# Path Compression heuristic
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def unite(self, x: int, y: int) -> None:
# Merge two sets using their roots and ranking
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
if self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
elif self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
else:
self.parent[rootY] = rootX
self.rank[rootX] += 1
def connected(self, x: int, y: int) -> bool:
# Check if two nodes share the same root
return self.find(x) == self.find(y)
def reset(self, x: int) -> None:
# Reset node to be its own parent and rank to zero
self.parent[x] = x
self.rank[x] = 0
In the given Python program, the task is to identify all individuals who know a specific secret from a list of interactions using a union-find data structure for efficient group management. Here’s a breakdown of the process implemented in the code:
- Interaction Sorting: The interactions are first sorted based on the time they occurred to process them chronologically.
- Grouping Interactions: Interactions occurring at the same time are grouped together to be processed simultaneously.
- Union-Find Data Structure Setup: This included methods for uniting groups (
unite
), finding the leader of a group (find
), checking connection between groups (connected
), and resetting group members (reset
). - Initial Union Operation: The secret holder (represented by
secondPerson
) is initially united with a base person (person 0). - Processing of Interactions:
- For each point in time, pairs of interacting individuals are united.
- After processing all interactions at that time, it checks and resets the connection status of individuals who are not connected to the base person.
- Result Compilation: Finally, it gathers and returns a list of all individuals directly or indirectly connected to the base person (person 0).
This algorithm ensures that all people who, through direct or indirect interactions at various times, are connected to the person initially known to have the secret, are identified. The usage of union-find with path compression and union by rank optimizes the process for larger datasets, making the approach efficient in terms of both time and space complexities.
No comments yet.