Most Popular Video Creator Problem Solution In C++/Java/Python/Javascript
Problem Description
You are given two string arrays creators and ids, and an integer array views, all of length n. The i th video on a platform was created by creators[i], has an id of ids[i], and has views[i] views.
The popularity of a creator is the sum of the number of views on all of the creator's videos. Find the creator with the highest popularity and the id of their most viewed video.
If multiple creators have the highest popularity, find all of them.
If multiple videos have the highest view count for a creator, find the lexicographically smallest id.
Note: It is possible for different videos to have the same id, meaning that ids do not uniquely identify a video. For example, two videos with the same ID are considered as distinct videos with their own viewcount.
Return a 2D array of strings answer where answer[i] = [creators i, id i] means that creators i has the highest popularity and id i is the id of their most popular video. The answer can be returned in any order.
Example
Below are Most Popular Video Creator examples for reference
Input: creators = ["alice","bob","alice","chris"], ids = ["one","two","three","four"], views = [5,10,5,4]
Output: [["alice","one"],["bob","two"]]
Explanation:
The popularity of alice is 5 + 5 = 10.
The popularity of bob is 10.
The popularity of chris is 4.
alice and bob are the most popular creators.
For bob, the video with the highest view count is "two".
For alice, the videos with the highest view count are "one" and "three". Since "one" is lexicographically smaller than "three", it is included in the answer.
Input: creators = ["alice","alice","alice"], ids = ["a","b","c"], views = [1,2,2]
Output: [["alice","b"]]
Explanation:
The videos with id "b" and "c" have the highest view count.
Since "b" is lexicographically smaller than "c", it is included in the answer.
Constraints:
- n == creators.length == ids.length == views.length
- 1 <= n <= 10^5
- 1 <= creators[i].length, ids[i].length <= 5
- creators[i] and ids[i] consist only of lowercase English letters.
- 0 <= views[i] <= 10^5
We need to find the most popular creator(s), where popularity is the sum of views across all their videos. If multiple creators have the highest popularity, we consider all of them. What if we can somehow dynamically add the views for a particular creator and choose the creator with maximum views each time.
Sub-Optimal Approach
Intuition
Real World Example
Most Popular Video Creator example can be thought of as an real world example of as If you're running a video-sharing platform where you need to keep track of each creator's overall performance. Now let us assume for a particular creator you want to add the views count as you move forward but the question is how can you do that? because we cannot check the list every time and add the views count to the creator , we want something so that instantly we can add the view count to the creator we want. To do this, you use data structures like hash maps to accumulate and organize data. This setup is like having a digital filing system where every piece of information is neatly categorized by creator. For example, one hash map can record each creator's total view count, while another can store details about their most popular video
What is a hash map?
A hash map (or hash table) is a data structure that stores key-value pairs, providing an efficient way to insert, delete, and retrieve data. It uses a hash function to compute an index from the given key, allowing for fast access to values. The computed index determines the position in an array where the corresponding key-value pair is stored. This structure is widely used in applications that require fast lookups, such as caching, database indexing, and symbol tables in compilers.
The efficiency of a hash map comes from its average-case time complexity of O(1)for insertion, deletion, and lookup operations. This is achieved when the hash function distributes keys evenly across the table, minimizing collisions. However, in the worst case, when multiple keys map to the same index, operations can degrade to O(n), as resolving collisions requires additional steps. Common collision resolution techniques include chaining, where each index stores a linked list of entries, and open addressing, where probing is used to find the next available slot in the array.
The space complexity of a hash map is O(n), where n is the number of elements stored. The efficiency of storage depends on the load factor, which measures the ratio of stored elements to the table’s size. If this factor exceeds a certain threshold (commonly 0.75), the table resizes itself, usually by doubling its capacity. This resizing ensures performance remains close to O(1), but it temporarily increases the cost of operations due to rehashing all elements.
Despite its advantages, a hash map has some drawbacks. The occurrence of collisions can degrade performance, requiring extra memory for linked lists or empty slots. Additionally, the unordered nature of hash maps makes them unsuitable for scenarios where maintaining the insertion order is essential. However, with proper implementation and a well-designed hash function, hash maps remain one of the most powerful and widely used data structures for fast key-based lookups.
Now, once all this data is gathered, the next challenge is to quickly determine which creators are at the top of the leaderboard in terms of total views. Assume you are moving forward in a list and dynamically adding views count and storing them but assume that as you move forward you want the creator with max views , so what can be done to achieve this? Should we traverse the list everytime and check for the creator with max views each time. This could be one of the solution but as the number of creators rise drastically this method would be computationally expensive. This is where a heap comes in. Think of a heap as a dynamic leaderboard that automatically sorts the creators based on their total view counts. Instead of manually scanning through your entire dataset every time you want to know who's in the lead, the heap allows you to instantly access the creator with the highest popularity. It’s an efficient tool to continuously keep track of and retrieve the maximum values, making your data retrieval process both swift and organized.
What is Heap?
A heap is a specialized tree-based data structure often used to implement priority queues. Heaps are usually implemented as complete binary trees (every level is fully filled except possibly the last, and all nodes are as far left as possible), which allows them to be efficiently stored in an array. With a heap, you can quickly access the minimum or maximum element in constant time, and insertion or deletion operations take logarithmic time. This makes heaps extremely useful in algorithms that require repeated retrieval of the "best" element, like scheduling tasks or sorting data with heapsort.
What is min-heap?
A min-heap is a specialized binary tree-based data structure where the smallest element is always at the root. This means that for any given node in the tree, its value is less than or equal to the values of its children. Because of this property, you can quickly access the minimum element at any time. Additionally, a min-heap is usually implemented as a complete binary tree, which means all levels of the tree are fully filled except possibly the last level, and all nodes in the last level are as far left as possible.
What is max-heap?
A max-heap is a complete binary tree data structure where every parent node has a value greater than or equal to its children, ensuring that the largest element is always at the root. This property makes it easy to quickly access the maximum element. Like a min-heap, a max-heap is typically implemented using an array, which efficiently represents the complete binary tree.
General Operations on Heap:
- Insertion:
Inserting an element takes O(log n) time because after placing the new element at the end of the array, you "bubble up" (or "sift up") to restore the heap property. - Removal (Extract-Min/Extract-Max):
Removing the root element (the minimum in a min-heap or maximum in a max-heap) also takes O(log n) time since after removal, you "bubble down" (or "sift down") the last element placed at the root to reestablish the heap property. - Peek (Find-Min/Find-Max):
Retrieving the root element is an O(1) operation because it is always at the front of the array. - Building a Heap:
Building a heap from an unsorted array can be done in O(n) time using a bottom-up heapify process. - Space Complexity:
The heap uses O(n) space to store n elements.
So, by combining hash maps and a heap, you first collect and store detailed data for each creator, and then you efficiently identify the top performers. The hash maps serve as your comprehensive database, while the heap acts like an always-updated scoreboard, instantly highlighting which creators have amassed the most views and should be showcased on your platform.
Approach
Most Popular Video Creator algorithm includes following steps:
Step 1: Initialize two hash maps. One will store each creator's total view count, and the other will track each creator's best video (storing both the video ID and its view count).
Step 2: Loop through every video. For each video, update the creator's total view count in the first hash map, and update the best video in the second hash map if the current video has more views or, in the event of a tie, a lexicographically smaller video ID.
Step 3: Create a (max-heap). Iterate over the total views hash map and push each creator along with their total view count into the heapso that the creator with the highest total views is at the top.
Step 4: Extract creators from the heap. Start by popping the top element to get the creator with the maximum total views, and continue popping while the next element has the same total view count to collect all top creators.
Step 5: For each extracted top creator, retrieve their best video from the second hash map and form a pair of [creator, video ID].
Step 6: Return the final list of these pairs as the result.
Why do we use two hash maps in this solution?
One hash map is used to accumulate the total views for each creator, while the other stores the best video for each creator (i.e., the video with the highest view count, using lexicographical order to break ties). This separation helps us efficiently track both overall popularity and individual video performance.
What role does the heap play in this approach?
The heap acts as a dynamic leaderboard that automatically orders creators by their total view counts. This allows us to quickly retrieve the creator with the highest total views without having to sort the entire list every time, making the solution more efficient.
How is the tie-breaking between videos handled?
If a creator has multiple videos with the same view count, we choose the video whose ID is lexicographically smaller. Lexicographical order means comparing the strings as if they were in a dictionary, ensuring a consistent and clear method for tie-breaking.
Dry Run
Assume the input is as follows:
Creators: ["alice", "bob", "alice", "chris"]
Video IDs: ["one", "two", "three", "four"]
Views: [5, 10, 5, 4]
Step 1: Process each video one by one.
For the video at index 0, "alice" created video "one" with 5 views. We add 5 to "alice"'s total views and record "one" as her best video with 5 views.
At index 1, "bob" created video "two" with 10 views. We add 10 to "bob"'s total views and record "two" as his best video with 10 views.
At index 2, "alice" created video "three" with 5 views. We update "alice"'s total views by adding another 5, making her total 10. We then compare video "three" with her current best video "one". Since both have 5 views, we keep "one" because it is lexicographically smaller than "three".
At index 3, "chris" created video "four" with 4 views. We add 4 to "chris"'s total views and record "four" as his best video with 4 views.
Step 2: Build the heap using the total views from each creator.
From our records, "alice" has 10 views, "bob" has 10 views, and "chris" has 4 views. We insert these into a (max-heap) which will automatically order them so that the creators with the highest views come first. In this case, both "alice" and "bob" are at the top with 10 views, while "chris" is at the bottom.
Step 3: Extract the top creators from the heap.
We pop the first element from the queue and get one of the creators with 10 views, say "bob". We then check the next element and find "alice", who also has 10 views. We pop "alice" as well. We stop extracting when we encounter a creator with fewer than 10 views (in this case, "chris" with 4 views is not extracted).
Step 4: Form the final result by pairing each top creator with their best video.
For "bob", the best video recorded is "two". For "alice", the best video is "one". The final result is a list of pairs: [["bob", "two"], ["alice", "one"]]. The order of the pairs can vary.
This dry run demonstrates how we use hash maps to accumulate data and a heapto efficiently extract and return the top creators along with their standout videos.
Code for All Languages
Most Popular Video Creator solution in C++ :Sub-Optimal
class Solution {
public:
vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
// Hash map to store total views for each creator.
unordered_map<string, long long> totalViews;
// Hash map to store the best video (ID and view count) for each creator.
unordered_map<string, pair<string, int>> bestVideo;
int n = creators.size();
// Process each video.
for (int i = 0; i < n; i++) {
string creator = creators[i];
string video = ids[i];
int viewCount = views[i];
totalViews[creator] += viewCount;
// Update the best video for the creator.
if (bestVideo.find(creator) == bestVideo.end() ||
viewCount > bestVideo[creator].second ||
(viewCount == bestVideo[creator].second && video < bestVideo[creator].first)) {
bestVideo[creator] = {video, viewCount};
}
}
// Priority queue (max-heap) to sort creators by total views.
auto cmp = [](const pair<long long, string>& a, const pair<long long, string>& b) {
return a.first < b.first; // Higher total views have higher priority.
};
priority_queue<pair<long long, string>, vector<pair<long long, string>>, decltype(cmp)> pq(cmp);
// Insert each creator with their total views into the priority queue.
for (auto &entry : totalViews) {
pq.push({entry.second, entry.first});
}
// Extract top creators.
vector<vector<string>> result;
if (pq.empty()) return result;
long long maxTotalViews = pq.top().first;
// Pop all creators that have the maximum total views.
while (!pq.empty() && pq.top().first == maxTotalViews) {
string creator = pq.top().second;
pq.pop();
// Get the best video ID for this creator.
string videoID = bestVideo[creator].first;
result.push_back({creator, videoID});
}
return result;
}
};
Most Popular Video Creator solution in Java:Sub-Optimal
class Solution {
// Helper class to store the best video info for a creator.
class VideoInfo {
String id;
int views;
VideoInfo(String id, int views) {
this.id = id;
this.views = views;
}
}
// Helper class to store a creator with their total views.
class CreatorView {
String creator;
long totalViews;
CreatorView(String creator, long totalViews) {
this.creator = creator;
this.totalViews = totalViews;
}
}
public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
// Map to store total views for each creator.
Map<String, Long> totalViewsMap = new HashMap<>();
// Map to store the best video (video ID and its view count) for each creator.
Map<String, VideoInfo> bestVideoMap = new HashMap<>();
int n = creators.length;
for (int i = 0; i < n; i++) {
String creator = creators[i];
String id = ids[i];
int viewCount = views[i];
// Update the total view count for the creator.
totalViewsMap.put(creator, totalViewsMap.getOrDefault(creator, 0L) + viewCount);
// Update the best video for the creator.
if (!bestVideoMap.containsKey(creator)) {
bestVideoMap.put(creator, new VideoInfo(id, viewCount));
} else {
VideoInfo currentBest = bestVideoMap.get(creator);
if (viewCount > currentBest.views) {
bestVideoMap.put(creator, new VideoInfo(id, viewCount));
} else if (viewCount == currentBest.views && id.compareTo(currentBest.id) < 0) {
bestVideoMap.put(creator, new VideoInfo(id, viewCount));
}
}
}
// Priority queue (max-heap) to sort creators by total views in descending order.
PriorityQueue<CreatorView> pq = new PriorityQueue<>((a, b) -> Long.compare(b.totalViews, a.totalViews));
// Insert each creator along with their total views into the priority queue.
for (Map.Entry<String, Long> entry : totalViewsMap.entrySet()) {
pq.offer(new CreatorView(entry.getKey(), entry.getValue()));
}
// Extract all creators with the maximum total views.
List<List<String>> result = new ArrayList<>();
if (pq.isEmpty()) {
return result;
}
long maxTotalViews = pq.peek().totalViews;
while (!pq.isEmpty() && pq.peek().totalViews == maxTotalViews) {
CreatorView cv = pq.poll();
// Retrieve the best video for this creator.
VideoInfo vi = bestVideoMap.get(cv.creator);
result.add(Arrays.asList(cv.creator, vi.id));
}
return result;
}
}Most Popular Video Creator solution in Python :Sub-Optimal
import heapq
from collections import defaultdict
from typing import List
class Solution:
def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
# Dictionary to accumulate total views for each creator.
total_views = defaultdict(int)
# Dictionary to store the best video for each creator (video ID and its view count).
best_video = {}
# Process each video.
for creator, video, view in zip(creators, ids, views):
total_views[creator] += view
# Update best video if creator is new or if current video is better.
if creator not in best_video:
best_video[creator] = (video, view)
else:
cur_video, cur_view = best_video[creator]
if view > cur_view or (view == cur_view and video < cur_video):
best_video[creator] = (video, view)
# Build a max-heap (using negative total views since heapq is a min-heap)
heap = [(-tv, creator) for creator, tv in total_views.items()]
heapq.heapify(heap)
result = []
# If heap is empty, return the result.
if not heap:
return result
# The maximum total views is the negative of the first element's value.
max_views = -heap[0][0]
# Extract all creators with total views equal to max_views.
while heap and -heap[0][0] == max_views:
_, creator = heapq.heappop(heap)
result.append([creator, best_video[creator][0]])
return result
Most Popular Video Creator solution in Javascript :Sub-Optimal
/**
* @param {string[]} creators
* @param {string[]} ids
* @param {number[]} views
* @return {string[][]}
*/
var mostPopularCreator = function(creators, ids, views) {
// Map to store total views for each creator.
const totalViews = new Map();
// Map to store the best video (id and its view count) for each creator.
const bestVideo = new Map();
// Process each video.
for (let i = 0; i < creators.length; i++) {
const creator = creators[i];
const id = ids[i];
const view = views[i];
// Update total views.
totalViews.set(creator, (totalViews.get(creator) || 0) + view);
// Update best video for the creator.
if (!bestVideo.has(creator)) {
bestVideo.set(creator, { id: id, views: view });
} else {
const currentBest = bestVideo.get(creator);
if (view > currentBest.views || (view === currentBest.views && id < currentBest.id)) {
bestVideo.set(creator, { id: id, views: view });
}
}
}
// Create an array to simulate a priority queue.
// Each element is an object with creator and total views.
const creatorsArr = [];
for (const [creator, total] of totalViews.entries()) {
creatorsArr.push({ creator, total });
}
// Sort the array in descending order of total views.
creatorsArr.sort((a, b) => b.total - a.total);
// Extract all creators with the maximum total views.
const result = [];
const maxViews = creatorsArr[0].total;
for (const item of creatorsArr) {
if (item.total === maxViews) {
result.push([item.creator, bestVideo.get(item.creator).id]);
} else {
break;
}
}
return result;
};
Most Popular Video Creator complexity analysis:Time Complexity O(n log n).
Processing Videos: O(n)
- Iterate through all n videos, updating the two hash maps (one for total views and one for best video per creator).
- Each update operation is O(1) on average, contributing a total of O(n).
Building the heap:
- Insert each unique creator into the heap.
- If there are m unique creators (with m≤n ), each insertion takes O(logm).
- In the worst case where m=n, this step takes O(nlogn).
Extracting Top Creators:
- Removing creators from the heap also takes O(logm) per extraction.
- In the worst-case scenario (e.g., if all creators tie for the highest views), extracting all n creators results in O(nlogn).
- Overall Time Complexity:
- Combining the steps, the worst-case time complexity is O(n)+O(nlogn)+O(nlogn), which simplifies to O(nlogn).
Most Popular Video Creator complexity analysis: Space Complexity O(n).
- Auxiliary Space Complexity:O(n)
- The two hash maps (one for total views and one for best video) each store up to O(n) entries in the worst case.
- The heap stores at most O(n)elements.
- The additional space used by these data structures, excluding the input, is O(n)
- Overall Space Complexity:O(n)
- When including the input and the output, the overall space remains O(n) in the worst case, since the input arrays, the hash maps, the heap, and the output vector each require O(n) space.
The heap approach uses hash maps to record totals and best videos while a max-heap dynamically extracts top creators in O(n log n) time. Can we somehow avoid the log factor in time complexity smartly?
Optimal Approach
Intuition
Imagine you're organizing a talent show where each performer can have several acts, and each act earns applause points. Instead of maintaining a constantly updated leaderboard, you decide to record every act's points in a "scorebook" for each performer. As each act is completed, you update two things: the total applause each performer has accumulated and, separately, the best-performing act they've ever given. You also keep a note of the highest total applause seen so far.
Once all the acts are done, you simply go through your scorebook to find out which performer(s) reached that highest total applause. This is much like our optimal approach: instead of using a dynamic leaderboard (which is like repeatedly sorting all performers), we update our records on the fly with hash maps and keep track of the maximum. Finally, we scan through our records to pick out the top performers along with their best act. This method is efficient and straightforward, ensuring you only process each act once and then quickly retrieve the final winners.
How does the optimal solution track the highest total views, and why is this important
As we update the total views for each creator, we also maintain a variable that records the maximum total views seen so far. This is important because, after processing all videos, we can simply scan through our hash map and pick the creators whose total views equal this maximum value. This direct comparison avoids the need for additional sorting or complex data structures.
Approach
Most Popular Video Creator algorithm includes following steps:
Step 1: Initialize two hash maps. One, called mostViews, stores each creator's total views. The other, called maxIds, stores for each creator the best video details (the highest view count and the corresponding video ID).
Step 2: Iterate through all the videos. For each video, add its view count to the creator’s total in mostViews and update maxIds for that creator if the current video has a higher view count, or if it ties, a lexicographically smaller ID.
Step 3: While iterating, maintain a variable maax that keeps track of the highest total views encountered among all creators.
Step 4: After processing all videos, go through the mostViews map and collect all creators whose total views equal maax. For each such creator, get their best video from maxIds and add the [creator, video ID] pair to the result.
Step 5: Return the result containing the top creators and their best video IDs.
Dry Run
Consider the following input:
creators = ["alice", "bob", "alice", "chris"]
ids = ["one", "two", "three", "four"]
views = [5, 10, 5, 4]
Step 1: For index 0, "alice" with video "one" gets 5 views.
- mostViews["alice"] becomes 5.
- maax is updated to 5.
- Since there's no record for "alice" yet, maxIds["alice"] is set to (5, "one").
Step 2: For index 1, "bob" with video "two" gets 10 views.
- mostViews["bob"] becomes 10.
- maax is updated to 10.
- maxIds["bob"] is set to (10, "two") because it's a new entry.
Step 3: For index 2, "alice" with video "three" gets 5 views.
- mostViews["alice"] is updated to 10 (5 + 5).
- maax remains 10 (max of 10 and 10).
- For "alice", the current best is (5, "one"). Since 5 equals the view count of "three", we compare IDs. "one" is lexicographically smaller than "three", so maxIds["alice"] remains (5, "one").
Step 4: For index 3, "chris" with video "four" gets 4 views.
- mostViews["chris"] becomes 4.
- maax remains 10.
- maxIds["chris"] is set to (4, "four").
Step 5: After processing, mostViews is {"alice": 10, "bob": 10, "chris": 4} and maax is 10.
- We iterate over mostViews and select creators with total views equal to maax.
- "alice" and "bob" both have 10 views.
- We use maxIds to retrieve their best video IDs: "alice" → "one" and "bob" → "two".
The final result is:
[["alice", "one"], ["bob", "two"]].
Code for All Languages
Most Popular Video Creator solution in C++ :Optimal
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
unordered_map<string, long long> totalViews; // Maps creator -> total views
unordered_map<string, pair<int, string>> bestVideo; // Maps creator -> {max video views, best video id}
long long maxTotalViews = 0;
int n = creators.size();
// Process each video.
for (int i = 0; i < n; i++) {
string creator = creators[i];
string video = ids[i];
int viewCount = views[i];
totalViews[creator] += viewCount;
maxTotalViews = max(maxTotalViews, totalViews[creator]);
// Update the best video for this creator.
if (bestVideo.find(creator) == bestVideo.end()) {
bestVideo[creator] = {viewCount, video};
} else {
// If current video has more views, update.
if (viewCount > bestVideo[creator].first) {
bestVideo[creator] = {viewCount, video};
}
// If views are equal, choose lexicographically smaller id.
else if (viewCount == bestVideo[creator].first && video < bestVideo[creator].second) {
bestVideo[creator] = {viewCount, video};
}
}
}
// Gather all creators with the maximum total views.
vector<vector<string>> result;
for (auto& p : totalViews) {
if (p.second == maxTotalViews) {
result.push_back({p.first, bestVideo[p.first].second});
}
}
return result;
}
};
Most Popular Video Creator solution in Java :Optimal
import java.util.*;
public class Solution {
// Helper class to store the best video details for a creator.
private static class BestVideo {
int views;
String videoId;
BestVideo(int views, String videoId) {
this.views = views;
this.videoId = videoId;
}
}
public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
// Map to store total views per creator.
Map<String, Long> totalViews = new HashMap<>();
// Map to store the best video for each creator.
Map<String, BestVideo> bestVideo = new HashMap<>();
int n = creators.length;
long maxTotalViews = 0;
// Process each video.
for (int i = 0; i < n; i++) {
String creator = creators[i];
String video = ids[i];
int viewCount = views[i];
// Update the total views for this creator.
long newTotal = totalViews.getOrDefault(creator, 0L) + viewCount;
totalViews.put(creator, newTotal);
maxTotalViews = Math.max(maxTotalViews, newTotal);
// Update the best video for this creator.
if (!bestVideo.containsKey(creator)) {
bestVideo.put(creator, new BestVideo(viewCount, video));
} else {
BestVideo currBest = bestVideo.get(creator);
if (viewCount > currBest.views) {
bestVideo.put(creator, new BestVideo(viewCount, video));
} else if (viewCount == currBest.views && video.compareTo(currBest.videoId) < 0) {
bestVideo.put(creator, new BestVideo(viewCount, video));
}
}
}
// Gather all creators whose total views equal the maximum total views.
List<List<String>> result = new ArrayList<>();
for (Map.Entry<String, Long> entry : totalViews.entrySet()) {
if (entry.getValue() == maxTotalViews) {
String creator = entry.getKey();
List<String> pair = new ArrayList<>();
pair.add(creator);
pair.add(bestVideo.get(creator).videoId);
result.add(pair);
}
}
return result;
}
// For testing purposes (input/output handling)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String[] creators = new String[n];
String[] ids = new String[n];
int[] views = new int[n];
for (int i = 0; i < n; i++) {
creators[i] = sc.next();
}
for (int i = 0; i < n; i++) {
ids[i] = sc.next();
}
for (int i = 0; i < n; i++) {
views[i] = sc.nextInt();
}
Solution sol = new Solution();
List<List<String>> result = sol.mostPopularCreator(creators, ids, views);
for (List<String> pair : result) {
System.out.println(pair.get(0) + " " + pair.get(1));
}
sc.close();
}
}
Most Popular Video Creator solution in Python :Optimal
class Solution(object):
def mostPopularCreator(self, creators, ids, views):
"""
:type creators: List[str]
:type ids: List[str]
:type views: List[int]
:rtype: List[List[str]]
"""
totalViews = {} # Maps each creator to their total views.
bestVideo = {} # Maps each creator to a tuple: (video id, view count) for the best video.
maxTotalViews = 0
n = len(creators)
for i in range(n):
creator = creators[i]
video = ids[i]
viewCount = views[i]
# Update the total views for the creator.
totalViews[creator] = totalViews.get(creator, 0) + viewCount
maxTotalViews = max(maxTotalViews, totalViews[creator])
# Update the best video for the creator.
if creator not in bestVideo:
bestVideo[creator] = (video, viewCount)
else:
currVideo, currView = bestVideo[creator]
if viewCount > currView or (viewCount == currView and video < currVideo):
bestVideo[creator] = (video, viewCount)
result = []
# Collect creators whose total views equals the maximum total views.
for creator, total in totalViews.items():
if total == maxTotalViews:
result.append([creator, bestVideo[creator][0]])
return result
Most Popular Video Creator solution in Javascript :Optimal
/**
* @param {string[]} creators
* @param {string[]} ids
* @param {number[]} views
* @return {string[][]}
*/
var mostPopularCreator = function(creators, ids, views) {
// Map to store total views for each creator.
const totalViews = new Map();
// Map to store the best video for each creator (object: { views, id }).
const bestVideo = new Map();
let maxTotalViews = 0;
for (let i = 0; i < creators.length; i++) {
const creator = creators[i];
const video = ids[i];
const viewCount = views[i];
// Update total views for the creator.
const newTotal = (totalViews.get(creator) || 0) + viewCount;
totalViews.set(creator, newTotal);
maxTotalViews = Math.max(maxTotalViews, newTotal);
// Update the best video for the creator.
if (!bestVideo.has(creator)) {
bestVideo.set(creator, { views: viewCount, id: video });
} else {
const currentBest = bestVideo.get(creator);
if (viewCount > currentBest.views ||
(viewCount === currentBest.views && video < currentBest.id)) {
bestVideo.set(creator, { views: viewCount, id: video });
}
}
}
// Build result by collecting creators with total views equal to maxTotalViews.
const result = [];
for (const [creator, total] of totalViews.entries()) {
if (total === maxTotalViews) {
result.push([creator, bestVideo.get(creator).id]);
}
}
return result;
};
Most Popular Video Creator complexity analysis:Time Complexity O(n).
- Processing Each Video:O(n).
- We iterate over all n videos once.
- For each video, we perform constant-time operations: updating the total views in the hash map (mostViews), updating the best video in the hash map (maxId), and updating the maximum total view variable (maax).
- Time for this step: O(n).
- Iterating Over Unique Creators: O(n)
- After processing the videos, we iterate over the entries in the mostViews hash map. In the worst case, there are m unique creators, and mmm can be as large as n.
- For each creator, we check if their total views equal maax and then add a result pair if so.
- Time for this step: O(m), which is O(n) in the worst case.
- Overall Time Complexity:O(n).
- Combining both steps gives an overall time complexity of O(n)+O(n)=O(n).
- Additional Considerations:
- Although comparing video IDs lexicographically might involve a constant factor (dependent on the length of the strings), the constraints (e.g., video ID lengths are small) allow us to treat these comparisons as O(1) operations in practice.
Most Popular Video Creator complexity analysis: Space Complexity O(n ).
Auxiliary Space Complexity:O(n)
The algorithm uses two hash maps and a result vector. In the worst case, if every video is from a unique creator, each hash map stores O(n) entries. Thus, the additional space used by these data structures is O(n).
Overall Space Complexity:O(n)
Including the input arrays (which take O(n)space) along with the auxiliary data structures, the overall space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Similar Problems
Design Video Sharing Platform
Design a video sharing platform that supports video uploads (with metadata like creator and title), view count updates, and retrieval of trending videos based on views. Outline how you would implement these operations using efficient data structures. Consider what methods and data structures (e.g., hash maps, heaps) would optimize performance even with a large volume of videos.
Design a Food Rating System
Design a system that initializes with arrays of foods, their cuisines, and ratings.
It should support updating the rating of any food and, given a cuisine, return the highest-rated food (using lexicographical order as a tiebreaker).
Implement the FoodRatings class with methods to change ratings and retrieve the top food for a specified cuisine.