Problem Description

You are given three arrays of the same length n:

• creators: string array containing creator names
• ids: string array containing video IDs
• views: integer array containing view counts

Each index i represents a video where:

• creators[i] is the creator who made the video
• ids[i] is the video's ID
• views[i] is the number of views for that video

The popularity of a creator is defined as the total sum of views across all their videos.

Your task is to find:

1. The creator(s) with the highest popularity (if multiple creators tie for highest, find all of them)
2. For each of these top creators, find the ID of their most viewed video
   • If a creator has multiple videos with the same highest view count, choose the ID that is lexicographically smallest

Important notes:

• Different videos can have the same ID (IDs don't uniquely identify videos)
• Videos with the same ID are still considered distinct videos with their own view counts

Return a 2D array where each element is [creator_name, most_popular_video_id] representing a creator with the highest popularity and the ID of their most popular video. The order of the results doesn't matter.

Example scenario: If creator "Alice" has videos with IDs ["video1", "video2"] and views [100, 200], Alice's popularity is 300 and her most popular video ID is "video2".

Intuition

To solve this problem, we need to track two key pieces of information for each creator:

1. Their total popularity (sum of all their video views)
2. Their most popular video's ID

The natural approach is to process all videos once and aggregate the data by creator. As we iterate through the videos, we can simultaneously:

• Add up the views for each creator to calculate their total popularity
• Keep track of which video is currently the most popular for each creator

For tracking the most popular video per creator, we need to handle the tie-breaking rule: when multiple videos have the same view count, we choose the lexicographically smallest ID. This means whenever we encounter a new video for a creator, we update their most popular video if:

• The new video has more views than the current most popular, OR
• The new video has the same views but a lexicographically smaller ID

Using hash tables (dictionaries) is ideal here because:

• We need to group data by creator name (which can be any string)
• We need quick lookups and updates as we process each video
• The number of unique creators is unknown beforehand

After processing all videos, finding the answer becomes straightforward:

1. Find the maximum total popularity across all creators
2. Return all creators who have this maximum popularity along with their most popular video's ID

The key insight is that we can do all the necessary bookkeeping in a single pass through the data, making this solution efficient with O(n) time complexity where n is the number of videos.

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

Solution Approach

We use two hash tables to solve this problem:

• cnt: Maps each creator to their total view count (popularity)
• d: Maps each creator to the index of their most popular video

Step 1: Process all videos

We iterate through all three arrays simultaneously using zip(creators, ids, views) along with enumerate to keep track of indices:

for k, (c, i, v) in enumerate(zip(creators, ids, views)):

For each video:

• Add the views to the creator's total: cnt[c] += v
• Update the creator's most popular video index if needed

Step 2: Track the most popular video for each creator

For updating the most popular video, we check three conditions:

if c not in d or views[d[c]] < v or (views[d[c]] == v and ids[d[c]] > i):
    d[c] = k

This updates the index when:

1. c not in d: First video for this creator
2. views[d[c]] < v: Current video has more views than the stored one
3. views[d[c]] == v and ids[d[c]] > i: Same views but current video has lexicographically smaller ID

Step 3: Find the maximum popularity

After processing all videos, find the highest total view count:

mx = max(cnt.values())

Step 4: Build the result

Create the answer by finding all creators with maximum popularity:

return [[c, ids[d[c]]] for c, x in cnt.items() if x == mx]

For each creator c with popularity x equal to mx, we include [creator_name, most_popular_video_id] where the video ID is retrieved using ids[d[c]] (the ID at the stored index).

Time Complexity: O(n) where n is the number of videos, as we iterate through the arrays once and perform constant-time operations for each video.

Space Complexity: O(m) where m is the number of unique creators, for storing the hash tables.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input:

• creators = ["Alice", "Bob", "Alice", "Chris", "Bob"]
• ids = ["video1", "video2", "video3", "video4", "video2"]
• views = [100, 200, 150, 50, 300]

Step 1: Initialize our hash tables

• cnt = {} (for tracking total views per creator)
• d = {} (for tracking index of most popular video per creator)

Step 2: Process each video

Video 0: creator="Alice", id="video1", views=100

• cnt["Alice"] = 100 (first video for Alice)
• d["Alice"] = 0 (store index 0 as Alice's most popular video)

Video 1: creator="Bob", id="video2", views=200

• cnt["Bob"] = 200 (first video for Bob)
• d["Bob"] = 1 (store index 1 as Bob's most popular video)

Video 2: creator="Alice", id="video3", views=150

• cnt["Alice"] = 100 + 150 = 250 (add to Alice's total)
• Check if we need to update d["Alice"]:
  • Current most popular: views[0] = 100
  • New video: views[2] = 150
  • Since 150 > 100, update d["Alice"] = 2

Video 3: creator="Chris", id="video4", views=50

• cnt["Chris"] = 50 (first video for Chris)
• d["Chris"] = 3 (store index 3 as Chris's most popular video)

Video 4: creator="Bob", id="video2", views=300

• cnt["Bob"] = 200 + 300 = 500 (add to Bob's total)
• Check if we need to update d["Bob"]:
  • Current most popular: views[1] = 200
  • New video: views[4] = 300
  • Since 300 > 200, update d["Bob"] = 4

Step 3: Find maximum popularity

• cnt = {"Alice": 250, "Bob": 500, "Chris": 50}
• mx = max(250, 500, 50) = 500

Step 4: Build result

• Only Bob has popularity = 500
• Bob's most popular video index is d["Bob"] = 4
• The ID at index 4 is ids[4] = "video2"
• Result: [["Bob", "video2"]]

Handling tie-breaking scenario: If Alice had two videos both with 150 views but IDs "video3" and "video1", we would choose "video1" because it's lexicographically smaller ("video1" < "video3").

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of videos (length of the input arrays).

• The code iterates through all videos once using zip(creators, ids, views), which takes O(n) time
• Inside the loop, dictionary operations (cnt[c] += v, checking/updating d[c]) are O(1) on average
• Finding the maximum value with max(cnt.values()) takes O(m) time where m is the number of unique creators, and m ≤ n
• The final list comprehension iterates through all unique creators O(m) and builds the result list
• Overall: O(n) + O(m) + O(m) = O(n) since m ≤ n

The space complexity is O(n).

• The cnt dictionary stores at most m unique creators with their total views, where m ≤ n, so O(m) space
• The d dictionary stores at most m unique creators with their video indices, so O(m) space
• The output list contains at most m creator-video pairs, so O(m) space
• In the worst case where all creators are unique, m = n
• Overall: O(m) = O(n) in the worst case

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

Common Pitfalls

Pitfall 1: Confusing Video ID with Video Index

The Problem: A common mistake is treating video IDs as unique identifiers when they're not. The problem explicitly states that different videos can have the same ID. This leads to incorrect logic where developers might try to use the ID as a key in a dictionary to track video information.

Incorrect Approach:

# WRONG: Using video ID as key
video_info = {}
for creator, video_id, view_count in zip(creators, ids, views):
    video_info[video_id] = view_count  # This overwrites data for duplicate IDs!

Correct Solution: Use the video's index position in the arrays as the unique identifier, not the video ID. Store indices in your tracking dictionaries and use them to reference back to the original arrays:

creator_best_video_index[creator] = index  # Store index, not ID
# Later retrieve the ID using: ids[creator_best_video_index[creator]]

Pitfall 2: Incorrect Lexicographic Comparison Logic

The Problem: When comparing videos with the same view count, the lexicographic comparison might be implemented backwards or at the wrong level of comparison.

Incorrect Approach:

# WRONG: Comparing current ID with stored ID incorrectly
if views[stored_index] == view_count and video_id < ids[stored_index]:
    # This would keep updating unnecessarily

Correct Solution: Only update when the current video has strictly better criteria. The condition should check if the stored video's ID is lexicographically larger (worse) than the current one:

if views[stored_index] == view_count and ids[stored_index] > video_id:
    creator_best_video_index[creator] = index

Pitfall 3: Not Handling First Occurrence Properly

The Problem: Forgetting to handle the case when encountering a creator for the first time can lead to KeyError or incorrect comparisons.

Incorrect Approach:

# WRONG: Assumes creator already exists in dictionary
if views[creator_best_video_index[creator]] < view_count:  # KeyError if creator not in dict!
    creator_best_video_index[creator] = index

Correct Solution: Always check if the creator exists in the dictionary first, or use defaultdict with proper initialization:

if (creator not in creator_best_video_index or 
    views[creator_best_video_index[creator]] < view_count or ...):
    creator_best_video_index[creator] = index

Pitfall 4: Returning Videos Instead of Video IDs

The Problem: The problem asks for the video ID in the result, not the video index or other information.

Incorrect Approach:

# WRONG: Returning the index instead of the ID
return [[creator, creator_best_video_index[creator]] ...]

Correct Solution: Use the stored index to retrieve the actual video ID from the ids array:

return [[creator, ids[creator_best_video_index[creator]]] ...]