You are given a list of videos. Each video carry two information- Hashtags attached to it, timestamp of the video. For each video, another video is found related to it if the video is released earlier and carries atleast one common hashtag. Output the number of related videos for each video.
Input- V1: {[#shorts , #gym] , 1} V2: {[#shorts , #cars, #halloween] , 5} V2: {[#truck , #automobile, #shorts] , 10} V3: {[#dance] , 15}
Output: [0,1,2,0]
Explanation- No video is released before V1. V2 one video is released before V2, which is V1 at timestamp 1 second and has a common hashtag- shorts. Similarly for V3, V1 and V2 both are related as they share #shorts as common hashtag and V1 and V2 are released earlier. For V3, no releated video is found.
The number of videos can be in millions so think of the most optimum approach.
is there any constraint on the number of hashtags?
nope, they did not provide.
So by the nature of inputs the total length of all hashtags can't be larger than 1e6. Sort the videos by timestamps. For every hashtag assign the latest element seen with it. Now for every new video connect it with every element seen with one of its hashtags in a DSU. Then just query the size of the component.