LeetCode 2720 - Popularity Percentage

LeetCode Problem 2720

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The Friends table stores friendship relationships between users on a social platform. Each row contains two user IDs, user1 and user2, indicating that those two users are friends with each other.

The task is to compute a popularity percentage for every user who appears anywhere in the table. The popularity percentage is defined as:

$\text{Popularity Percentage} = \frac{\text{Number of Friends}}{\text{Total Number of Users}} \times 100$

The final result must contain:

• The user ID
• The popularity percentage rounded to exactly 2 decimal places

The result must be sorted by user1 in ascending order.

An important detail is that friendships are bidirectional. Even though the table stores a row like (2,1), this means user 2 is friends with user 1, and user 1 is also friends with user 2. Therefore, every friendship contributes to the friend count of both users.

The total number of users is not given directly. We must determine it by collecting every distinct user ID that appears in either the user1 column or the user2 column.

The constraints imply that the table can contain many friendship relationships, so repeatedly scanning the table for every user would be inefficient. Instead, we should process the table in a single pass and aggregate friend counts efficiently.

Several edge cases are important:

• A user may appear only in user1 or only in user2, but they still count as a valid platform user.
• Every friendship must count for both participants.
• Rounding errors can occur if floating point arithmetic is not handled carefully.
• Duplicate friendships are prevented because (user1, user2) is the primary key.

Approaches

Brute Force Approach

A straightforward solution is to first collect all unique users, then for each user scan the entire Friends table and count how many rows contain that user either as user1 or user2.

This approach is correct because every friendship involving the current user contributes exactly one friend connection. After counting all friendships for each user, we divide by the total number of users and multiply by 100.

However, this method is inefficient. If there are U users and N friendship rows, then for every user we scan all rows again. This results in O(U × N) time complexity, which becomes expensive for large datasets.

Optimal Approach

The key observation is that every friendship contributes exactly one friend to both participating users. Therefore, instead of rescanning the table repeatedly, we can process each row once and increment the friend count for both users immediately.

We also need the total number of unique users. We can obtain this by combining both columns into a single set of users.

In SQL, the cleanest way to do this is:

1. Convert each friendship into two directed records using UNION ALL
2. Count friendships per user using GROUP BY
3. Compute the total number of distinct users
4. Calculate and round the percentage

This approach only requires linear processing of the table and avoids repeated scans.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(U × N)	O(U)	Scan the entire table for every user
Optimal	O(N)	O(U)	Aggregate friendship counts in a single pass

Algorithm Walkthrough

1. First, create a derived table that treats every friendship as bidirectional.

If the original row is (2,1), then:

• User 2 gains one friend
• User 1 gains one friend

We can represent this by creating two rows:

• (2,1)
• (1,2)

Using UNION ALL allows us to generate both directions efficiently. 2. Compute the total number of unique users.

Since users may appear in either column, we combine both columns using UNION and count distinct IDs. 3. Group the bidirectional friendship table by user ID.

Each row in the transformed table corresponds to one friendship contribution. Counting rows per user gives the total number of friends. 4. Calculate the popularity percentage.

For each user:

$\text{percentage_popularity} = \text{ROUND}\left(\frac{\text{friend_count}}{\text{total_users}} \times 100, 2\right)$ 5. Sort the final output by user ID in ascending order.

Why it works

The algorithm works because every friendship is represented exactly twice in the transformed table, once for each participant. Therefore, counting grouped rows accurately measures the number of friends each user has. The denominator uses the exact count of distinct platform users, so the computed percentage matches the problem definition precisely.

Python Solution

Although this is a database problem, LeetCode database solutions are typically expressed as SQL queries. Below is the correct SQL solution.

SELECT
    f.user1,
    ROUND(COUNT(*) * 100.0 / total.total_users, 2) AS percentage_popularity
FROM
(
    SELECT user1, user2 FROM Friends
    UNION ALL
    SELECT user2 AS user1, user1 AS user2 FROM Friends
) f
CROSS JOIN
(
    SELECT COUNT(*) AS total_users
    FROM
    (
        SELECT user1 AS user FROM Friends
        UNION
        SELECT user2 AS user FROM Friends
    ) users
) total
GROUP BY f.user1
ORDER BY f.user1;

The query begins by transforming the friendship relationships into a bidirectional representation using UNION ALL. This ensures both users receive credit for the friendship.

Next, the query computes the total number of unique users by combining both columns with UNION, which removes duplicates automatically.

The CROSS JOIN makes the total user count available to every grouped row. Then GROUP BY aggregates the friendship counts for each user.

Finally, the ROUND function formats the percentage to exactly two decimal places, and ORDER BY ensures ascending user order.

Go Solution

Database problems on LeetCode are solved with SQL, not Go code. However, if we simulate the logic programmatically, the equivalent Go implementation would look like this:

package main

import (
	"fmt"
	"sort"
)

type Friendship struct {
	user1 int
	user2 int
}

func popularityPercentage(friends []Friendship) map[int]float64 {
	friendCount := make(map[int]int)
	users := make(map[int]bool)

	for _, f := range friends {
		friendCount[f.user1]++
		friendCount[f.user2]++

		users[f.user1] = true
		users[f.user2] = true
	}

	totalUsers := float64(len(users))
	result := make(map[int]float64)

	for user, count := range friendCount {
		result[user] = float64(count) * 100.0 / totalUsers
	}

	return result
}

func main() {
	friends := []Friendship{
		{2, 1},
		{1, 3},
		{4, 1},
		{1, 5},
		{1, 6},
		{2, 6},
		{7, 2},
		{8, 3},
		{3, 9},
	}

	result := popularityPercentage(friends)

	var users []int
	for user := range result {
		users = append(users, user)
	}

	sort.Ints(users)

	for _, user := range users {
		fmt.Printf("User %d -> %.2f\n", user, result[user])
	}
}

The Go version uses hash maps to track both friend counts and unique users. Unlike SQL, we manually iterate through the friendships and update counts directly.

Floating point division is handled using float64, ensuring correct percentage calculations. Sorting is required because Go maps do not preserve order.

Worked Examples

Example 1

Input:

(2,1)
(1,3)
(4,1)
(1,5)
(1,6)
(2,6)
(7,2)
(8,3)
(3,9)

Step 1: Collect Unique Users

Friendship	Users Seen
(2,1)	{1,2}
(1,3)	{1,2,3}
(4,1)	{1,2,3,4}
(1,5)	{1,2,3,4,5}
(1,6)	{1,2,3,4,5,6}
(7,2)	{1,2,3,4,5,6,7}
(8,3)	{1,2,3,4,5,6,7,8}
(3,9)	{1,2,3,4,5,6,7,8,9}

Total users = 9

Step 2: Count Friendships

User	Friends	Count
1	2,3,4,5,6	5
2	1,6,7	3
3	1,8,9	3
4	1	1
5	1	1
6	1,2	2
7	2	1
8	3	1
9	3	1

Step 3: Compute Percentages

User	Formula	Result
1	(5 / 9) × 100	55.56
2	(3 / 9) × 100	33.33
3	(3 / 9) × 100	33.33
4	(1 / 9) × 100	11.11
5	(1 / 9) × 100	11.11
6	(2 / 9) × 100	22.22
7	(1 / 9) × 100	11.11
8	(1 / 9) × 100	11.11
9	(1 / 9) × 100	11.11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Each friendship row is processed a constant number of times
Space	O(U)	Storage for unique users and grouped counts

The query processes each friendship relationship once while building aggregated counts. The only additional memory required is for storing grouped friendship totals and unique users.

Test Cases

# Example case from the problem
assert round((5 / 9) * 100, 2) == 55.56  # user 1 popularity

# Single friendship
assert round((1 / 2) * 100, 2) == 50.00  # both users have one friend

# User connected to many others
assert round((4 / 5) * 100, 2) == 80.00  # hub user

# Minimal percentage
assert round((1 / 10) * 100, 2) == 10.00  # one friendship among many users

# Dense graph
assert round((3 / 4) * 100, 2) == 75.00  # highly connected user

# Rounding validation
assert round((2 / 3) * 100, 2) == 66.67  # repeating decimal rounding

# Symmetric friendship handling
assert 1 + 1 == 2  # each friendship counted for both users

Test	Why
Example case	Validates the official sample
Single friendship	Tests smallest nontrivial graph
Hub user	Tests large friend count
Minimal percentage	Tests small ratios
Dense graph	Tests highly connected users
Rounding validation	Ensures correct decimal rounding
Symmetric friendship	Ensures bidirectional counting

Edge Cases

One important edge case occurs when a user appears only in the user2 column and never in user1. A careless implementation that only groups on user1 would completely miss such users. The solution handles this by combining both columns using UNION.

Another critical edge case involves bidirectional friendships. Since friendships are inherently mutual, counting only the original rows would give each friendship credit to just one user. The UNION ALL transformation explicitly creates both directions, ensuring both users receive a friendship count increment.

Rounding is also a common source of bugs. Some percentages produce repeating decimals, such as 2 / 3 = 66.666.... Without proper rounding, the output may fail strict comparison tests. Using ROUND(..., 2) guarantees exactly two decimal places.

A final subtle case is duplicate user discovery. A user may appear many times across different friendships. Using UNION instead of UNION ALL when counting users ensures each platform user is counted exactly once in the denominator.