What is the time complexity of Get Watched Videos by Your Friends?

The optimal solution has a time complexity of O(N+VlogV).

What is the space complexity of Get Watched Videos by Your Friends?

The space complexity is O(N+V).

What data structures are used to solve Get Watched Videos by Your Friends?

This problem uses Array, Hash Table, Breadth-First Search, Graph, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Get Watched Videos by Your Friends?

Insight 1: Breadth-first search (BFS) is the correct algorithm to traverse the social network graph and find all people at a given distance (level) from the starting person. Insight 2: A hash table (or counter) is useful for storing and counting the frequency of each watched video.

Which companies ask LeetCode 1311. Get Watched Videos by Your Friends in interviews?

This problem is frequently asked at Guidewire.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Get Watched Videos by Your Friends - LeetCode 1311 Solution

Get Watched Videos by Your Friends - Complete Solution Guide

Get Watched Videos by Your Friends is LeetCode problem 1311, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

There are n people, each person has a unique id between 0 and n-1 . Given the arrays watchedVideos and friends , where watchedVideos[i] and friends[i] contain the list of watched videos and the list of friends respectively for the person with id = i . Level 1 of videos are all watched videos by your friends, level 2 of videos are all watched videos by the friends of your friends and so on. In general, the level k of videos are all watched videos by people with the shortest path exactly equal to

Detailed Explanation

The problem asks us to find the videos watched by the friends of a person at a specific level (distance) in a social network. We are given the list of videos watched by each person and the list of friends for each person. We need to perform a breadth-first search (BFS) to find all people at the given level and then count the frequency of each video watched by these people. Finally, we return a sorted list of videos based on their frequencies (ascending) and then alphabetically (ascending) for videos with the same frequency.

Solution Approach

The solution uses a BFS algorithm to find all people at the specified `level`. It starts from the given `id` and explores the graph level by level. A `visited` set is maintained to prevent cycles and avoid revisiting people. Once the BFS reaches the desired `level`, it counts the frequencies of all videos watched by those people. Finally, the videos are sorted based on frequency (ascending) and alphabetically (ascending), and the result is returned as a list of videos.

Step-by-Step Algorithm

Step 1: Initialize a queue with the starting `id` and a set `visited` to keep track of visited nodes.
Step 2: Perform BFS up to the given `level`. In each level, iterate through the friends of each person in the current queue. If a friend hasn't been visited, add them to the queue and the `visited` set.
Step 3: After reaching the desired `level`, iterate through the people in the queue (the friends at that level).
Step 4: For each person at the target level, iterate through their `watchedVideos` and update a counter (hash table) to store the frequency of each video.
Step 5: Sort the videos based on their frequency (ascending) and alphabetically (ascending) if frequencies are equal.
Step 6: Extract the video names from the sorted list and return the list of videos.

Key Insights

Insight 1: Breadth-first search (BFS) is the correct algorithm to traverse the social network graph and find all people at a given distance (level) from the starting person.
Insight 2: A hash table (or counter) is useful for storing and counting the frequency of each watched video.
Insight 3: Sorting is needed to order the videos based on their frequencies and alphabetically.

Complexity Analysis

Time Complexity: O(N+VlogV)

Space Complexity: O(N+V)

Topics

This problem involves: Array, Hash Table, Breadth-First Search, Graph, Sorting.

Companies

Asked at: Guidewire.

Get Watched Videos by Your Friends | LeetCode 1311

Medium

Array Hash Table Breadth-First Search Graph Sorting

Time: O(N+VlogV)Space: O(N+V)

Solution Code

Available in:

import java.util.*;

class Solution {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        Queue<Integer> queue = new LinkedList<>(Arrays.asList(id));
        Set<Integer> visited = new HashSet<>(Arrays.asList(id));

        for (int i = 0; i < level; i++) {
            if (queue.isEmpty()) {
                return new ArrayList<>();
            }
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                int person = queue.poll();
                for (int friend : friends[person]) {
                    if (!visited.contains(friend)) {
                        visited.add(friend);
                        queue.offer(friend);
                    }
                }
            }
        }

        Map<String, Integer> videoCounts = new HashMap<>();
        for (int friendId : queue) {
            for (String video : watchedVideos.get(friendId)) {
                videoCounts.put(video, videoCounts.getOrDefault(video, 0) + 1);
            }
        }

        List<Map.Entry<String, Integer>> sortedItems = new ArrayList<>(videoCounts.entrySet());
        sortedItems.sort((a, b) -> {
            if (a.getValue().equals(b.getValue())) {
                return a.getKey().compareTo(b.getKey());
            } else {
                return a.getValue() - b.getValue();
            }
        });

        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : sortedItems) {
            result.add(entry.getKey());
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1311: Get Watched Videos by Your Friends - Detailed explanation and solution approaches.

Topics

Array Hash Table Breadth-First Search Graph Sorting

Companies

Guidewire

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1311

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a queue with the starting `id` and a set `visited` to keep track of visited nodes.
2
Step 2: Perform BFS up to the given `level`. In each level, iterate through the friends of each person in the current queue. If a friend hasn't been visited, add them to the queue and the `visited` set.
3
Step 3: After reaching the desired `level`, iterate through the people in the queue (the friends at that level).
4
Step 4: For each person at the target level, iterate through their `watchedVideos` and update a counter (hash table) to store the frequency of each video.
5
Step 5: Sort the videos based on their frequency (ascending) and alphabetically (ascending) if frequencies are equal.
6
Step 6: Extract the video names from the sorted list and return the list of videos.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(N+VlogV)

💾

Space Complexity

O(N+V)

📝

Why?

The BFS visits each person at most once, taking O(N) time. The counting of videos also takes O(N) in the worst-case as we iterate through watched videos of at most N friends. Sorting the distinct videos takes O(VlogV) time, where V is the number of distinct videos. The queue, visited set, and video counter all use O(N) and O(V) space respectively.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

Instead of BFS, DFS can also be used to find the people at a specific level. However, BFS is generally preferred for finding shortest paths or nodes at a specific distance in an unweighted graph.

Time: O(N + VlogV)Space: O(N + V)

Trade-offs: DFS might be less efficient than BFS in this specific scenario because BFS naturally explores the graph level by level, allowing us to easily stop at the required level. DFS requires additional logic to keep track of the depth during traversal.

✨

Key Insights

1Insight 1: Breadth-first search (BFS) is the correct algorithm to traverse the social network graph and find all people at a given distance (level) from the starting person.
2Insight 2: A hash table (or counter) is useful for storing and counting the frequency of each watched video.
3Insight 3: Sorting is needed to order the videos based on their frequencies and alphabetically.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Graph

Nodes connected by edges. Like a social network or city map!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: `level` is greater than the distance to any reachable person. The BFS might terminate early. The solution handles this by checking if the queue is empty during the BFS loop. If it's empty, it returns an empty list.
Edge case 2: `friends` array contains cycles. The `visited` set prevents infinite loops by ensuring each person is visited only once.
Edge case 3: No videos are watched by the friends at the specified level. The solution will return an empty list as the counter will be empty.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling cycles in the `friends` graph. Failing to use a `visited` set can lead to infinite loops and incorrect results.

✗Common mistake 2: Incorrect sorting logic. Forgetting to sort alphabetically after sorting by frequency can result in incorrect output for videos with the same frequency.

✗Common mistake 3: Not handling the case where the level is unreachable. The algorithm should return an empty list if the BFS terminates before reaching the desired level.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Recommending content on social media platforms. Finding friends of friends at a specific level and recommending videos or articles based on their viewing history.

🏦Real-world scenario 2: Analyzing network influence. Determining the reach of a piece of information or a product within a social network by finding the number of people at a specific degree of separation from the original source.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Get Watched Videos by Your Friends"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?