Problem

Table: Events

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| business_id   | int     |
| event_type    | varchar |
| occurrences   | int     | 
+---------------+---------+

(business_id, event_type) is the primary key (combination of columns with unique values) of this table.
Each row in the table logs the info that an event of some type occurred at some business for a number of times.

The average activity for a particular event_type is the average occurrences across all companies that have this event.

An active business is a business that has more than one event_type such that their occurrences is strictly greater than the average activity for that event.

Write a solution to find all active businesses.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Events table:
+-------------+------------+-------------+
| business_id | event_type | occurrences |
+-------------+------------+-------------+
| 1           | reviews    | 7           |
| 3           | reviews    | 3           |
| 1           | ads        | 11          |
| 2           | ads        | 7           |
| 3           | ads        | 6           |
| 1           | page views | 3           |
| 2           | page views | 12          |
+-------------+------------+-------------+
Output: 
+-------------+
| business_id |
+-------------+
| 1           |
+-------------+
Explanation:  
The average activity for each event can be calculated as follows:
- 'reviews': (7+3)/2 = 5
- 'ads': (11+7+6)/3 = 8
- 'page views': (3+12)/2 = 7.5
The business with id=1 has 7 'reviews' events (more than 5) and 11 'ads' events (more than 8), so it is an active business.

Solution

Method 1 – Using Aggregation and Self Join

Intuition

The key idea is to first compute the average occurrences for each event type, then compare each business’s occurrences for each event type to this average. A business is “active” if it exceeds the average for more than one event type.

Approach

  1. Calculate the average occurrences for each event_type using a subquery or CTE.
  2. Join this average back to the original Events table to compare each business’s occurrences to the average for that event type.
  3. For each business, count how many event types have occurrences strictly greater than the average.
  4. Select businesses where this count is greater than one.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

WITH AvgEvents AS (
  SELECT event_type, AVG(occurrences) AS avg_occurrences
  FROM Events
  GROUP BY event_type
),
AboveAvg AS (
  SELECT e.business_id, e.event_type
  FROM Events e
  JOIN AvgEvents a
    ON e.event_type = a.event_type
  WHERE e.occurrences > a.avg_occurrences
)
SELECT business_id
FROM AboveAvg
GROUP BY business_id
HAVING COUNT(DISTINCT event_type) > 1;

Complexity

  • ⏰ Time complexity: O(n) — Each row is processed a constant number of times for aggregation and join.
  • 🧺 Space complexity: O(m) — Where m is the number of unique event types, for storing averages.