Leetcode 2456: Most Popular Video Creator
You are given three arrays: ‘creators’, ‘ids’, and ‘views’. Each index i corresponds to a video created by the creator ‘creators[i]’, with an id ‘ids[i]’, and a number of views ‘views[i]’. The task is to find the most popular creators based on the sum of views of all their videos and identify the id of their most viewed video. If multiple creators have the same popularity, return all of them. For each creator, if they have multiple videos with the highest view count, return the lexicographically smallest id of their most viewed video.
Problem
Approach
Steps
Complexity
Input: You are given three arrays: 'creators' (a list of strings), 'ids' (a list of strings), and 'views' (a list of integers). All arrays have the same length n, representing the number of videos.
Example: creators = ['anna', 'bob', 'anna', 'chris'], ids = ['one', 'two', 'three', 'four'], views = [5, 10, 5, 4]
Constraints:
• 1 <= n <= 10^5
• 1 <= creators[i].length, ids[i].length <= 5
• creators[i] and ids[i] consist of lowercase English letters only
• 0 <= views[i] <= 10^5
Output: Return a 2D array where each element is a pair of creator and their most popular video's id. If there are multiple creators with the highest popularity, include all of them. If a creator has multiple videos with the highest views, return the lexicographically smallest id.
Example: [['anna', 'one'], ['bob', 'two']]
Constraints:
• The answer can be in any order.
Goal: To calculate the popularity of creators based on the sum of views of their videos and identify the id of their most popular video.
Steps:
• 1. Iterate through each video and accumulate views for each creator.
• 2. Store the video details for each creator in a way that allows easy identification of the most viewed video.
• 3. After processing all the videos, identify the creator(s) with the highest total views.
• 4. For each of these creators, find their video with the highest views, and if there are ties, choose the lexicographically smallest video id.
Goal: Ensure the solution is optimized to handle large inputs within the provided constraints.
Steps:
• The input size can be up to 100,000, so the solution should run in O(n) time complexity.
Assumptions:
• The video ids are not necessarily unique across creators, but each video id is unique for each creator.
• Input: creators = ['anna', 'bob', 'anna', 'chris'], ids = ['one', 'two', 'three', 'four'], views = [5, 10, 5, 4]
• Explanation: In this example, 'anna' has a total of 10 views (from videos 'one' and 'three'). 'bob' has 10 views (from video 'two'). 'chris' has 4 views. 'anna' and 'bob' are the most popular creators. For 'anna', the lexicographically smaller video id with the highest views is 'one'. For 'bob', the video id with the highest views is 'two'.
• Input: creators = ['anna', 'anna', 'anna'], ids = ['a', 'b', 'c'], views = [1, 2, 2]
• Explanation: Here, 'anna' is the only creator, and the most viewed video is 'b' because it has 2 views, which is lexicographically smaller than 'c'.
Approach: We will first calculate the total views for each creator and track the most viewed video for each creator. After determining the creators with the highest popularity, we will select the lexicographically smallest video id for those creators.
Observations:
• We need to handle large inputs efficiently, so we should aim for a linear time complexity.
• We can use a hash map to store the sum of views for each creator and a list of videos for each creator.
Steps:
• 1. Use a map to store the total views for each creator.
• 2. Use another map to store the video details (views and ids) for each creator.
• 3. After processing all videos, find the creator(s) with the highest total views.
• 4. For each creator with the highest views, sort their videos and select the lexicographically smallest id.
Empty Inputs:
• If the input arrays are empty, return an empty result.
Large Inputs:
• For large inputs, ensure the solution can handle up to 100,000 videos efficiently.
Special Values:
• If all videos have zero views, the result should be an empty list.
Constraints:
• Ensure efficient handling of both the creators and video ids, as there can be many different creators and video ids.
class Solution {
static bool cmp(pair<ll, string> p1, pair<ll, string> p2) {
if(p1.first == p2.first) return p1.second < p2.second;
else return p1.first > p2.first;
}
public:
vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
vector<vector<string>> ans;
long long n = creators.size(), maxi = INT_MIN;
map<string, ll> m1;
map<string, vector<pair<ll, string>>> m2;
for(int i = 0; i < n; i++) {
m1[creators[i]] += views[i];
m2[creators[i]].push_back(make_pair(views[i], ids[i]));
maxi = max(maxi, m1[creators[i]]);
}
for(auto &[l, r] : m1) {
if(r == maxi) {
sort(m2[l].begin(), m2[l].end(), cmp);
ans.push_back({l, m2[l].front().second});
}
}
return ans;
}
1 : Class Definition
class Solution {
Defines the `Solution` class containing the required function.
2 : Helper Function
static bool cmp(pair<ll, string> p1, pair<ll, string> p2) {
Defines a comparator function to sort pairs of view counts and IDs based on the view count and lexicographical order of IDs.
3 : Condition Check
if(p1.first == p2.first) return p1.second < p2.second;
Checks if two elements have the same view count and compares their IDs lexicographically.
4 : Condition Check
else return p1.first > p2.first;
If view counts differ, sorts them in descending order of view count.
5 : Function Definition
public:
Marks the start of the public section in the `Solution` class.
6 : Function Definition
vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
Defines the main function to calculate the most popular creators and their most viewed content.
7 : Variable Initialization
vector<vector<string>> ans;
Initializes the result container for the output.
8 : Variable Initialization
long long n = creators.size(), maxi = INT_MIN;
Stores the number of creators and initializes the maximum views variable.
9 : Map Initialization
map<string, ll> m1;
Initializes a map to store cumulative views for each creator.
10 : Map Initialization
map<string, vector<pair<ll, string>>> m2;
Initializes a map to store pairs of views and IDs for each creator.
11 : Loop Through List
for(int i = 0; i < n; i++) {
Loops through all creators to populate the maps.
12 : Map Update
m1[creators[i]] += views[i];
Updates the cumulative views for the current creator in the map.
13 : Map Update
m2[creators[i]].push_back(make_pair(views[i], ids[i]));
Adds the view count and ID pair to the vector for the current creator.
14 : Maximum Update
maxi = max(maxi, m1[creators[i]]);
Updates the maximum views encountered so far.
15 : Map Iteration
for(auto &[l, r] : m1) {
Iterates through the map to identify creators with the maximum views.
16 : Condition Check
if(r == maxi) {
Checks if the current creator's total views match the maximum views.
17 : Sorting
sort(m2[l].begin(), m2[l].end(), cmp);
Sorts the content for the current creator using the comparator function.
18 : Result Update
ans.push_back({l, m2[l].front().second});
Adds the creator and their most popular content ID to the result.
19 : Return Statement
return ans;
Returns the result containing the most popular creators and their top content.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We are only performing simple operations on each video and then sorting a small list of video ids for each creator.
Best Case: O(n)
Worst Case: O(n)
Description: We store video details and the popularity of each creator, which requires linear space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus