LeetCode 183 - Customers Who Never Order

LeetCode Problem 183

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem is asking us to identify all customers from a Customers table who have never placed an order according to the Orders table. In other words, we are looking for entries in Customers that do not have a corresponding customerId in the Orders table.

The input consists of two tables: Customers and Orders. Customers has an id (primary key) and name (the customer name), while Orders has an id (primary key) and customerId (foreign key referencing Customers.id). The expected output is a single-column table named Customers listing all customer names that do not appear in any order record.

Constraints implied by the problem include that both tables are non-empty, IDs are unique, and customerId in Orders always points to a valid customer. The problem allows the output to be returned in any order.

Important edge cases include situations where no customers have orders, where all customers have orders, or where the Orders table is empty. The solution should correctly handle these cases without generating duplicates or missing any customer.

Approaches

The brute-force approach would iterate over every customer and, for each customer, scan the entire Orders table to check whether there is a matching customerId. This approach is correct because it directly verifies for each customer whether an order exists. However, this approach is inefficient, with a time complexity of O(C * O), where C is the number of customers and O is the number of orders, because each customer requires scanning all orders.

The optimal approach leverages SQL set operations or joins. The key insight is that we only need customers that do not appear in the Orders table. This can be done using a LEFT JOIN between Customers and Orders, selecting rows where the Orders.customerId is NULL, or using a NOT IN or NOT EXISTS subquery. These approaches reduce the number of comparisons needed by using indexed lookups instead of scanning the entire table repeatedly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C * O)	O(1)	Check each customer against all orders
Optimal	O(C + O)	O(O)	Use LEFT JOIN or NOT IN/NOT EXISTS subquery for efficient lookup

Algorithm Walkthrough

1. Start with the Customers table as the primary table because we need to list all customers, including those with no orders.
2. Perform a LEFT JOIN between Customers and Orders on the customer ID. This will attach order information to each customer if it exists, and NULL if it does not.
3. Filter the result set to only include rows where the Orders.customerId is NULL, indicating the customer never placed an order.
4. Select only the name column from these filtered rows and return it as the final result.

Why it works: By using a LEFT JOIN, we preserve all customer records and only nullify unmatched order records. Filtering for NULLs guarantees that we only pick customers without orders. The query leverages relational database indexing for efficiency.

Python Solution

import sqlite3
from typing import List, Tuple

def customers_who_never_order(cursor: sqlite3.Cursor) -> List[Tuple[str]]:
    query = """
    SELECT name AS Customers
    FROM Customers c
    LEFT JOIN Orders o ON c.id = o.customerId
    WHERE o.customerId IS NULL
    """
    cursor.execute(query)
    return cursor.fetchall()

The implementation uses a LEFT JOIN to attach order data to each customer. The WHERE clause filters out all customers who have orders by checking for NULL values in Orders.customerId. Finally, fetchall returns the names of customers who never placed an order.

Go Solution

package main

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

func CustomersWhoNeverOrder(db *sql.DB) ([]string, error) {
    query := `
    SELECT name AS Customers
    FROM Customers c
    LEFT JOIN Orders o ON c.id = o.customerId
    WHERE o.customerId IS NULL
    `
    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
}

The Go implementation is similar, using db.Query to execute the LEFT JOIN SQL query. Rows are iterated over with rows.Next() and scanned into a slice of strings. We handle errors carefully and defer closing of rows. Unlike Python, Go requires explicit iteration and slice handling.

Worked Examples

For the input:

Customers table:

id	name
1	Joe
2	Henry
3	Sam
4	Max

Orders table:

id	customerId
1	3
2	1

Step-by-step execution:

1. Perform LEFT JOIN:

+----+-------+------------+
| id | name  | customerId |
+----+-------+------------+
| 1  | Joe   | 1          |
| 2  | Henry | NULL       |
| 3  | Sam   | 3          |
| 4  | Max   | NULL       |

2. Filter WHERE customerId IS NULL:

+----+-------+
| id | name  |
+----+-------+
| 2  | Henry |
| 4  | Max   |

3. Return only name:

+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |

Complexity Analysis

Measure	Complexity	Explanation
Time	O(C + O)	Scanning both tables once with indexed lookups; LEFT JOIN is efficient with indexes
Space	O(O)	Temporary space to store joined order information, or result set of unmatched customers

The complexity arises because the database engine optimizes joins using indexes. The result set size is proportional to the number of customers without orders.

Test Cases

# Provided example
assert customers_who_never_order(cursor) == [('Henry',), ('Max',)]  # basic functionality

# All customers have orders
assert customers_who_never_order(cursor_all_orders) == []  # no unmatched customers

# No orders exist
assert customers_who_never_order(cursor_no_orders) == [('Joe',), ('Henry',), ('Sam',), ('Max',)]  # all customers returned

# Single customer, no orders
assert customers_who_never_order(cursor_single_customer) == [('Alice',)]

# Single customer, with order
assert customers_who_never_order(cursor_single_order) == []

Test	Why
Provided example	Validates normal case with partial orders
All customers have orders	Ensures no false positives are returned
No orders exist	Ensures all customers are returned when Orders is empty
Single customer, no orders	Tests minimal table edge case
Single customer, with order	Tests minimal table edge case with an order

Edge Cases

Empty Orders Table: If the Orders table has no entries, every customer has never placed an order. The implementation correctly returns all customers because the LEFT JOIN produces NULL for all Orders.customerId.

All Customers Have Orders: If every customer has at least one order, the LEFT JOIN will attach a non-null customerId for every row. Filtering for NULL correctly produces an empty result, ensuring no false positives.

Single Customer: With only one customer, the solution must correctly return either that customer or an empty set depending on whether an order exists. This tests that the algorithm does not rely on multiple rows and correctly handles minimal input sizes.

This approach ensures correctness, handles edge cases gracefully, and scales efficiently with indexed tables.