Skip to main content
Talentd

Find Customer Referee - Solution & Explanation

EasyDatabase6 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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.

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.

Code

SQL

SQL

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.

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.

Code

SQL

SQL

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 →

Approach 3: Filtering Customers by Referee ID

This approach involves filtering the list of customers based on the referee_id. The goal is to select customers whose referee_id is either NULL or not equal to 2. This solution exploits the fact that SQL can be used to construct a SELECT statement with a conditional WHERE clause to filter out the desired rows.

This SQL query selects the name of customers where the referee_id is either NULL or not equal to 2. The 'IS NULL' condition ensures that customers without any referrer are included. The '!= 2' condition ensures that customers referred by customer 2 are excluded.

Code

SQL

SQL

Complexity

Time Complexity: O(n), where 'n' is the total number of rows in the table, because we need to scan each row.
Space Complexity: O(n), where 'n' is the maximum possible number of results stored in the output.

Try this approach in the editor →

Approach 4: Subquery to Exclude Referrals

This approach uses a subquery to identify and exclude customers who were referred by the customer with id = 2. By constructing a subquery, the main query is able to filter the rest of the customers from the full list who do not appear in the subquery's result set.

The main query selects all name entries from the Customer table where the id is not in the list returned by the subquery. The subquery retrieves the id of customers with a referee_id of 2, effectively excluding these entries from the result set.

Code

SQL

SQL

Complexity

Time Complexity: O(n^2), since each candidate row is compared against the subquery results.
Space Complexity: O(1) if the subquery results can be stored efficiently in temporary space with respect to the total number of customers.

Try this approach in the editor →

Approach 5: Conditional Filtering

We can directly filter out the customer names whose referee_id is not 2. Note that the customers whose referee_id is NULL should also be filtered out.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.

Filtering Customers by Referee ID

Time Complexity: O(n), where 'n' is the total number of rows in the table, because we need to scan each row.
Space Complexity: O(n), where 'n' is the maximum possible number of results stored in the output.

Subquery to Exclude Referrals

Time Complexity: O(n^2), since each candidate row is compared against the subquery results.
Space Complexity: O(1) if the subquery results can be stored efficiently in temporary space with respect to the total number of customers.

Conditional Filtering—

Detailed Complexity Analysis

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

Video Solution

Find Customer Referee | Leetcode 584 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 16,255 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find Customer Referee with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary