LeetCode 1355 - Activity Participants

This problem asks us to analyze participation counts for different activities and return only the activities whose parti

leetcodemediumdatabase

LeetCode Problem 1355

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze participation counts for different activities and return only the activities whose participant counts are neither the highest nor the lowest among all activities.

We are given two database tables:

The Friends table records which friend participates in which activity. Each row represents one friend and exactly one activity.

The Activities table contains the list of all activities.

The key observation is that every activity listed in Activities is guaranteed to appear in Friends, which means every activity has at least one participant. This guarantee simplifies the solution because we do not need to handle activities with zero participants.

The task is to compute how many friends participate in each activity, determine:

  • the maximum participant count
  • the minimum participant count

and then return all activities whose counts are strictly between those two values.

For the sample input:

Activity Participants
Eating 3
Singing 2
Horse Riding 1

The maximum count is 3, the minimum count is 1, and only Singing has a count that is neither maximum nor minimum.

An important detail is that multiple activities may share the same maximum or minimum count. Every activity with the maximum count must be excluded, and every activity with the minimum count must also be excluded.

The output may be returned in any order, so sorting is unnecessary unless explicitly requested.

Because this is a SQL database problem, the main challenge is constructing the correct aggregation and filtering logic using SQL operations such as:

  • GROUP BY
  • aggregate functions like COUNT
  • subqueries or common table expressions
  • filtering based on computed aggregates

Several edge cases are important:

  • If all activities have the same number of participants, then every activity is simultaneously both maximum and minimum, so the result is empty.
  • Multiple activities can tie for maximum participation.
  • Multiple activities can tie for minimum participation.
  • There may be only two distinct participation counts, in which case no activity qualifies.
  • Since every activity appears in Friends, we never need to handle null counts or missing joins.

Approaches

Brute Force Approach

A straightforward approach is to compute the participant count for every activity, store those counts, and then repeatedly compare each activity against all others to determine whether it has the maximum or minimum count.

The process would look like this:

  1. Count participants for every activity.
  2. For each activity:
  • Scan all other activities to determine whether its count is the maximum.
  • Scan all other activities again to determine whether its count is the minimum.
  1. Include the activity only if it is neither.

This works because every activity is explicitly compared against every other activity, guaranteeing correct identification of maximum and minimum counts.

However, this approach is inefficient because for n activities, each activity may compare itself against all others, leading to quadratic behavior.

Optimal Approach

The better solution is based on aggregation.

The key insight is that we only need three pieces of information:

  1. The participant count for every activity
  2. The global maximum participant count
  3. The global minimum participant count

Once we know these values, filtering becomes simple.

We first group the Friends table by activity and compute counts. Then we calculate the maximum and minimum counts across those grouped results. Finally, we return only the activities whose counts are not equal to either extreme.

This approach avoids repeated comparisons and performs aggregation only once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly compares every activity against all others
Optimal O(n) O(n) Uses aggregation once, then filters efficiently

Algorithm Walkthrough

  1. Group the Friends table by activity.

We need to know how many participants belong to each activity. Using GROUP BY activity allows SQL to collect all rows for the same activity together. 2. Compute the participant count for each group.

Using COUNT(*), we calculate the number of friends participating in each activity.

Example intermediate result:

activity cnt
Eating 3
Singing 2
Horse Riding 1
3. Determine the maximum participant count.

We apply MAX(cnt) over the grouped counts. In the example above, the maximum is 3. 4. Determine the minimum participant count.

We apply MIN(cnt) over the grouped counts. In the example above, the minimum is 1. 5. Filter activities whose counts are neither maximum nor minimum.

We keep only rows where:

cnt != max_cnt AND cnt != min_cnt
  1. Return the activity names.

The final result contains only the qualifying activities.

Why it works

The algorithm works because every activity is assigned exactly one participation count. The global maximum and minimum counts fully define which activities must be excluded. Any activity whose count differs from both extremes necessarily lies strictly between them, so it satisfies the problem requirements.

Python Solution

Although this is a database problem, LeetCode database solutions are written in SQL. The following represents the correct SQL solution embedded in Python string form for completeness.

class Solution:
    def activityParticipants(self):
        return """
        WITH activity_counts AS (
            SELECT
                activity,
                COUNT(*) AS participant_count
            FROM Friends
            GROUP BY activity
        )
        SELECT activity
        FROM activity_counts
        WHERE participant_count NOT IN (
            (SELECT MAX(participant_count) FROM activity_counts),
            (SELECT MIN(participant_count) FROM activity_counts)
        );
        """

The solution first creates a common table expression named activity_counts. This intermediate result stores each activity together with its participant count.

Next, the outer query filters the rows. The MAX and MIN subqueries compute the largest and smallest participation counts from the aggregated table.

Finally, the NOT IN condition removes all activities whose counts match either extreme.

Using a common table expression improves readability because the aggregation logic is written only once.

Go Solution

Again, because this is a database problem, the actual accepted solution is SQL. The following Go representation simply returns the SQL query.

package main

type Solution struct{}

func (s Solution) ActivityParticipants() string {
	return `
WITH activity_counts AS (
    SELECT
        activity,
        COUNT(*) AS participant_count
    FROM Friends
    GROUP BY activity
)
SELECT activity
FROM activity_counts
WHERE participant_count NOT IN (
    (SELECT MAX(participant_count) FROM activity_counts),
    (SELECT MIN(participant_count) FROM activity_counts)
);
`
}

The Go version mirrors the Python version exactly. Since the problem is fundamentally SQL-based, the Go code simply stores and returns the query string.

There are no concerns about integer overflow, slices, arrays, or nil handling because all computation occurs inside the SQL engine.

Worked Examples

Example 1

Input tables:

Friends

id name activity
1 Jonathan D. Eating
2 Jade W. Singing
3 Victor J. Singing
4 Elvis Q. Eating
5 Daniel A. Eating
6 Bob B. Horse Riding

Step 1: Group by activity

activity participants
Eating Jonathan D., Elvis Q., Daniel A.
Singing Jade W., Victor J.
Horse Riding Bob B.

Step 2: Count participants

activity count
Eating 3
Singing 2
Horse Riding 1

Step 3: Compute maximum and minimum

Metric Value
Maximum 3
Minimum 1

Step 4: Filter activities

activity count Keep?
Eating 3 No, maximum
Singing 2 Yes
Horse Riding 1 No, minimum

Final result:

activity
Singing

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row in Friends is processed once during grouping
Space O(n) The grouped aggregation stores counts for activities

The dominant operation is the GROUP BY aggregation over the Friends table. After aggregation, computing maximum and minimum values is linear in the number of distinct activities. Since each activity is processed a constant number of times, the total complexity remains linear.

Test Cases

# Example case
counts = {
    "Eating": 3,
    "Singing": 2,
    "Horse Riding": 1
}
assert [
    activity
    for activity, cnt in counts.items()
    if cnt not in (max(counts.values()), min(counts.values()))
] == ["Singing"]  # standard example

# All activities have same count
counts = {
    "A": 2,
    "B": 2,
    "C": 2
}
assert [
    activity
    for activity, cnt in counts.items()
    if cnt not in (max(counts.values()), min(counts.values()))
] == []  # everything excluded

# Multiple maximum activities
counts = {
    "A": 5,
    "B": 5,
    "C": 3,
    "D": 1
}
assert [
    activity
    for activity, cnt in counts.items()
    if cnt not in (max(counts.values()), min(counts.values()))
] == ["C"]  # both maximum activities removed

# Multiple minimum activities
counts = {
    "A": 4,
    "B": 2,
    "C": 2,
    "D": 5
}
assert set(
    activity
    for activity, cnt in counts.items()
    if cnt not in (max(counts.values()), min(counts.values()))
) == {"A"}  # both minimum activities removed

# Only two activities
counts = {
    "A": 10,
    "B": 1
}
assert [
    activity
    for activity, cnt in counts.items()
    if cnt not in (max(counts.values()), min(counts.values()))
] == []  # no middle activity

# Larger mixed case
counts = {
    "A": 7,
    "B": 3,
    "C": 5,
    "D": 1,
    "E": 6
}
assert set(
    activity
    for activity, cnt in counts.items()
    if cnt not in (max(counts.values()), min(counts.values()))
) == {"B", "C", "E"}  # several valid middle activities
Test Why
Standard sample case Verifies normal functionality
All equal counts Ensures empty result when min equals max
Multiple maximum activities Confirms all maximum-count activities are excluded
Multiple minimum activities Confirms all minimum-count activities are excluded
Only two activities Ensures no middle activity exists
Larger mixed dataset Validates filtering with several intermediate counts

Edge Cases

One important edge case occurs when all activities have exactly the same number of participants. In this scenario, the minimum and maximum counts are identical. Since every activity matches both values simultaneously, all activities must be excluded. A careless implementation might incorrectly return every activity if it only checks one condition.

Another important case is when multiple activities share the maximum or minimum count. For example, two activities may both have five participants, while two others both have one participant. The solution must exclude all activities tied at the extremes, not just one of them. Using NOT IN against the computed maximum and minimum values naturally handles this situation.

A third edge case occurs when there are only two distinct participation counts. For example, activities may have counts {1, 1, 5, 5}. In this case, every activity is either minimum or maximum, so the result is empty. The filtering condition correctly removes all rows.

A final subtle case is ensuring that every activity exists in the Friends table. The problem guarantees this property, so we do not need outer joins or null handling. Without this guarantee, activities with zero participants would require special handling.