2213. Find All People With Secret¶

LeetCode Problem View on GitHub

2213. Find All People With Secret

Hard

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [xi, yi, timei] indicates that person xi and person yi have a meeting at timei. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person xi has the secret at timei, then they will share the secret with person yi, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

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

Solution¶

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    static class Pair {
        int node, time;
        public Pair(int node, int time) {
            this.node = node;
            this.time = time;
        }
        @Override
        public String toString() {
            return "Pair{" +
                   "node=" + node +
                   ", time=" + time +
                   '}';
        }
    }
    static class customSort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(first.time, second.time);
        }
    }
    private ArrayList<ArrayList<Pair >> adj;
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        List<Integer> ans = new ArrayList<>();
        adj = new ArrayList<>();
        for (int i = 0; i <= n + 1; i++)
            adj.add(new ArrayList<>());

        for (int edge[] : meetings) {
            int u = edge[0], v = edge[1], t = edge[2];
            adj.get(u).add(new Pair(v, t));
            adj.get(v).add(new Pair(u, t));
        }

        int vis[] = new int[n + 1];
        PriorityQueue<Pair> pq = new PriorityQueue<>(new customSort());
        pq.offer(new Pair(firstPerson, 0));
        pq.offer(new Pair(0, 0));
        vis[0] = 1;
        vis[firstPerson] = 1;
        HashSet<Integer> set = new HashSet<>();
        while (pq.size() > 0) {
            int currNode = pq.peek().node;
            int currTime = pq.peek().time;
            set.add(currNode);
            vis[currNode] = 1;
            pq.poll();
            for (int i = 0; i < adj.get(currNode).size(); i++) {
                int childNode = adj.get(currNode).get(i).node;
                int childTime = adj.get(currNode).get(i).time;
                if (vis[childNode] == 1)
                    continue;
                if (childTime >= currTime)
                    pq.offer(new Pair(childNode, childTime));
            }
        }

        for (int ele : set)
            ans.add(ele);
        return ans;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here