Last Updated: 9 Sep, 2021
Share The Story
Hard
Asked in company
When a person knows a story and meets someone, he immediately shares the story at that timeStamp. Initially, only person 1 knows the story. You are given a list of meetings between people in the array ‘arr’ where each meeting is in the form of (person1, person2, timeStamp) where ‘person1‘ will tell the story to ‘person2’ at time ‘timeStamp’. Your task is to construct the list of people in sorted order who will know the story at the end.
For example:
Consider ‘arr’ = [(1, 2, 100), (3, 4, 200), (1, 3, 300), (2, 5, 400)]
Person 1 will tell the story to person 2 at 100th timeStamp.
Person 1 will tell the story to person 3 at 300th timeStamp.
Person 2 will tell the story to person 5 at 400th timeStamp.
Person 4 will not be able to learn the story.
So the output will be [1, 2, 3, 5].
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.
The first line of each test case contains an integer ‘N’, denoting the number of meeting between people.
The next ‘N’ lines contain 3 space-separated integers denoting ‘person1’, ‘person2’, and ‘timeStamp’.
Output Format :
For each test case, print an array of integers in sorted order representing all persons who will know the story by the end.
The output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= person1 <= person2 <= 10^6
1 <= timeStamp <= 10^9
Time limit: 1 sec
Approaches
In the approach, we will use a depth-first search to find all persons who will know the store by the end. We will maintain a visited HashMap to store the people who have been visited. We will maintain a HashMap graph to create a directed edge for the meeting between the people.
We will create a recursive function helper(graph, visited, index, time) where graph and visited is the HashMap, the index is the current person, and time is the current time.
Algorithm:
- helper(graph, visited, index, time)
- Maintain an array ans.
- Set visited[index] as true;
- Iterate i from 0 to size of graph[index]
- Set curr as graph[index][i]
- We will check if visited[curr[0]] is equal to true or curr[1] is less than the time
- We will move to the next iteration.
- Create a recursive call and set k as helper(graph, visited, curr[0], curr[1]).
- Insert all the elements in k into ans.
- Return the array ans.
- Maintain a HashMap graph
- Iterate i from 0 to N - 1.
- Insert [arr[i][1], arr[i][2]] in graph[arr[i][0]].
- Maintain a HashMap visited.
- Set ans as a helper(graph, visited, 1, 0)
- Sort the array ans
- Return the array ans.
We will maintain a queue of persons. Initially, only person 1 knows the story, so we will push it into our queue. Now we will add all those people who are reachable from person1 into the queue with their time. We have the complete information of when the person gets to know about the story. So if a person doesn’t know the story yet, they will not be able to share it with others. Hence we will check whether a person knows the story before meeting another person or not.
Algorithm:
- We will maintain a queue and push 1 into it, as only 1 knows the story initially.
- While the queue is NOT empty, we will do the following steps:
- First, we will see all the persons connected to 1. We will add them to the queue.
- We will add the front of the queue into our answer.
- Before adding, we will check for the condition: if the person who is in the front of the queue already knows the story.
- To check this condition, we will see:
- If the timestamp of the person being added to the queue is greater than the timestamp of the person in front of the queue, then add it to the queue.
- Else, don’t add it to the queue.
- Pop the front element of the queue.
- After that, we will sort our answer array and return it.