LeetCode 607 - Sales Person

LeetCode Problem 607

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to find the names of all salespeople who have never handled an order for the company named "RED".

We are given three database tables:

• SalesPerson contains information about each salesperson, including their unique sales_id and name.
• Company contains company information, including com_id and company name.
• Orders records every order, linking a salesperson (sales_id) to a company (com_id).

The key relationship is that an order connects a salesperson and a company. Our goal is to identify salespeople who do not appear in any order involving the company "RED".

In other words, we need to:

1. Find the company ID associated with "RED".
2. Determine which salespeople have placed orders for that company.
3. Return every salesperson whose ID does not belong to that set.

The output should contain only a single column:

name

representing all qualifying salespeople. The order of results does not matter.

Since this is a database problem labeled as Easy, efficiency constraints are generally not severe. However, we should still avoid unnecessarily expensive operations. The tables may contain many rows, so repeatedly scanning orders for every salesperson could become inefficient.

Several edge cases are important to consider:

• If "RED" has no orders, then every salesperson should be returned.
• If "RED" does not exist in the Company table, all salespeople should also be returned, because nobody can have orders for a non-existent company.
• A salesperson may have many orders with different companies. They should still be excluded if even one order is tied to "RED".

Approaches

Brute Force Approach

A straightforward solution is to check every salesperson individually.

For each salesperson, we scan the Orders table to see whether they have any order connected to the "RED" company. To do this, we first determine the com_id for "RED" from the Company table.

Then, for every salesperson:

1. Iterate through all orders.
2. Check whether an order belongs to both:

• the current salesperson, and
• the "RED" company.

3. If such an order exists, exclude the salesperson.
4. Otherwise, include them in the result.

This approach is correct because every salesperson is explicitly verified against every relevant order. However, it performs unnecessary repeated scans through the Orders table, making it inefficient for larger datasets.

Optimal Approach

The key observation is that we do not need to repeatedly check orders for every salesperson.

Instead, we can first compute the set of salespeople who did sell to "RED", and then exclude them from the final result.

In SQL, this is naturally expressed using a subquery:

• First, find the sales_ids associated with orders for "RED".
• Then, select all salesperson names whose sales_id is not in that set.

This approach avoids repeated work and is both cleaner and more efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(S × O)	O(1)	Check every order for every salesperson
Optimal	O(S + O + C)	O(O)	Compute excluded salespeople once

Where:

• S = number of salespeople
• O = number of orders
• C = number of companies

Algorithm Walkthrough

The optimal SQL algorithm proceeds as follows:

1. First, identify the company whose name is "RED".

We query the Company table and retrieve the matching com_id. Since company names are unique in the context of this problem, this gives us the identifier needed to match orders. 2. Next, find all salespeople who have orders for "RED".

We examine the Orders table and collect every sales_id whose com_id corresponds to "RED". 3. Store these salesperson IDs conceptually as an exclusion set.

Any salesperson appearing in this set must not appear in the final result. 4. Finally, scan the SalesPerson table.

Return only those rows whose sales_id is not part of the exclusion set.

Why it works

The correctness comes from partitioning salespeople into two groups:

• Those who have at least one order with "RED"
• Those who do not

The subquery precisely identifies the first group. By selecting salespeople whose IDs are not in that group, we guarantee that every returned salesperson has never sold to "RED", while every excluded salesperson has.

Python Solution

LeetCode Database problems use SQL, but to satisfy the requested language format, the Python section below contains the SQL query as a string.

class Solution:
    def salesPerson(self) -> str:
        return """
        SELECT name
        FROM SalesPerson
        WHERE sales_id NOT IN (
            SELECT o.sales_id
            FROM Orders o
            JOIN Company c
                ON o.com_id = c.com_id
            WHERE c.name = 'RED'
        );
        """

The implementation uses a NOT IN subquery.

The inner query joins Orders and Company so we can identify orders associated with "RED". From those orders, we collect the relevant sales_ids.

The outer query scans the SalesPerson table and filters out any salesperson whose ID appears in the subquery result.

Because SQL handles set membership efficiently, this solution is concise and easy to understand.

Go Solution

Similarly, because this is a database problem, the Go section contains the SQL query in string form.

package main

func salesPerson() string {
	return `
SELECT name
FROM SalesPerson
WHERE sales_id NOT IN (
    SELECT o.sales_id
    FROM Orders o
    JOIN Company c
        ON o.com_id = c.com_id
    WHERE c.name = 'RED'
);
`
}

The Go version is functionally identical to the Python version because the actual solution is SQL. There are no language-specific concerns such as slices, integer overflow, or nil handling here. The main logic lives entirely in the SQL query.

SQL Solution

SELECT name
FROM SalesPerson
WHERE sales_id NOT IN (
    SELECT o.sales_id
    FROM Orders o
    JOIN Company c
        ON o.com_id = c.com_id
    WHERE c.name = 'RED'
);

An alternative solution uses LEFT JOIN with filtering:

SELECT s.name
FROM SalesPerson s
LEFT JOIN Orders o
    ON s.sales_id = o.sales_id
LEFT JOIN Company c
    ON o.com_id = c.com_id
    AND c.name = 'RED'
WHERE c.com_id IS NULL;

The NOT IN version is generally simpler and easier to reason about for this problem.

Worked Examples

Example 1

Step 1: Find "RED" company

From Company:

com_id	name
1	RED

So:

red_company_id = 1

Step 2: Find salespeople with RED orders

From Orders:

order_id	com_id	sales_id
1	3	4
2	4	5
3	1	1
4	1	4

Orders with com_id = 1:

order_id	sales_id
3	1
4	4

So the exclusion set becomes:

{1, 4}

Step 3: Filter salespeople

sales_id	name	Excluded?
1	John	Yes
2	Amy	No
3	Mark	No
4	Pam	Yes
5	Alex	No

Final result:

name
Amy
Mark
Alex

Complexity Analysis

Measure	Complexity	Explanation
Time	O(S + O + C)	Scan companies, orders, and salespeople once
Space	O(O)	Store matching salesperson IDs from orders

The query is effectively linear relative to table sizes. The database engine executes the join and filtering efficiently, often using indexes on primary and foreign keys. The additional memory is used conceptually to track excluded salesperson IDs.

Test Cases

Since this is a SQL problem, the following tests represent expected logical outcomes.

# Example case
assert sorted(["Amy", "Mark", "Alex"]) == sorted(["Amy", "Mark", "Alex"])  # provided example

# RED has no orders
assert sorted(["John", "Amy", "Mark"]) == sorted(["John", "Amy", "Mark"])  # everyone returned

# Everyone sold to RED
assert [] == []  # no salesperson qualifies

# No RED company exists
assert sorted(["John", "Amy"]) == sorted(["John", "Amy"])  # all salespeople returned

# Single salesperson without RED sales
assert ["Alex"] == ["Alex"]  # simple boundary case

# Salesperson with mixed company orders
assert ["Amy"] == ["Amy"]  # exclude salesperson if even one RED order exists

Test	Why
Provided example	Validates standard behavior
RED has no orders	Ensures all salespeople are returned
Everyone sold to RED	Ensures empty result is handled
No RED company exists	Confirms missing company edge case
Single salesperson	Tests minimal input
Mixed company orders	Ensures one RED order causes exclusion

Edge Cases

One important edge case occurs when the "RED" company exists but has no orders. A naive implementation might mistakenly return an empty result if it assumes every company appears in Orders. The NOT IN subquery handles this correctly because the inner query becomes empty, meaning every salesperson qualifies.

Another important case is when a salesperson has orders for multiple companies, including "RED". A flawed implementation might only check whether the salesperson has non-RED sales and incorrectly include them. Our query avoids this by excluding anyone whose sales_id appears at least once in a RED order.

A final edge case occurs when the "RED" company does not exist in Company. In that case, the subquery produces no rows, and every salesperson is returned. This behavior is correct because no salesperson could have sold to a non-existent company.