Find All People With Secret

Updated on 28 May, 2025
Find All People With Secret header image

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:

  1. Initialization

    • Start by noting that individuals 0 and firstPerson know the secret at the outset (time 0).
    • Maintain a set or list to record the indices of people who become informed of the secret.
  2. Sort Meetings by Time

    • Organize meetings based on their time to ensure that sharing happens in a chronological order.
  3. 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.
  4. 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.
  5. 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
cpp
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 and rank 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.
  • Solution:

    • Receives inputs: the number of people n, a list of meetings with their times [x, y, time], and firstPerson 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.

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.

java
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.

python
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.

Comments

No comments yet.