# LeetCode 183: Customers Who Never Order

## Problem Restatement

We are given two tables: `Customers` and `Orders`.

`Customers` stores customer information.

| Column | Type |
|---|---|
| id | int |
| name | varchar |

`Orders` stores order information.

| Column | Type |
|---|---|
| id | int |
| customerId | int |

The `customerId` column in `Orders` refers to `Customers.id`.

We need to find all customers who never placed an order. The result can be returned in any order. The official problem asks for all customers who never order anything.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Tables `Customers(id, name)` and `Orders(id, customerId)` |
| Output | One column named `Customers` |
| Rule | Return customers whose `id` does not appear in `Orders.customerId` |
| Order | Any order is accepted |

Expected output column:

```sql
Customers
```

## Examples

Input:

```text
Customers
+----+-------+
| id | name  |
+----+-------+
| 1  | Joe   |
| 2  | Henry |
| 3  | Sam   |
| 4  | Max   |
+----+-------+

Orders
+----+------------+
| id | customerId |
+----+------------+
| 1  | 3          |
| 2  | 1          |
+----+------------+
```

Customer `Joe` has an order because `Orders.customerId = 1`.

Customer `Sam` has an order because `Orders.customerId = 3`.

Customer `Henry` has no order.

Customer `Max` has no order.

Output:

```text
+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+
```

## First Thought: Find Customer IDs Missing From Orders

The task is to find customer rows with no matching order row.

The relationship is:

```sql
Customers.id = Orders.customerId
```

So for each customer, we need to ask:

```text
Does this customer's id appear in Orders.customerId?
```

If the answer is no, that customer should be returned.

## Key Insight

This is an anti-join problem.

An anti-join means we keep rows from one table when no matching row exists in another table.

There are two common SQL ways to express this:

| Method | Idea |
|---|---|
| `LEFT JOIN ... IS NULL` | Join orders if they exist, then keep unmatched customers |
| `NOT EXISTS` | Keep customers where no related order row exists |

For this problem, `LEFT JOIN` is direct and easy to read.

## Algorithm

1. Start from `Customers`.
2. `LEFT JOIN` to `Orders` using `Customers.id = Orders.customerId`.
3. Customers with orders will have matching `Orders` rows.
4. Customers without orders will have `NULL` in the joined `Orders` columns.
5. Keep rows where `Orders.id IS NULL`.
6. Return the customer name as `Customers`.

## Correctness

A `LEFT JOIN` keeps every row from `Customers`.

If a customer has at least one order, the join finds a matching row in `Orders`, so `Orders.id` will not be `NULL`.

If a customer has no order, the join cannot find a matching `Orders` row. SQL fills the joined `Orders` columns with `NULL`.

The condition:

```sql
WHERE o.id IS NULL
```

keeps exactly the customers without matching orders.

Therefore, every returned customer never ordered anything, and every customer who never ordered anything is returned.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(c + o)` expected | The database scans customers and checks matching orders |
| Space | `O(k)` | The result stores customers without orders |

Here, `c` is the number of customers, `o` is the number of orders, and `k` is the number of returned customers.

With an index on `Orders.customerId`, the join can be executed efficiently.

## Implementation

```sql
SELECT
    c.name AS Customers
FROM Customers c
LEFT JOIN Orders o
    ON c.id = o.customerId
WHERE o.id IS NULL;
```

## Code Explanation

This starts from all customers:

```sql
FROM Customers c
```

Then it tries to attach each customer's orders:

```sql
LEFT JOIN Orders o
    ON c.id = o.customerId
```

Because this is a `LEFT JOIN`, customers remain in the result even when no order matches.

This filter keeps only unmatched customers:

```sql
WHERE o.id IS NULL
```

Finally, this returns the required output column:

```sql
SELECT
    c.name AS Customers
```

## Alternative Implementation

We can also use `NOT EXISTS`.

```sql
SELECT
    c.name AS Customers
FROM Customers c
WHERE NOT EXISTS (
    SELECT 1
    FROM Orders o
    WHERE o.customerId = c.id
);
```

This reads almost exactly like the problem: return customers for whom no order exists.

This version also avoids edge cases that can happen with `NOT IN` when the subquery contains `NULL`.

## Testing

Test case 1:

```sql
CREATE TABLE Customers (
    id INT PRIMARY KEY,
    name VARCHAR(255)
);

CREATE TABLE Orders (
    id INT PRIMARY KEY,
    customerId INT
);

INSERT INTO Customers (id, name) VALUES
(1, 'Joe'),
(2, 'Henry'),
(3, 'Sam'),
(4, 'Max');

INSERT INTO Orders (id, customerId) VALUES
(1, 3),
(2, 1);

SELECT
    c.name AS Customers
FROM Customers c
LEFT JOIN Orders o
    ON c.id = o.customerId
WHERE o.id IS NULL;
```

Expected:

```text
+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+
```

Test case 2:

```sql
DELETE FROM Orders;
DELETE FROM Customers;

INSERT INTO Customers (id, name) VALUES
(1, 'Alice'),
(2, 'Bob');

INSERT INTO Orders (id, customerId) VALUES
(1, 1),
(2, 2);
```

Expected:

```text
+-----------+
| Customers |
+-----------+
```

Every customer has an order.

Test case 3:

```sql
DELETE FROM Orders;
DELETE FROM Customers;

INSERT INTO Customers (id, name) VALUES
(1, 'Alice'),
(2, 'Bob');
```

Expected:

```text
+-----------+
| Customers |
+-----------+
| Alice     |
| Bob       |
+-----------+
```

No customer has an order.

Test case 4:

```sql
DELETE FROM Orders;
DELETE FROM Customers;

INSERT INTO Customers (id, name) VALUES
(1, 'Alice'),
(2, 'Bob'),
(3, 'Cara');

INSERT INTO Orders (id, customerId) VALUES
(1, 1),
(2, 1);
```

Expected:

```text
+-----------+
| Customers |
+-----------+
| Bob       |
| Cara      |
+-----------+
```

Multiple orders from the same customer do not affect the result.