LeetCode 1264 - Page Recommendations

This problem models a small social network with two database tables. The Friendship table stores friendship relationship

leetcodemediumdatabase

LeetCode Problem 1264

Difficulty: 🟡 Medium
Topics: Database

Solution

LeetCode 1264 - Page Recommendations

Problem Understanding

This problem models a small social network with two database tables.

The Friendship table stores friendship relationships between users. Each row (user1_id, user2_id) means those two users are friends. Friendship is effectively bidirectional, even though each pair appears only once in the table.

The Likes table stores which pages each user likes. Each row (user_id, page_id) means that user likes that page.

The task is to recommend pages to user_id = 1. A page should be recommended if:

  1. At least one friend of user 1 likes the page.
  2. User 1 does not already like the page.

The result must contain unique page IDs. If multiple friends like the same page, that page should still appear only once in the output.

The output table contains one column:

Column Meaning
recommended_page A page liked by a friend of user 1, but not already liked by user 1

The important detail is identifying all friends of user 1. Since friendships are stored as (user1_id, user2_id), user 1 can appear in either column. For example:

  • (1, 2) means user 2 is a friend of user 1
  • (6, 1) means user 6 is also a friend of user 1

A correct solution must handle both cases.

Another important requirement is removing duplicates. If two different friends like the same page, the page should appear only once in the final answer.

The problem guarantees that:

  • Friendship pairs are unique.
  • User-page likes are unique.
  • The tables are well-formed relational data.

The main edge cases are:

  • Friends appearing on either side of the friendship relation.
  • Multiple friends liking the same page.
  • User 1 already liking a page that friends also like.
  • User 1 having no friends.
  • Friends not liking any pages.
  • All friend-liked pages already being liked by user 1.

Approaches

Brute Force Approach

A brute force solution would examine every page liked by every user and repeatedly check whether:

  1. The user is a friend of user 1
  2. User 1 already likes the page
  3. The page has already been added to the result

One possible brute force strategy is:

  1. Scan the friendship table repeatedly to determine whether each user is a friend of user 1.
  2. For every row in Likes, check whether the user is a friend.
  3. For every candidate page, scan the Likes table again to determine whether user 1 already likes it.
  4. Use duplicate elimination at the end.

This works because every possible candidate page is examined. However, it is inefficient because the same data is repeatedly rescanned.

Optimal Approach

The key insight is that this is fundamentally a set filtering problem.

We only need three things:

  1. The set of user 1's friends
  2. The set of pages already liked by user 1
  3. Pages liked by those friends but not by user 1

In SQL, this becomes a clean combination of:

  • A derived table that extracts all friends of user 1
  • A join with the Likes table
  • A filter removing pages already liked by user 1
  • DISTINCT to eliminate duplicates

The optimal solution avoids repeated rescanning and lets the database engine efficiently perform joins and filtering.

Approach Time Complexity Space Complexity Notes
Brute Force O(F × L) O(L) Repeated scans of friendship and likes tables
Optimal O(F + L) O(F + L) Uses set-style filtering and joins efficiently

Here:

  • F = number of friendship rows
  • L = number of likes rows

Algorithm Walkthrough

Optimal SQL Algorithm

  1. First, identify all friends of user 1.

Since friendship is bidirectional, user 1 may appear in either column. We create a derived table that normalizes friendships into a single friend_id column.

If user1_id = 1, then the friend is user2_id.

If user2_id = 1, then the friend is user1_id. 2. Next, retrieve all pages liked by those friends.

We join the friend list with the Likes table using:

friend_id = Likes.user_id

This gives us every page liked by at least one friend. 3. Then, remove pages already liked by user 1.

We use a subquery or anti-join to exclude pages that already exist in:

SELECT page_id
FROM Likes
WHERE user_id = 1
  1. Finally, remove duplicates.

Multiple friends may like the same page, so we use DISTINCT to ensure each recommended page appears only once.

Why it works

The algorithm works because it precisely models the recommendation definition.

The friend extraction step guarantees that every friend of user 1 is included exactly once. The join with Likes guarantees that every page liked by those friends is considered. The exclusion filter guarantees that pages already liked by user 1 are removed. Finally, DISTINCT guarantees uniqueness in the result.

Together, these steps produce exactly the set of valid recommendations.

Python Solution

Although this is a Database problem and normally solved in SQL, the following Python implementation simulates the same logic using in-memory data structures.

from typing import List, Tuple, Set

class Solution:
    def pageRecommendations(
        self,
        friendships: List[Tuple[int, int]],
        likes: List[Tuple[int, int]]
    ) -> List[int]:

        user_id = 1

        friends: Set[int] = set()

        for user1, user2 in friendships:
            if user1 == user_id:
                friends.add(user2)
            elif user2 == user_id:
                friends.add(user1)

        liked_by_user: Set[int] = set()

        for user, page in likes:
            if user == user_id:
                liked_by_user.add(page)

        recommendations: Set[int] = set()

        for user, page in likes:
            if user in friends and page not in liked_by_user:
                recommendations.add(page)

        return list(recommendations)

The implementation follows the algorithm directly.

The first loop builds the friend set. Because friendships are bidirectional, the code checks both columns of each friendship row.

The second loop builds the set of pages already liked by user 1. A hash set is ideal because membership checks are constant time on average.

The third loop scans all likes again. If the liking user is a friend and the page is not already liked by user 1, the page is added to the recommendation set.

Using a set for recommendations automatically removes duplicates when multiple friends like the same page.

Go Solution

package main

type Solution struct{}

func (s Solution) pageRecommendations(
	friendships [][2]int,
	likes [][2]int,
) []int {

	userID := 1

	friends := make(map[int]bool)

	for _, friendship := range friendships {
		user1 := friendship[0]
		user2 := friendship[1]

		if user1 == userID {
			friends[user2] = true
		} else if user2 == userID {
			friends[user1] = true
		}
	}

	likedByUser := make(map[int]bool)

	for _, like := range likes {
		user := like[0]
		page := like[1]

		if user == userID {
			likedByUser[page] = true
		}
	}

	recommendations := make(map[int]bool)

	for _, like := range likes {
		user := like[0]
		page := like[1]

		if friends[user] && !likedByUser[page] {
			recommendations[page] = true
		}
	}

	result := []int{}

	for page := range recommendations {
		result = append(result, page)
	}

	return result
}

The Go version mirrors the Python logic closely.

Go does not have a built-in set type, so maps with bool values are used to simulate sets. This is common Go practice for membership testing and duplicate elimination.

Slices are used for the input and output collections. Since the problem allows returning results in any order, no sorting is required.

There are no integer overflow concerns because the algorithm only stores and compares IDs.

Worked Examples

Example 1

Input friendship table:

user1_id user2_id
1 2
1 3
1 4
2 3
2 4
2 5
6 1

Input likes table:

user_id page_id
1 88
2 23
3 24
4 56
5 11
6 33
2 77
3 77
6 88

Step 1: Find friends of user 1

Process each friendship row:

Friendship Action Friends Set
(1,2) add 2 {2}
(1,3) add 3 {2,3}
(1,4) add 4 {2,3,4}
(2,3) ignore {2,3,4}
(2,4) ignore {2,3,4}
(2,5) ignore {2,3,4}
(6,1) add 6 {2,3,4,6}

Final friend set:

{2, 3, 4, 6}

Step 2: Find pages liked by user 1

Like Row Action Liked Pages
(1,88) add 88 {88}

Final liked set:

{88}

Step 3: Build recommendations

Process all likes again:

User Page Friend? Already Liked? Add? Recommendations
1 88 No Yes No {}
2 23 Yes No Yes {23}
3 24 Yes No Yes {23,24}
4 56 Yes No Yes {23,24,56}
5 11 No No No {23,24,56}
6 33 Yes No Yes {23,24,56,33}
2 77 Yes No Yes {23,24,56,33,77}
3 77 Yes No Yes, duplicate removed {23,24,56,33,77}
6 88 Yes Yes No {23,24,56,33,77}

Final output:

[23, 24, 56, 33, 77]

Complexity Analysis

Measure Complexity Explanation
Time O(F + L) One pass over friendships and two passes over likes
Space O(F + L) Sets store friends, liked pages, and recommendations

The friendship table is scanned once to build the friend set. The likes table is scanned twice, once to build the set of pages already liked by user 1, and once to generate recommendations.

All set operations are average-case constant time, so the overall complexity remains linear in the input size.

Test Cases

from typing import List, Tuple

class Solution:
    def pageRecommendations(
        self,
        friendships: List[Tuple[int, int]],
        likes: List[Tuple[int, int]]
    ) -> List[int]:

        user_id = 1

        friends = set()

        for u1, u2 in friendships:
            if u1 == user_id:
                friends.add(u2)
            elif u2 == user_id:
                friends.add(u1)

        liked = set()

        for user, page in likes:
            if user == user_id:
                liked.add(page)

        recommendations = set()

        for user, page in likes:
            if user in friends and page not in liked:
                recommendations.add(page)

        return list(recommendations)

sol = Solution()

# Example case from problem statement
assert set(sol.pageRecommendations(
    [(1,2), (1,3), (1,4), (2,3), (2,4), (2,5), (6,1)],
    [(1,88), (2,23), (3,24), (4,56), (5,11),
     (6,33), (2,77), (3,77), (6,88)]
)) == {23, 24, 56, 33, 77}

# User has no friends
assert set(sol.pageRecommendations(
    [],
    [(2,10), (3,20)]
)) == set()

# Friends like pages already liked by user 1
assert set(sol.pageRecommendations(
    [(1,2), (1,3)],
    [(1,50), (2,50), (3,50)]
)) == set()

# Multiple friends like same page
assert set(sol.pageRecommendations(
    [(1,2), (1,3)],
    [(2,99), (3,99)]
)) == {99}

# Friend appears in second friendship column
assert set(sol.pageRecommendations(
    [(5,1)],
    [(5,42)]
)) == {42}

# Friends with multiple unique recommendations
assert set(sol.pageRecommendations(
    [(1,2), (1,3)],
    [(2,10), (2,20), (3,30)]
)) == {10, 20, 30}

# Non-friends should not affect recommendations
assert set(sol.pageRecommendations(
    [(1,2)],
    [(3,100), (4,200), (2,300)]
)) == {300}

# User 1 likes nothing initially
assert set(sol.pageRecommendations(
    [(1,2)],
    [(2,500)]
)) == {500}

# Empty likes table
assert set(sol.pageRecommendations(
    [(1,2), (1,3)],
    []
)) == set()
Test Why
Problem example Validates standard functionality
No friends Ensures empty friend graph handled correctly
Already liked pages Ensures exclusion logic works
Duplicate page likes Verifies duplicate elimination
Reverse friendship direction Ensures bidirectional friendship handling
Multiple recommendations Validates accumulation of pages
Non-friend likes Ensures filtering correctness
User likes nothing Tests empty liked set
Empty likes table Ensures no recommendations generated

Edge Cases

Friendships Stored in Reverse Direction

One subtle issue is that friendship rows are not guaranteed to store user 1 in the first column. A naive implementation that only checks user1_id = 1 would miss rows like (6,1).

The implementation handles this by checking both columns:

if user1 == 1:
    friend = user2
elif user2 == 1:
    friend = user1

This guarantees that all friends are discovered regardless of ordering.

Multiple Friends Liking the Same Page

Different friends may like the same page. Without duplicate handling, the result could contain repeated recommendations.

The implementation stores recommendations in a set, which automatically removes duplicates:

recommendations.add(page)

This guarantees uniqueness in the final output.

Friends Liking Pages Already Liked by User 1

A page should never be recommended if user 1 already likes it, even if many friends also like it.

This can easily cause bugs if recommendation generation happens before exclusion filtering.

The implementation prevents this by maintaining a liked_by_user set and checking membership before adding recommendations:

if page not in liked_by_user:

This guarantees that already-liked pages are excluded from the result.