Share The Story

Hard
0/120
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Google inc

Problem statement

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 2 100
3 4 200
1 3 300
2 5 400
3
1 2 1
2 3 2
3 4 3
Sample Output 1 :
1 2 3 5
1 2 3 4
Explanation For Sample Output 1 :
For test case 1 :
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]

For test case 2 :
Person 1 will tell the story to person 2 at 1st timeStamp.
Person 2 will tell the story to person 3 at 2nd timeStamp.
Person 3 will tell the story to person 4 at 3rd timeStamp.

So the output will be [1, 2, 3, 4]
Sample Input 2 :
2
2
2 3 1
1 2 2
3
1 4 2
3 5 1
4 2 3
Sample Output 2 :
1 2
1 2 4
Hint

Can you make directed connections between persons? 

Approaches (2)
Depth First Search

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.
Time Complexity

O(N*log(N)), where ‘N’ is the number of meetings in the array.

 

We are using a depth-first search approach to traverse through all people, which takes O(N), and after that, we are sorting, which takes O(N*log(N)) time. Hence the overall complexity is O(N*log(N))

Space Complexity

O(N), where ‘N’ is the number of meetings in the array.
 

In the worst case, we maintained a HashMap, holding most  ‘N’ elements, and the recursion stack also takes O(N). So the space complexity is O(N+N) which is effectively O(N). Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Share The Story
Full screen
Console