Most Popular Video Creator

Med

#2240Time: O(C * N * L), where `N` is the number of videos, `C` is the number of unique creators, and `L` is the maximum length of the strings. In the worst case, `C` can be up to `N`, leading to a complexity of O(N² * L).Space: O(C * L), where `C` is the number of unique creators and `L` is the maximum length of a creator's name or video ID. This space is used for the set of unique creators and the two maps.

Algorithms

Sorting

Data structures

Array Hash Table String Heap (Priority Queue)

Prompt

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 1:

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.

Example 2:

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⁵
1 <= creators[i].length, ids[i].length <= 5
creators[i] and ids[i] consist only of lowercase English letters.
0 <= views[i] <= 10⁵

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves a straightforward but inefficient method. It first identifies all unique creators. Then, for each unique creator, it iterates through the entire list of videos to calculate their total popularity and separately finds their most popular video. This results in a nested loop structure, making it very slow for large inputs.

Algorithm

Create a Set of unique creators from the creators array.
Create two maps: popularityMap<String, Long> to store total views for each creator, and bestIdMap<String, String> to store the ID of the most viewed video.
For each creator in the set of unique creators:
- Initialize totalViews = 0, maxView = -1, bestId = "".
- Iterate through all videos from i = 0 to n-1.
- If creators[i] equals the current creator:
  - Add views[i] to totalViews.
  - Compare views[i] with maxView to find the best video ID, handling ties by choosing the lexicographically smaller ID.
- After iterating through all videos, store the final totalViews in popularityMap and bestId in bestIdMap for the current creator.
Find the maxPopularity by iterating through the values of popularityMap.
Create an empty result list.
For each creator in the set of unique creators:
- If popularityMap.get(creator) equals maxPopularity, add [creator, bestIdMap.get(creator)] to the result list.
Return the result list.

Walkthrough

The brute-force strategy separates the problem into distinct, sequential steps. First, we find all unique creators by adding them to a Set. Then, for each of these unique creators, we perform a full scan of the input arrays. During this scan, we calculate two things: the sum of all their video views (their popularity) and identify which of their videos has the highest view count (resolving ties with the lexicographically smallest ID). These two pieces of information (total popularity and best video ID) are stored in two separate maps, keyed by the creator's name. After processing all unique creators, we find the maximum popularity value from our popularity map. Finally, we iterate through the unique creators one last time. If a creator's popularity matches the maximum, we retrieve their name and their best video ID from our maps and add the pair to the result list.

1public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {2    Set<String> uniqueCreators = new HashSet<>(Arrays.asList(creators));3    Map<String, Long> popularityMap = new HashMap<>();4    Map<String, String> bestIdMap = new HashMap<>();5    long maxPopularity = 0;6 7    for (String creator : uniqueCreators) {8        long currentPopularity = 0;9        int maxView = -1;10        String bestId = "";11        for (int i = 0; i < creators.length; i++) {12            if (creators[i].equals(creator)) {13                currentPopularity += views[i];14                if (views[i] > maxView) {15                    maxView = views[i];16                    bestId = ids[i];17                } else if (views[i] == maxView) {18                    if (bestId.isEmpty() || ids[i].compareTo(bestId) < 0) {19                        bestId = ids[i];20                    }21                }22            }23        }24        popularityMap.put(creator, currentPopularity);25        bestIdMap.put(creator, bestId);26        if (currentPopularity > maxPopularity) {27            maxPopularity = currentPopularity;28        }29    }30 31    List<List<String>> result = new ArrayList<>();32    for (String creator : uniqueCreators) {33        if (popularityMap.get(creator) == maxPopularity) {34            result.add(Arrays.asList(creator, bestIdMap.get(creator)));35        }36    }37    return result;38}

Complexity

Time

O(C * N * L), where `N` is the number of videos, `C` is the number of unique creators, and `L` is the maximum length of the strings. In the worst case, `C` can be up to `N`, leading to a complexity of O(N² * L).

Space

O(C * L), where `C` is the number of unique creators and `L` is the maximum length of a creator's name or video ID. This space is used for the set of unique creators and the two maps.

Trade-offs

Pros

Conceptually simple and easy to understand.
It clearly separates the concern of calculating popularity from finding the best video for each creator.

Cons

Highly inefficient due to nested loops, which cause repeated traversals of the input data.
Will almost certainly result in a "Time Limit Exceeded" (TLE) error on platforms like LeetCode for the given constraints.

This approach improves upon the brute-force method by first sorting the video data. By sorting the videos based on the creator's name, all videos by the same creator become adjacent in memory. This allows us to process all information for a single creator in one sequential scan over their block of videos, avoiding the need to re-scan the entire dataset for each creator.

Algorithm

Define a helper class, Video, to store creator, id, and view for each video.
Create a list of Video objects, populating it with the data from the input arrays.
Sort this list of Video objects primarily based on the creator's name. This groups all videos by the same creator together.
Initialize maxPopularity = -1 and an empty result list.
Iterate through the sorted list. Since videos are grouped, process one creator at a time.
For each block of videos belonging to the same creator:
- Calculate their totalViews.
- Find their maxSingleView and the corresponding bestId (handling ties).
After processing a creator's block, compare their totalViews with maxPopularity:
- If totalViews > maxPopularity, update maxPopularity, clear the result list, and add the current [creator, bestId].
- If totalViews == maxPopularity, just add [creator, bestId] to the result list.
Continue until all videos are processed and return the result list.

Walkthrough

To implement this, we first encapsulate the video data into a custom class or structure, say Video, containing the creator, id, and views. We create a list of these Video objects from the input arrays. The key step is sorting this list using the creator's name as the primary sort key. This operation groups all videos from the same creator consecutively.

After sorting, we can iterate through the list once. We use a sliding window or a two-pointer approach (i and j) to process one creator at a time. For each creator, we iterate over their contiguous block of videos, calculating their total popularity and finding their most popular video ID. Once we move to a new creator, we compare the previous creator's total popularity with the maximum popularity found so far and update our result list. If their popularity is higher, we clear the old results; if it's equal, we append them. This process continues until all creators have been evaluated.

1class Video {2    String creator;3    String id;4    int view;5    Video(String c, String i, int v) {6        this.creator = c;7        this.id = i;8        this.view = v;9    }10}11 12public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {13    int n = creators.length;14    List<Video> videoList = new ArrayList<>();15    for (int i = 0; i < n; i++) {16        videoList.add(new Video(creators[i], ids[i], views[i]));17    }18 19    videoList.sort(Comparator.comparing(v -> v.creator));20 21    List<List<String>> result = new ArrayList<>();22    long maxPopularity = -1;23 24    int i = 0;25    while (i < n) {26        String currentCreator = videoList.get(i).creator;27        int j = i;28        long currentPopularity = 0;29        int maxView = -1;30        String bestId = "";31 32        while (j < n && videoList.get(j).creator.equals(currentCreator)) {33            Video video = videoList.get(j);34            currentPopularity += video.view;35            if (video.view > maxView) {36                maxView = video.view;37                bestId = video.id;38            } else if (video.view == maxView) {39                if (bestId.isEmpty() || video.id.compareTo(bestId) < 0) {40                    bestId = video.id;41                }42            }43            j++;44        }45 46        if (currentPopularity > maxPopularity) {47            maxPopularity = currentPopularity;48            result.clear();49            result.add(Arrays.asList(currentCreator, bestId));50        } else if (currentPopularity == maxPopularity) {51            result.add(Arrays.asList(currentCreator, bestId));52        }53        i = j;54    }55    return result;56}

Complexity

Time

O(N * L * log N), dominated by the sorting step. `N` is the number of videos, and `L` is the max string length required for comparisons during the sort.

Space

O(N * L), where `N` is the number of videos and `L` is the max string length. This space is needed to store the list of `Video` objects before and after sorting.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Processes data for each creator in a single pass after the initial sort.

Cons

The sorting step has a time complexity of O(N log N), which is less efficient than a linear-time hash map approach.
Requires significant extra space, O(N * L), to create a copy of the data in a new list of objects, which can be large.

This is the most efficient approach, utilizing a hash map to aggregate data for each creator in a single pass. This avoids both the nested loops of the brute-force method and the O(N log N) overhead of sorting, achieving a linear time complexity.

Algorithm

Define a helper class, CreatorStats, to hold totalPopularity, maxSingleView, and bestVideoId.
Create a HashMap<String, CreatorStats> to map each creator's name to their statistics.
Iterate through the input videos from i = 0 to n-1.
- For each video (creator, id, view):
- Retrieve the CreatorStats for the creator from the map. If the creator is not yet in the map, create a new CreatorStats object.
- Add the current view to the creator's totalPopularity.
- Compare the current view with the creator's maxSingleView. If the current view is greater, or if it's equal and the current id is lexicographically smaller, update maxSingleView and bestVideoId.
- Put the updated CreatorStats object back into the map.
After the first pass, iterate through the map's values to find the overall maxPopularity.
Create an empty result list.
Iterate through the map's entries a final time. If a creator's totalPopularity equals maxPopularity, add their [creator, bestVideoId] to the result list.
Return the result list.

Walkthrough

The core of this optimal solution is a HashMap. The map's keys are the creator names, and the values are custom objects (e.g., a CreatorStats class) that store the aggregated information for each creator: their total popularity, the highest view count on any of their single videos, and the ID of that most-viewed video.

We iterate through the input arrays (creators, ids, views) just once. For each video, we look up its creator in the map. If the creator is new, we initialize their stats with the current video's data. If the creator already exists, we update their stats: we add the current video's views to their total popularity and check if this video is their new 'best' video (either more views, or same views with a lexicographically smaller ID).

After this single pass populates the map, we perform two quick passes over the map itself (which has at most N entries). The first pass finds the maximum popularity score among all creators. The second pass collects all creators whose popularity matches this maximum, adding their [creator, bestId] pair to the final result list.

1class CreatorStats {2    long totalPopularity;3    int maxView;4    String bestId;5 6    CreatorStats(long p, int v, String id) {7        this.totalPopularity = p;8        this.maxView = v;9        this.bestId = id;10    }11}12 13public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {14    Map<String, CreatorStats> statsMap = new HashMap<>();15    int n = creators.length;16 17    for (int i = 0; i < n; i++) {18        String creator = creators[i];19        String id = ids[i];20        int view = views[i];21 22        statsMap.putIfAbsent(creator, new CreatorStats(0, -1, ""));23        CreatorStats stats = statsMap.get(creator);24        25        stats.totalPopularity += view;26 27        if (view > stats.maxView) {28            stats.maxView = view;29            stats.bestId = id;30        } else if (view == stats.maxView) {31            if (stats.bestId.isEmpty() || id.compareTo(stats.bestId) < 0) {32                stats.bestId = id;33            }34        }35    }36 37    long maxPopularity = -1;38    for (CreatorStats stats : statsMap.values()) {39        if (stats.totalPopularity > maxPopularity) {40            maxPopularity = stats.totalPopularity;41        }42    }43 44    List<List<String>> result = new ArrayList<>();45    for (Map.Entry<String, CreatorStats> entry : statsMap.entrySet()) {46        if (entry.getValue().totalPopularity == maxPopularity) {47            result.add(Arrays.asList(entry.getKey(), entry.getValue().bestId));48        }49    }50    return result;51}

Complexity

Time

O(N * L), where `N` is the number of videos and `L` is the max string length. Each of the `N` videos involves map operations (hashing, comparison) which take O(L) time on average. The subsequent passes over the map take O(C * L), where `C <= N`.

Space

O(C * L), where `C` is the number of unique creators and `L` is the maximum string length. This space is used for the hash map.

Trade-offs

Pros

Optimal time complexity, as it processes all data in a single primary pass.
Conceptually clean, as it directly maps creators to their aggregated data.

Cons

Requires extra space for the hash map, which could be significant if there are many unique creators.

Solutions

Solution

1class Solution { public List < List < String >> mostPopularCreator ( String [] creators , String [] ids , int [] views ) { int n = ids . length ; Map < String , Long > cnt = new HashMap <>( n ); Map < String , Integer > d = new HashMap <>( n ); for ( int k = 0 ; k < n ; ++ k ) { String c = creators [ k ], i = ids [ k ]; long v = views [ k ]; cnt . merge ( c , v , Long: : sum ); if (! d . containsKey ( c ) || views [ d . get ( c )] < v || ( views [ d . get ( c )] == v && ids [ d . get ( c )]. compareTo ( i ) > 0 )) { d . put ( c , k ); } } long mx = 0 ; for ( long x : cnt . values ()) { mx = Math . max ( mx , x ); } List < List < String >> ans = new ArrayList <>(); for ( var e : cnt . entrySet ()) { if ( e . getValue () == mx ) { String c = e . getKey (); ans . add ( List . of ( c , ids [ d . get ( c )])); } } return ans ; } }

1class Solution { public: vector < vector < string >> mostPopularCreator ( vector < string >& creators , vector < string >& ids , vector < int >& views ) { unordered_map < string , long long > cnt ; unordered_map < string , int > d ; int n = ids . size (); for ( int k = 0 ; k < n ; ++ k ) { auto c = creators [ k ], id = ids [ k ]; int v = views [ k ]; cnt [ c ] += v ; if ( ! d . count ( c ) || views [ d [ c ]] < v || ( views [ d [ c ]] == v && ids [ d [ c ]] > id )) { d [ c ] = k ; } } long long mx = 0 ; for ( auto & [ _ , x ] : cnt ) { mx = max ( mx , x ); } vector < vector < string >> ans ; for ( auto & [ c , x ] : cnt ) { if ( x == mx ) { ans . push_back ({ c , ids [ d [ c ]]}); } } return ans ; } };

1class Solution : def mostPopularCreator ( self , creators : List [ str ], ids : List [ str ], views : List [ int ] ) -> List [ List [ str ]]: cnt = defaultdict ( int ) d = defaultdict ( int ) for k , ( c , i , v ) in enumerate ( zip ( creators , ids , views )): cnt [ c ] += v if c not in d or views [ d [ c ]] < v or ( views [ d [ c ]] == v and ids [ d [ c ]] > i ): d [ c ] = k mx = max ( cnt . values ()) return [[ c , ids [ d [ c ]]] for c , x in cnt . items () if x == mx ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public List < List < String >> mostPopularCreator ( String [] creators , String [] ids , int [] views ) { int n = ids . length ; Map < String , Long > cnt = new HashMap <>( n ); Map < String , Integer > d = new HashMap <>( n ); for ( int k = 0 ; k < n ; ++ k ) { String c = creators [ k ], i = ids [ k ]; long v = views [ k ]; cnt . merge ( c , v , Long: : sum ); if (! d . containsKey ( c ) || views [ d . get ( c )] < v || ( views [ d . get ( c )] == v && ids [ d . get ( c )]. compareTo ( i ) > 0 )) { d . put ( c , k ); } } long mx = 0 ; for ( long x : cnt . values ()) { mx = Math . max ( mx , x ); } List < List < String >> ans = new ArrayList <>(); for ( var e : cnt . entrySet ()) { if ( e . getValue () == mx ) { String c = e . getKey (); ans . add ( List . of ( c , ids [ d . get ( c )])); } } return ans ; } }

1class Solution { public: vector < vector < string >> mostPopularCreator ( vector < string >& creators , vector < string >& ids , vector < int >& views ) { unordered_map < string , long long > cnt ; unordered_map < string , int > d ; int n = ids . size (); for ( int k = 0 ; k < n ; ++ k ) { auto c = creators [ k ], id = ids [ k ]; int v = views [ k ]; cnt [ c ] += v ; if ( ! d . count ( c ) || views [ d [ c ]] < v || ( views [ d [ c ]] == v && ids [ d [ c ]] > id )) { d [ c ] = k ; } } long long mx = 0 ; for ( auto & [ _ , x ] : cnt ) { mx = max ( mx , x ); } vector < vector < string >> ans ; for ( auto & [ c , x ] : cnt ) { if ( x == mx ) { ans . push_back ({ c , ids [ d [ c ]]}); } } return ans ; } };

1class Solution : def mostPopularCreator ( self , creators : List [ str ], ids : List [ str ], views : List [ int ] ) -> List [ List [ str ]]: cnt = defaultdict ( int ) d = defaultdict ( int ) for k , ( c , i , v ) in enumerate ( zip ( creators , ids , views )): cnt [ c ] += v if c not in d or views [ d [ c ]] < v or ( views [ d [ c ]] == v and ids [ d [ c ]] > i ): d [ c ] = k mx = max ( cnt . values ()) return [[ c , ids [ d [ c ]]] for c , x in cnt . items () if x == mx ]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.