Most Popular Video Creator

Medium

Asked by:

28 views

Topics:

ArraysStringsDynamic Programming

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⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum sizes of the `creators`, `ids`, and `views` arrays? Are they guaranteed to be the same length?
Can the `views` array contain negative values, zero, or extremely large values (e.g., exceeding the maximum value of a standard integer)?
If multiple creators have the same highest popularity, should the order of the creator-video ID pairs in the returned list be based on the order in which the creators first appear in the `creators` array, or is there a specific ordering required?
If a creator has multiple videos with the same maximum number of views, and the same smallest video ID, is that considered a valid solution, or are more tie-breaking criteria needed?
Are the `creators` and `ids` guaranteed to be non-empty? What should I return if they are empty?

Brute Force Solution

Approach

To find the most popular video creator using a brute force method, we will meticulously check each creator's videos. We will count the total views for each creator by going through every single video they've made.

Here's how the algorithm would work step-by-step:

Start with the first creator on the list.
Look at all of the videos made by that creator.
Add up the number of views for each of their videos to get their total views.
Write down the creator's name and their total view count.
Move on to the next creator and repeat the process of adding up their video views.
Continue this process until you've calculated the total views for every creator.
Once you have the total views for all creators, compare the numbers to find the highest total.
The creator with the highest total views is the most popular.

Code Implementation

def most_popular_video_creator_brute_force(creators, views):
    creator_views = {}

    # Accumulate total views for each creator.
    for i in range(len(creators)):
        creator = creators[i]
        view_count = views[i]

        if creator not in creator_views:
            # If a creator is not already present, create new entry.
            creator_views[creator] = 0

        creator_views[creator] += view_count

    most_popular_creator = None
    max_views = -1

    # Find the creator with the maximum views.
    for creator, total_views in creator_views.items():
        if total_views > max_views:
            # Update most popular creator if larger number of views found
            most_popular_creator = creator
            max_views = total_views

        elif total_views == max_views:
            # Break tie using lexicographical order
            if creator < most_popular_creator:
                most_popular_creator = creator

    return most_popular_creator

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of creators and m be the total number of videos across all creators. The outer loop iterates through each of the n creators. For each creator, the inner operation sums up the views of their videos. In the worst case, we must iterate through all m videos to compute the views for each creator. Therefore, the time complexity is O(n*m).

Space Complexity

O(C) – The brute force method requires storing the creator's name and their total view count. Since we have to write down the total view count for each creator, we are creating a data structure whose size depends on the number of creators. Let C be the number of creators. Thus, the space complexity is O(C), where C is the number of video creators in the input. We store each creator name and their total views. Although we compare numbers to find the highest total, this comparison does not require extra space dependent on the input size.

Optimal Solution

Approach

To find the most popular video creator, we'll efficiently count the views for each creator. We'll use a way to quickly keep track of the total views for each creator without having to search through all the videos every time.

Here's how the algorithm would work step-by-step:

First, create a system to store the total views for each video creator. Think of it as a tally board.
Go through the list of videos, one by one.
For each video, look up the creator. Then, add the video's views to that creator's total views on the tally board.
After processing all videos, find the creator with the highest total views on the tally board.
If multiple creators have the same highest view count, list all of them.

Code Implementation

def most_popular_video_creator(creators, videos, views):
    creator_views = {}
    most_popular = ''
    max_views = 0

    # Aggregate total views for each creator
    for i in range(len(creators)):
        creator = creators[i]
        view_count = views[i]

        if creator in creator_views:
            creator_views[creator] += view_count
        else:
            creator_views[creator] = view_count

    best_videos = {}
    # Find the best video for each creator
    for i in range(len(creators)):
        creator = creators[i]
        video = videos[i]
        view_count = views[i]

        if creator not in best_videos:
            best_videos[creator] = (video, view_count)
        else:
            previous_video, previous_views = best_videos[creator]
            if view_count > previous_views:
                best_videos[creator] = (video, view_count)

    most_popular_creator = ""
    highest_views = 0
    # Find the most popular creator based on total views
    for creator, total_views in creator_views.items():
        if total_views > highest_views:
            # Update the most popular creator if current creator has more views
            most_popular_creator = creator
            highest_views = total_views
        elif total_views == highest_views and creator < most_popular_creator:
            most_popular_creator = creator

    return [most_popular_creator, best_videos[most_popular_creator][0]]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the list of videos once. For each video, it looks up the creator (which we assume is an O(1) operation using a hash map or similar data structure) and updates the creator's total views. After processing all videos, it finds the creator(s) with the maximum views, which involves iterating through the creators' view counts once more. Therefore, the dominant operation is iterating through the videos, making the overall time complexity O(n), where n is the number of videos.

Space Complexity

O(C) – The solution uses a tally board (essentially a hash map or dictionary) to store the total views for each creator. In the worst case, each video has a unique creator, so the tally board would store information for C unique creators, where C is the number of unique video creators. Therefore, the auxiliary space used is proportional to the number of unique creators. This simplifies to O(C).

Edge Cases

Case	How to Handle
Empty input arrays (creators, ids, views)	Return an empty list since there are no creators or videos.
Null input arrays (creators, ids, views)	Throw IllegalArgumentException or return an empty list after null check, depending on API contract.
Arrays creators, ids, and views have different lengths	Throw IllegalArgumentException as the input is invalid and there is no one-to-one mapping of video, creator and view count.
Input arrays with a single element each	The algorithm should correctly identify the single creator and their video as the most popular.
Multiple creators with the same maximum popularity	The algorithm should return a list of pairs containing all such creators and their most popular videos.
A creator has multiple videos with the same maximum view count	The algorithm must choose the video with the smallest ID among those with the maximum view count for that creator.
Large number of views causing integer overflow	Use long instead of int to store views and popularity to avoid potential overflow issues.
Creator names are very long strings	The hash map approach should still work correctly since string keys are supported, but consider potential memory usage.

Empty input arrays (creators, ids, views)

How to Handle:

Return an empty list since there are no creators or videos.

Null input arrays (creators, ids, views)

How to Handle:

Throw IllegalArgumentException or return an empty list after null check, depending on API contract.

Arrays creators, ids, and views have different lengths

How to Handle:

Throw IllegalArgumentException as the input is invalid and there is no one-to-one mapping of video, creator and view count.

Input arrays with a single element each

How to Handle:

The algorithm should correctly identify the single creator and their video as the most popular.

Multiple creators with the same maximum popularity

How to Handle:

The algorithm should return a list of pairs containing all such creators and their most popular videos.

A creator has multiple videos with the same maximum view count

How to Handle:

The algorithm must choose the video with the smallest ID among those with the maximum view count for that creator.

Large number of views causing integer overflow

How to Handle:

Use long instead of int to store views and popularity to avoid potential overflow issues.

Creator names are very long strings

How to Handle:

The hash map approach should still work correctly since string keys are supported, but consider potential memory usage.