{x}
blog image

Find Customer Referee

Table: Customer

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| name        | varchar |
| referee_id  | int     |
+-------------+---------+
In SQL, id is the primary key column for this table.
Each row of this table indicates the id of a customer, their name, and the id of the customer who referred them.

 

Find the names of the customer that are not referred by the customer with id = 2.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Customer table:
+----+------+------------+
| id | name | referee_id |
+----+------+------------+
| 1  | Will | null       |
| 2  | Jane | null       |
| 3  | Alex | 2          |
| 4  | Bill | null       |
| 5  | Zack | 1          |
| 6  | Mark | 2          |
+----+------+------------+
Output: 
+------+
| name |
+------+
| Will |
| Jane |
| Bill |
| Zack |
+------+

Solution Explanation for LeetCode Problem 584: Find Customer Referee

This problem requires finding the names of customers who were not referred by the customer with id = 2. The solution uses SQL queries to filter the Customer table.

Approach: Conditional Filtering with IFNULL

The most efficient approach involves directly filtering the Customer table based on the referee_id column. The key is handling NULL values appropriately, as customers without a referrer will also satisfy the condition.

The IFNULL function is used to handle the cases where referee_id is NULL. IFNULL(referee_id, 0) replaces NULL values with 0. This allows us to compare the referee_id (or its replacement) with 2 directly in the WHERE clause. Customers with referee_id not equal to 2 (including those with NULL referee_id which become 0 after IFNULL) are selected.

SQL Query (MySQL)

SELECT name
FROM Customer
WHERE IFNULL(referee_id, 0) != 2;

This query selects the name column from the Customer table where the referee_id is either not equal to 2 or is NULL (which is treated as 0 after the IFNULL function).

Time Complexity Analysis

The time complexity of this SQL query is determined by the database's query planner and the size of the Customer table. In the worst case, it would involve scanning the entire table, resulting in a time complexity of O(N), where N is the number of rows in the Customer table. However, with proper indexing on the referee_id column, the query could achieve significantly better performance closer to O(log N) or even O(1) depending on the database system's optimization strategies. Database indexes dramatically speed up lookups.

Space Complexity Analysis

The space complexity is O(M), where M is the number of customers who were not referred by customer with id = 2. This space is used to store the result set. In the worst case, M could be equal to N (the total number of customers). However, typically, this would be a much smaller subset of the entire table.