584. Find Customer Referee - SQL Solution

The problem

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 |
+------+

Approach overview

Problem Overview: The table Customer stores each customer's name and the referee_id that referred them. The task is to return the names of customers whose referee is not customer 2. Customers with NULL referee IDs should also be included since they were not referred by anyone.

Approach 1: SQL WHERE Clause (O(n) time, O(1) space)

The most direct solution filters rows using a WHERE condition. Iterate through each row of the table and return customers where referee_id != 2 or the value is NULL. SQL comparisons with NULL return unknown, so an explicit IS NULL check is required. This approach scans the table once and applies a simple conditional filter, which most SQL engines execute efficiently with a sequential scan or index if available. For database-focused interview questions, this is the expected solution because it is simple and readable.

Approach 2: SQL NOT IN Clause (O(n) time, O(1) space)

Another option uses a NOT IN filter to exclude the specific referee value. The query returns rows where referee_id NOT IN (2) or where the value is NULL. This expresses the exclusion logic more declaratively and is useful when filtering multiple values. Internally, the database still performs a scan and comparison for each row. The complexity remains linear relative to the number of records.

Approach 3: Filtering Customers by Referee ID (O(n) time, O(1) space)

This version explicitly checks both conditions: customers whose referee_id is not equal to 2 and customers who have no referee. The query logic typically looks like referee_id IS NULL OR referee_id != 2. The key insight is understanding SQL’s three‑valued logic—NULL cannot be compared with standard equality operators. Explicitly including the IS NULL condition guarantees correct results.

Approach 4: Subquery to Exclude Referrals (O(n) time, O(1) space)

A slightly more verbose approach uses a subquery to filter out customers referred by ID 2. The outer query selects names while the subquery identifies rows that should be excluded. Although logically correct, the subquery does not provide performance benefits for this problem and can reduce readability. Subqueries become more useful in complex SQL scenarios involving joins or aggregated filters.

Recommended for interviews: The simple WHERE referee_id != 2 OR referee_id IS NULL solution is what interviewers expect. It demonstrates understanding of SQL filtering and correct handling of NULL values in relational database queries. Knowing the alternative NOT IN or subquery approach helps when the exclusion list becomes dynamic or derived from another table.

Approach 1: Approach 1: SQL WHERE Clause

This approach involves using a simple SQL query with a WHERE clause to filter out customers who are referred by the customer with id = 2. We need to select all entries where referee_id is not equal to 2, including those where referee_id is NULL.

MySQL

SELECT name FROM Customer WHERE referee_id IS NULL OR referee_id != 2;

The SQL query selects the 'name' from the 'Customer' table where the 'referee_id' is either NULL or not equal to 2. By using 'referee_id IS NULL' in the WHERE clause, we also include customers who were not referred by anyone.

Complexity

Time Complexity: O(n), where n is the number of rows in the Customer table.
Space Complexity: O(1), since the query operates in-place within the database.

Try this approach in the editor

Approach 2: Approach 2: SQL NOT IN Clause

This method utilizes the NOT IN clause to exclude specific entries from the result. By listing all customer ids that have referee_id of 2 and filtering them out, we can achieve the desired result.

MySQL

SELECT name FROM Customer WHERE id NOT IN (SELECT id FROM Customer WHERE referee_id = 2);

This SQL query achieves the same goal through the use of a subquery. The subquery selects all customer ids with a 'referee_id' of 2. The outer query then selects the names of customers whose ids are not in that subquery result.

Complexity

Time Complexity: O(n), where n is the number of rows in the Customer table.
Space Complexity: O(1), as the query executes using the database's inbuilt mechanisms.

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: SQL WHERE Clause	Time Complexity: O(n), where n is the number of rows in the Customer table. Space Complexity: O(1), since the query operates in-place within the database.
Approach 2: SQL NOT IN Clause	Time Complexity: O(n), where n is the number of rows in the Customer table. Space Complexity: O(1), as the query executes using the database's inbuilt mechanisms.

Complexity analysis

Approach	Time	Space	When to Use
SQL WHERE Clause	O(n)	O(1)	Best general solution. Simple filtering with explicit NULL handling.
SQL NOT IN Clause	O(n)	O(1)	Useful when excluding multiple referee IDs.
Filtering by Referee ID Condition	O(n)	O(1)	Clear logic when explicitly handling NULL and inequality checks.
Subquery Exclusion	O(n)	O(1)	Helpful when the excluded referees come from another query or table.

Frequently asked questions

Is Find Customer Referee easy or hard?

Find Customer Referee is classified as an Easy problem on LeetCode with an acceptance rate above 70%. The challenge mainly tests basic SQL filtering and understanding how NULL comparisons work.

Find Customer Referee Python/Java solution

Unlike algorithm problems, this task is solved using SQL rather than Python or Java. The core query selects customer names from the table and filters rows using a WHERE condition that excludes referee_id = 2 while keeping NULL values.

How to solve Find Customer Referee in O(n)?

Use a WHERE condition that filters rows based on the referee_id column. The typical query is: SELECT name FROM Customer WHERE referee_id != 2 OR referee_id IS NULL. The database performs a single pass over the table and outputs only the qualifying rows.

What is the best approach for Find Customer Referee?

The simplest and most common solution uses a SQL WHERE filter: referee_id != 2 OR referee_id IS NULL. It scans the table once and directly removes customers referred by ID 2 while keeping those without a referee. This approach runs in O(n) time and requires no additional space.

Is Find Customer Referee asked at Google/Amazon/Meta?

This problem represents the type of SQL filtering question commonly used in interviews at data-driven companies. Variations of similar database queries appear in interviews at companies like Amazon and other organizations that evaluate SQL fundamentals.

What data structure is used in Find Customer Referee?

The problem operates on a relational database table rather than traditional data structures. The key concept is SQL filtering using conditions on table columns, along with correct handling of NULL values.

What is the time complexity of Find Customer Referee?

Most SQL solutions run in O(n) time because the database scans the Customer table and evaluates the filter condition for each row. Space complexity is O(1) since the query only returns filtered results without storing additional structures.

Find Customer Referee solution and explanation

The problem

Approach overview

Approach 1: Approach 1: SQL WHERE Clause

Approach 2: Approach 2: SQL NOT IN Clause

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Customer Referee solution and explanation

The problem

Approach overview

Approach 1: Approach 1: SQL WHERE Clause

Approach 2: Approach 2: SQL NOT IN Clause

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems