# Most Popular Video Creator
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-popular-video-creator)
Canonical: https://scaleengineer.com/dsa/problems/most-popular-video-creator
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String, Heap (Priority Queue)
---
## Problem
You are given two string arrays `creators` and `ids`, and an integer array `views`, all of length `n`. The `ith` 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 `id`s do not uniquely identify a video. For example, two videos with the same ID are considered as distinct videos with their own viewcount.

Returna **2D array** of **strings** `answer` where `answer[i] = [creatorsi, idi]` means that `creatorsi` has the **highest** popularity and `idi` 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 <= 105`
* `1 <= creators[i].length, ids[i].length <= 5`
* `creators[i]` and `ids[i]` consist only of lowercase English letters.
* `0 <= views[i] <= 105`

# Approaches
## Brute-Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
    Set<String> uniqueCreators = new HashSet<>(Arrays.asList(creators));
    Map<String, Long> popularityMap = new HashMap<>();
    Map<String, String> bestIdMap = new HashMap<>();
    long maxPopularity = 0;

    for (String creator : uniqueCreators) {
        long currentPopularity = 0;
        int maxView = -1;
        String bestId = "";
        for (int i = 0; i < creators.length; i++) {
            if (creators[i].equals(creator)) {
                currentPopularity += views[i];
                if (views[i] > maxView) {
                    maxView = views[i];
                    bestId = ids[i];
                } else if (views[i] == maxView) {
                    if (bestId.isEmpty() || ids[i].compareTo(bestId) < 0) {
                        bestId = ids[i];
                    }
                }
            }
        }
        popularityMap.put(creator, currentPopularity);
        bestIdMap.put(creator, bestId);
        if (currentPopularity > maxPopularity) {
            maxPopularity = currentPopularity;
        }
    }

    List<List<String>> result = new ArrayList<>();
    for (String creator : uniqueCreators) {
        if (popularityMap.get(creator) == maxPopularity) {
            result.add(Arrays.asList(creator, bestIdMap.get(creator)));
        }
    }
    return result;
}
```
### 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.

## Grouping by Sorting
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.
**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.
**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.
### Explanation
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.

```java
class Video {
    String creator;
    String id;
    int view;
    Video(String c, String i, int v) {
        this.creator = c;
        this.id = i;
        this.view = v;
    }
}

public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
    int n = creators.length;
    List<Video> videoList = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        videoList.add(new Video(creators[i], ids[i], views[i]));
    }

    videoList.sort(Comparator.comparing(v -> v.creator));

    List<List<String>> result = new ArrayList<>();
    long maxPopularity = -1;

    int i = 0;
    while (i < n) {
        String currentCreator = videoList.get(i).creator;
        int j = i;
        long currentPopularity = 0;
        int maxView = -1;
        String bestId = "";

        while (j < n && videoList.get(j).creator.equals(currentCreator)) {
            Video video = videoList.get(j);
            currentPopularity += video.view;
            if (video.view > maxView) {
                maxView = video.view;
                bestId = video.id;
            } else if (video.view == maxView) {
                if (bestId.isEmpty() || video.id.compareTo(bestId) < 0) {
                    bestId = video.id;
                }
            }
            j++;
        }

        if (currentPopularity > maxPopularity) {
            maxPopularity = currentPopularity;
            result.clear();
            result.add(Arrays.asList(currentCreator, bestId));
        } else if (currentPopularity == maxPopularity) {
            result.add(Arrays.asList(currentCreator, bestId));
        }
        i = j;
    }
    return result;
}
```
### 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.

## Single-Pass with Hash Map
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.
**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.
**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.
### Explanation
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.

```java
class CreatorStats {
    long totalPopularity;
    int maxView;
    String bestId;

    CreatorStats(long p, int v, String id) {
        this.totalPopularity = p;
        this.maxView = v;
        this.bestId = id;
    }
}

public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
    Map<String, CreatorStats> statsMap = new HashMap<>();
    int n = creators.length;

    for (int i = 0; i < n; i++) {
        String creator = creators[i];
        String id = ids[i];
        int view = views[i];

        statsMap.putIfAbsent(creator, new CreatorStats(0, -1, ""));
        CreatorStats stats = statsMap.get(creator);
        
        stats.totalPopularity += view;

        if (view > stats.maxView) {
            stats.maxView = view;
            stats.bestId = id;
        } else if (view == stats.maxView) {
            if (stats.bestId.isEmpty() || id.compareTo(stats.bestId) < 0) {
                stats.bestId = id;
            }
        }
    }

    long maxPopularity = -1;
    for (CreatorStats stats : statsMap.values()) {
        if (stats.totalPopularity > maxPopularity) {
            maxPopularity = stats.totalPopularity;
        }
    }

    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<String, CreatorStats> entry : statsMap.entrySet()) {
        if (entry.getValue().totalPopularity == maxPopularity) {
            result.add(Arrays.asList(entry.getKey(), entry.getValue().bestId));
        }
    }
    return result;
}
```
### 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.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 ]
```