LeetCode 1892 - Page Recommendations II

The problem asks us to implement a page recommendation system based on users’ friendships and their page likes. We are given two database tables: Friendship and Likes.

leetcodeharddatabase

LeetCode Problem 1892

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem asks us to implement a page recommendation system based on users’ friendships and their page likes. We are given two database tables: Friendship and Likes. The Friendship table contains pairs of users who are friends, and the Likes table contains pairs of users and pages that they have liked.

The goal is to recommend pages to each user under the following rules: a page is recommended to a user if at least one of their friends likes it, but the user themselves has not liked it yet. The output should include user_id, page_id, and the number of friends who liked that page as friends_likes.

Important clarifications include: friendships are bidirectional, so if (1, 2) exists in Friendship, both user 1 is a friend of user 2 and vice versa. Also, a user may have no friends or may have liked all pages their friends liked, in which case there will be no recommendations for that user.

Edge cases include users with no friends, users who have liked all pages their friends like, pages liked by multiple friends (which should be counted correctly), and users appearing only as user2_id in Friendship.

Approaches

Brute-Force Approach

A naive approach is to iterate over every user, retrieve all their friends, then for each friend, retrieve the pages they liked. For each page, check if the user has already liked it. If not, increment a counter for how many friends like this page. This approach works but requires multiple nested loops: one over users, one over friends, and one over liked pages. For large datasets, this becomes prohibitively slow.

Optimal Approach

The key insight is that SQL allows us to join tables efficiently. We can first construct a full set of friendship pairs in both directions, join it with the Likes table to find all pages liked by friends, then exclude pages already liked by the user. Finally, we group by user_id and page_id to count the number of friends liking each page. This avoids nested loops and uses database set operations efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(U * F * P) O(P) Iterate through each user and each friend's liked pages; slow for large data
Optimal O(F + L) O(F + L) Use SQL joins and group by to efficiently count friends' likes

Algorithm Walkthrough

  1. Normalize friendships: Construct a list of (user_id, friend_id) pairs in both directions so that friendships are bidirectional.
  2. Join friends with likes: For each (user_id, friend_id) pair, join with the Likes table on friend_id to get pages liked by each friend.
  3. Exclude already liked pages: Left join or use a WHERE NOT EXISTS condition to ensure the user_id has not liked the page yet.
  4. Count friends liking each page: Group the result by user_id and page_id and use COUNT(*) to calculate how many friends liked the page.
  5. Return results: Output the final result as a table of user_id, page_id, and friends_likes.

Why it works: By joining friendships with the likes of friends and filtering out pages the user already likes, we are guaranteed to capture all candidate recommendations. Grouping ensures accurate counts of friends for each page.

Python Solution

class Solution:
    def recommendPages(self, Friendship: list[list[int]], Likes: list[list[int]]) -> list[list[int]]:
        from collections import defaultdict
        
        friends = defaultdict(set)
        user_likes = defaultdict(set)
        
        for u1, u2 in Friendship:
            friends[u1].add(u2)
            friends[u2].add(u1)
        
        for u, p in Likes:
            user_likes[u].add(p)
        
        recommendations = []
        
        for user in friends:
            candidate_pages = defaultdict(int)
            for friend in friends[user]:
                for page in user_likes.get(friend, []):
                    if page not in user_likes[user]:
                        candidate_pages[page] += 1
            for page, count in candidate_pages.items():
                recommendations.append([user, page, count])
        
        return recommendations

The Python implementation constructs a bidirectional friendship map and a user likes map. For each user, it iterates over friends’ liked pages, counts the likes, excludes pages the user already likes, and collects the results.

Go Solution

package main

func RecommendPages(Friendship [][]int, Likes [][]int) [][]int {
    friends := make(map[int]map[int]bool)
    userLikes := make(map[int]map[int]bool)
    
    for _, f := range Friendship {
        u1, u2 := f[0], f[1]
        if friends[u1] == nil {
            friends[u1] = make(map[int]bool)
        }
        if friends[u2] == nil {
            friends[u2] = make(map[int]bool)
        }
        friends[u1][u2] = true
        friends[u2][u1] = true
    }
    
    for _, l := range Likes {
        u, p := l[0], l[1]
        if userLikes[u] == nil {
            userLikes[u] = make(map[int]bool)
        }
        userLikes[u][p] = true
    }
    
    var recommendations [][]int
    
    for user, frSet := range friends {
        pageCount := make(map[int]int)
        for friend := range frSet {
            for page := range userLikes[friend] {
                if !userLikes[user][page] {
                    pageCount[page]++
                }
            }
        }
        for page, count := range pageCount {
            recommendations = append(recommendations, []int{user, page, count})
        }
    }
    
    return recommendations
}

The Go solution mirrors the Python version using maps of maps to track friends and likes. Go requires explicit map initialization and does not allow default empty sets, so we ensure each map is created before adding elements.

Worked Examples

For user 1 in Example 1:

  1. Friends: 2, 3, 4, 6
  2. Pages liked by friends: 23, 77, 24, 77, 56, 33, 88
  3. Exclude pages already liked by user 1: 88
  4. Count remaining pages: 77 (2 friends), 23 (1), 24 (1), 56 (1), 33 (1)
  5. Recommendations: [1, 77, 2], [1, 23, 1], [1, 24, 1], [1, 56, 1], [1, 33, 1]

Other users are processed similarly.

Complexity Analysis

Measure Complexity Explanation
Time O(F + L + U_F_P_f) F is number of friendships, L is number of likes, U is number of users, P_f is average pages liked by friends
Space O(F + L) Storing friendship map and likes map

The algorithm is efficient because each friendship and like is processed only once, and counting recommendations for each user scales with their number of friends and pages liked.

Test Cases

# Provided example
Friendship = [[1,2],[1,3],[1,4],[2,3],[2,4],[2,5],[6,1]]
Likes = [[1,88],[2,23],[3,24],[4,56],[5,11],[6,33],[2,77],[3,77],[6,88]]
sol = Solution()
assert sorted(sol.recommendPages(Friendship, Likes)) == sorted([
    [1,77,2],[1,23,1],[1,24,1],[1,56,1],[1,33,1],
    [2,24,1],[2,56,1],[2,11,1],[2,88,1],
    [3,88,1],[3,23,1],
    [4,88,1],[4,77,1],[4,23,1],
    [5,77,1],[5,23,1]
])

# No friends
assert Solution().recommendPages([], []) == []

# No recommendations
Friendship = [[1,2]]
Likes = [[1,10],[2,10]]
assert Solution().recommendPages(Friendship, Likes) == []

# Multiple friends like same page
Friendship = [[1,2],[1,3]]
Likes = [[2,5],[3,5]]
assert Solution().recommendPages(Friendship, Likes) == [[1,5,2]]
Test Why
Provided example Validates general case with multiple friends and pages
No friends Edge case where user has no friends
No recommendations Users have liked all friends’ pages
Multiple friends like same page Tests correct counting of friends_likes

Edge Cases

Edge Case 1: User with no friends. Users appearing only in Likes or isolated in Friendship will have no recommendations. Our algorithm skips users without friends naturally because there is no entry in the friends map.

Edge Case 2: Users have liked all friends’ pages. The `if page not in user_likes[user