LeetCode 584 - Find Customer Referee

LeetCode Problem 584

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem provides a Customer table with three columns: id, name, and referee_id. Each row represents a customer, their unique identifier (id), their name, and optionally the id of the customer who referred them. A null value in referee_id indicates that the customer was not referred by anyone.

The task is to identify all customers who satisfy one of two conditions: either they were referred by a customer whose id is not 2, or they were not referred by anyone at all (referee_id is null). The result should be returned as a table with a single column, name, and the order does not matter.

Important constraints include that id is unique for each customer, and there are no guarantees on the total number of customers, but given the "Easy" difficulty, we can assume O(n) solutions are acceptable. Key edge cases involve customers who were referred by id = 2 (which should be excluded), customers with referee_id as null, and the possibility of the table being empty.

Approaches

A brute-force approach would be to iterate over all rows of the Customer table, check for each customer whether their referee_id is null or not equal to 2, and then manually collect their names. This approach works because it explicitly evaluates the problem conditions for each customer. However, in SQL, writing this with multiple joins or subqueries could become verbose and less efficient if the table size grows.

The optimal approach leverages a single SQL query with a WHERE condition that directly filters customers based on the two criteria: referee_id != 2 or referee_id IS NULL. This eliminates unnecessary complexity and efficiently retrieves the desired results with minimal computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Iterate over all customers and apply condition checks row by row
Optimal	O(n)	O(n)	Single SQL query with a WHERE clause filtering by referee_id != 2 or referee_id IS NULL

Algorithm Walkthrough

1. Begin by examining the Customer table row by row.
2. For each customer, check if the referee_id is either null (not referred) or a number different from 2 (referred by someone other than customer 2).
3. If a customer meets either condition, select their name and include it in the result set.
4. Continue this process until all rows have been evaluated.
5. Return the resulting list of names as a table. Since order does not matter, no sorting is necessary.

Why it works: By directly applying the two conditions in a WHERE clause, we guarantee that only customers who are either not referred or referred by someone other than id = 2 are selected. This preserves the logical constraints of the problem and ensures correctness.

Python Solution

# SQL problem; Python simulation using SQLite for demonstration
import sqlite3
from typing import List

def find_customers_referee(cursor: sqlite3.Cursor) -> List[str]:
    query = """
    SELECT name
    FROM Customer
    WHERE referee_id IS NULL OR referee_id != 2
    """
    cursor.execute(query)
    results = cursor.fetchall()
    return [row[0] for row in results]

In this Python solution, we connect to a SQLite database and execute a single query. The query directly expresses the two conditions from the problem: referee_id IS NULL captures customers not referred by anyone, and referee_id != 2 captures customers referred by anyone except customer 2. The fetchall() function retrieves all matching rows, and a list comprehension extracts the name column for the final output.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

func findCustomersReferee(db *sql.DB) ([]string, error) {
    query := `
    SELECT name
    FROM Customer
    WHERE referee_id IS NULL OR referee_id != 2
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var result []string
    for rows.Next() {
        var name string
        if err := rows.Scan(&name); err != nil {
            return nil, err
        }
        result = append(result, name)
    }
    return result, nil
}

In Go, we query the database using db.Query, iterate over the resulting rows, and append each valid name to a slice. Go requires explicit handling of nil and error propagation, which is why we check for errors at each step and defer the closing of rows to ensure resources are cleaned up.

Worked Examples

Consider the example input table:

id	name	referee_id
1	Will	null
2	Jane	null
3	Alex	2
4	Bill	null
5	Zack	1
6	Mark	2

Step by step:

1. Customer 1, referee_id = null, included (Will).
2. Customer 2, referee_id = null, included (Jane).
3. Customer 3, referee_id = 2, excluded (Alex).
4. Customer 4, referee_id = null, included (Bill).
5. Customer 5, referee_id = 1, included (Zack).
6. Customer 6, referee_id = 2, excluded (Mark).

Resulting names: Will, Jane, Bill, Zack.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each row is scanned once by the SQL engine to evaluate the WHERE clause.
Space	O(n)	Space is used to store the result set containing up to all names.

The reasoning is straightforward: the query needs to examine each row of the table, and the output size is proportional to the number of qualifying customers.

Test Cases

# test cases using SQLite
import sqlite3

conn = sqlite3.connect(':memory:')
c = conn.cursor()
c.execute("CREATE TABLE Customer (id INT, name TEXT, referee_id INT)")

# Example test case
c.executemany("INSERT INTO Customer VALUES (?, ?, ?)", [
    (1, 'Will', None),
    (2, 'Jane', None),
    (3, 'Alex', 2),
    (4, 'Bill', None),
    (5, 'Zack', 1),
    (6, 'Mark', 2)
])
assert sorted(find_customers_referee(c)) == sorted(['Will', 'Jane', 'Bill', 'Zack'])

# Test: all referred by 2
c.execute("DELETE FROM Customer")
c.executemany("INSERT INTO Customer VALUES (?, ?, ?)", [
    (1, 'Alice', 2),
    (2, 'Bob', 2)
])
assert find_customers_referee(c) == []

# Test: no customers
c.execute("DELETE FROM Customer")
assert find_customers_referee(c) == []

# Test: no referrals at all
c.execute("DELETE FROM Customer")
c.executemany("INSERT INTO Customer VALUES (?, ?, ?)", [
    (1, 'Tom', None),
    (2, 'Jerry', None)
])
assert sorted(find_customers_referee(c)) == ['Tom', 'Jerry']

# Test: mix referrals including non-2
c.execute("DELETE FROM Customer")
c.executemany("INSERT INTO Customer VALUES (?, ?, ?)", [
    (1, 'A', 3),
    (2, 'B', 2),
    (3, 'C', None)
])
assert sorted(find_customers_referee(c)) == sorted(['A', 'B', 'C'])

Test	Why
Example input	Validates basic functionality
All referred by 2	Ensures correct exclusion of referee_id = 2
Empty table	Handles edge case of no customers
No referrals	Ensures customers with null referee_id are included
Mixed referrals	Tests combination of null, 2, and other referee_ids

Edge Cases

One important edge case is when all customers are referred by id = 2. In this case, the result should be empty. This is handled correctly because the WHERE clause explicitly excludes referee_id = 2.

Another edge case is when all customers have null as referee_id. The algorithm correctly includes them because referee_id IS NULL evaluates to true for every row.

A third edge case is a table with a single customer, either referred by 2, referred by another customer, or not referred. Each scenario is correctly handled by the same condition logic, and no additional checks are necessary. This ensures that minimal or extreme inputs do not break the query.