2456. Most Popular Video Creator

MediumArrayHash TableStringSortingHeap (Priority Queue)

Problem Description

In this problem, we're working with a platform that hosts videos. Each video has a unique creator and ID and has accumulated a certain number of views. We're given three arrays of equal length n:

creators which includes the names of the creators of the videos.
ids which contains the unique identifiers for each video.
views representing the number of times each video has been watched.

The goal is to calculate the popularity of each creator, defined as the sum of the views of all their videos, and then determine the creator(s) with the highest popularity. For each creator with the maximum popularity, we also need to find the ID of their most viewed video. If there is more than one such video, we select the one with the lexicographically smallest ID. The final output should be a 2D array listing the creators with the highest popularity alongside the ID of their most viewed video.

Special conditions to be aware of:

There may be more than one creator tieing for the highest popularity.
If a creator has multiple videos with the same highest view count, the one with the smallest ID in lexicographic order should be chosen.

The expectation is to have a comprehensive solution that handles these special cases correctly.

Intuition

To solve this problem, we can tackle it step-by-step:

We need to keep track of the total views for each creator. This can be achieved by iterating over the given creators and views arrays and accumulating the views in a dictionary where the keys are creator names and the values are their total views.
We need to find each creator's most viewed video. This also requires iteration over the arrays, but this time we are tracking the maximum number of views for each creator. We use another dictionary to map the creator's name to the index of their most viewed video.
If there is a tie in view counts for a creator's videos, we must make sure to select the video ID that is the smallest lexicographically. We can achieve this by updating the dictionary only when we find a video with more views or if the view count is the same but the video ID is smaller lexicographically.
After populating the dictionaries with the necessary information, we determine the maximum popularity by looking at the values in the views dictionary.
Finally, we compile the list of creators who have matched the highest popularity and pair them with the ID of their most viewed video (referenced by index in the final step) to form the 2D array.

The solution code implements these steps with efficient lookups and comparisons using dictionaries, and it accommodates the possibility of multiple creators sharing the same highest popularity, as well as the need to compare strings lexicographically.

The key aspects of this approach involve the use of hashing (dictionaries) for fast lookups and careful logic to handle ties in both popularity and view counts, ensuring the specified conditions for selecting the most viewed video ID are satisfied.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution can be broken down into distinct stages aligned with the problem requirements and utilizing specific data structures for efficiency:

Use of Default Dicts: The solution uses two defaultdicts from Python's collections module to manage the accumulation of views and tracking of the most viewed video indices. A defaultdict(int) automatically initializes any new key with an integer value of 0, facilitating easy summation.
Tracking Total Views: Iterating over the creators, ids, and views arrays simultaneously, the code increments the view count for each creator. This is achieved by the for loop and by summing up views into the cnt dictionary: cnt[c] += v.
Finding the Most Viewed Video ID: Alongside counting views, for each creator, we track the index of their most viewed video using the d dictionary. A comparison is made to determine if the current video either has more views or, on equal views, a lexicographically smaller ID than the previously tracked video.

The condition if c not in d or views[d[c]] < v or (views[d[c]] == v and ids[d[c]] > i): ensures that we are only updating the record for a creator in d when a video with more views is found or if we find a video with the same number of views but a smaller ID, ensuring the proper selection per the problem's constraints.
Determining the Maximum Popularity: Once the iteration is complete and all view counts and most viewed video indices are stored, we determine the maximum popularity using Python's max function on the values of the cnt dictionary: mx = max(cnt.values()).
Building the Answer: The final step is to construct a 2D array that contains the highest popularity creators and the IDs of their most viewed videos. This is done by building a list comprehension that checks for creators c whose popularity x is equal to the maximum mx and then pairs them with the most viewed video ID found at ids[d[c]]. The final list comprehension looks like this: [[c, ids[d[c]]] for c, x in cnt.items() if x == mx].

This solution approach expertly combines efficient iteration, conditional logic, and Python's built-in functions and data structures to fulfill the complex requirements of the problem, leading to an optimal algorithm that is both succinct and highly readable.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's use a small example with the following data:

creators = ["Anne", "Ben", "Anne", "Ben", "Cara"]
ids = ["A2", "B1", "A1", "B2", "C1"]
views = [100, 150, 50, 200, 100]

Following the steps of the solution approach:

Use of Default Dicts: We create two defaultdicts, one (cnt) for tracking the total views per creator and another (d) for tracing the most viewed video index for each creator.
Tracking Total Views: As we iterate, we sum the views for each creator in cnt like this:
- cnt["Anne"] += 100 (first video by Anne),
- cnt["Ben"] += 150 (first video by Ben),
- cnt["Anne"] += 50 (second video by Anne, now Anne's total is 150),
- and so on...
Finding the Most Viewed Video ID: For each creator, we determine the most viewed video. After iterating, we end up with:
- d["Anne"] points to the index of "A2" because "A2" has more views than "A1",
- d["Ben"] points to the index of "B2" because it has more views,
- for "Cara", we only have one video, so d["Cara"] points to "C1".
Determining the Maximum Popularity: We find the maximum popularity. In this case:
- mx is 200, the total views of Ben's most popular video.
Building the Answer: We build the final 2D array that lists creators with the highest popularity and their most viewed videos. Only Ben has the maximum popularity of 200, so the answer is:
- [['Ben', 'B2']] since Ben's most viewed video is "B2" with 200 views.

In this case, our output indicates that Ben is the most popular creator with the most viewed video "B2". If there were another creator with a total view count of 200, they would also appear in the final array with their most viewed video.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
5        # Initialize two dictionaries to keep track of view counts and most viewed video indices for each creator.
6        creator_view_count = defaultdict(int)
7        creator_best_video_index = defaultdict(int)
8
9        # Loop through each video and its associated creator and views.
10        for index, (creator, video_id, view_count) in enumerate(zip(creators, ids, views)):
11            # Increment the view count for the creator.
12            creator_view_count[creator] += view_count
13
14            # If this is the first time we see the creator or if this video has more views than the currently
15            # recorded best one (or same views but smaller id), then update the most viewed video index.
16            if (creator not in creator_best_video_index or 
17                views[creator_best_video_index[creator]] < view_count or 
18                (views[creator_best_video_index[creator]] == view_count and ids[creator_best_video_index[creator]] > video_id)):
19                creator_best_video_index[creator] = index
20
21        # Find the maximum view count across all creators.
22        max_view_count = max(creator_view_count.values())
23
24        # Create a list of [creator, video_id] for those creators whose total view count equals the max view count.
25        most_popular_creators = [
26            [creator, ids[creator_best_video_index[creator]]]
27            for creator, total_views in creator_view_count.items() if total_views == max_view_count
28        ]
29
30        # Return the list of most popular creators and their most popular video ids.
31        return most_popular_creators
32```
33
34In addition, the required `List` type hint should be imported from the `typing` module, which is not shown in the code snippet. To include it, add the following line at the beginning of your script:
35
36```python
37from typing import List
38

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
8        // Total number of entries
9        int numberOfEntries = ids.length;
10        // Map to store the total views for each creator
11        Map<String, Long> creatorViewsCount = new HashMap<>(numberOfEntries);
12        // Map to store the index of the most viewed id per creator
13        Map<String, Integer> mostViewedIdIndex = new HashMap<>(numberOfEntries);
14      
15        // Iterate over all entries
16        for (int index = 0; index < numberOfEntries; ++index) {
17            String creator = creators[index], id = ids[index];
18            long viewCount = views[index];
19          
20            // Sum up views for each creator
21            creatorViewsCount.merge(creator, viewCount, Long::sum);
22          
23            // Update the most viewed id index for the creator if this entry has more views
24            // or if the view count is the same but the id is lexicographically smaller
25            if (!mostViewedIdIndex.containsKey(creator) || views[mostViewedIdIndex.get(creator)] < viewCount
26                || (views[mostViewedIdIndex.get(creator)] == viewCount && ids[mostViewedIdIndex.get(creator)].compareTo(id) > 0)) {
27                mostViewedIdIndex.put(creator, index);
28            }
29        }
30      
31        // Find the maximum views across all creators
32        long maxViews = 0;
33        for (long viewCount : creatorViewsCount.values()) {
34            maxViews = Math.max(maxViews, viewCount);
35        }
36      
37        // List to store the result
38        List<List<String>> answer = new ArrayList<>();
39      
40        // Iterate through the view counts and find creators with view counts equal to maxViews
41        for (var entry : creatorViewsCount.entrySet()) {
42            if (entry.getValue() == maxViews) {
43                String mostPopularCreator = entry.getKey();
44                answer.add(List.of(mostPopularCreator, ids[mostViewedIdIndex.get(mostPopularCreator)]));
45            }
46        }
47      
48        // Return the list of creators with the most viewed contents and their respective most viewed content ids
49        return answer;
50    }
51}
52

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9    // Function to find the creators with the most views and their most viewed content.
10    vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& contentIds, vector<int>& views) {
11        unordered_map<string, long long> creatorViewsSum; // Map to store the sum of views per creator
12        unordered_map<string, int> creatorHighestViewIndex; // Map to store the index of each creator's content with the highest views
13      
14        int contentCount = contentIds.size(); // Total number of contents
15
16        // Aggregate views for each creator and identify the content with highest views
17        for (int i = 0; i < contentCount; ++i) {
18            string creator = creators[i];
19            string contentId = contentIds[i];
20            int viewCount = views[i];
21
22            creatorViewsSum[creator] += viewCount; // Summing up the views for each creator
23            // Check if the current content has more views than the stored one, or if it is not stored yet
24            if (!creatorHighestViewIndex.count(creator) || views[creatorHighestViewIndex[creator]] < viewCount || 
25                (views[creatorHighestViewIndex[creator]] == viewCount && contentIds[creatorHighestViewIndex[creator]] > contentId)) {
26                creatorHighestViewIndex[creator] = i;
27            }
28        }
29
30        long long maximumViews = 0;
31        // Find the maximum number of views across all creators
32        for (auto& pair : creatorViewsSum) {
33            maximumViews = max(maximumViews, pair.second);
34        }
35
36        vector<vector<string>> result; // Final result to store the creators with the most views along with their most popular content id
37        // Iterate through the creators to find those with the highest views and add them along with their popular content id to the result
38        for (auto& pair : creatorViewsSum) {
39            if (pair.second == maximumViews) {
40                result.push_back({pair.first, contentIds[creatorHighestViewIndex[pair.first]]});
41            }
42        }
43        return result;
44    }
45};
46

1function mostPopularCreator(creators: string[], ids: string[], views: number[]): string[][] {
2    // Create a map to store the total views per creator
3    const viewCounts: Map<string, number> = new Map();
4    // Create a map to store the index of the most viewed content for each creator
5    const mostViewedIndex: Map<string, number> = new Map();
6    // Get the number of elements in the arrays
7    const numElements = ids.length;
8
9    // Iterate through each content piece
10    for (let index = 0; index < numElements; ++index) {
11        const creator = creators[index];
12        const contentId = ids[index];
13        const viewCount = views[index];
14
15        // Update the total views for the creator
16        viewCounts.set(creator, (viewCounts.get(creator) ?? 0) + viewCount);
17
18        // Determine if the current content has more views or a lower id (in case of a tie) than the stored one
19        if (!mostViewedIndex.has(creator) || 
20            views[mostViewedIndex.get(creator)!] < viewCount || 
21            (views[mostViewedIndex.get(creator)!] === viewCount && ids[mostViewedIndex.get(creator)!] > contentId)) {
22            mostViewedIndex.set(creator, index);
23        }
24    }
25  
26    // Find the maximum view count across all creators
27    const maxViewCount = Math.max(...viewCounts.values());
28    // Prepare the result array
29    const result: string[][] = [];
30
31    // Find all creators who have the maximum view count
32    for (const [creator, totalViews] of viewCounts) {
33        if (totalViews === maxViewCount) {
34            // Add the creator and their most viewed content id to the result array
35            result.push([creator, ids[mostViewedIndex.get(creator)!]]);
36        }
37    }
38  
39    // Return the final results
40    return result;
41}
42

Time and Space Complexity

The time complexity of the given code is O(N), where N is the total number of videos in the views list. This time complexity arises from a single loop over the list of creators, ids, and views, processing each element once. Within the loop, operations of constant time complexity such as dictionary access and comparison are performed. The subsequent loop to generate the result list also runs in O(N) in the worst case, where every creator has the maximum views, thus keeping the overall time complexity at O(N).

The space complexity of the code is also O(N). Two dictionaries, cnt and d, store information for each creator, where cnt stores the sum of views and d stores the index of their most viewed video under specific conditions. The size of these dictionaries scales with the number of creators, which can be up to N in the case where all creators have a unique video. The space for the input lists creators, ids, and views is not counted towards this complexity as they are typically considered as input space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know