LeetCode 2084 - Drop Type 1 Orders for Customers With Type 0 Orders

LeetCode Problem 2084

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

In this problem, we are given a database table named Orders. Each row represents a single order and contains three columns:

• order_id, the unique identifier for the order
• customer_id, the customer who placed the order
• order_type, which is either 0 or 1

The task is to return a filtered version of the table according to a specific business rule:

• If a customer has at least one order with order_type = 0, then all of that customer's orders with order_type = 1 must be excluded.
• If a customer does not have any type 0 orders, then all of their orders should be included.

The important detail is that the filtering decision is made per customer, not per individual order. We first determine whether the customer has any type 0 orders, then decide which rows to keep.

The output can be returned in any order, which means we do not need an ORDER BY clause unless we want one for readability.

The input table may contain multiple orders per customer, and customers can have:

• only type 0 orders
• only type 1 orders
• a mixture of both

The constraints are not explicitly stated, but this is a standard SQL filtering problem where efficiency still matters. A naive solution that repeatedly scans the table for every row could become expensive for large datasets. The goal is to identify customers with type 0 orders efficiently, then filter rows based on that information.

Several edge cases are important:

• A customer with only type 1 orders should have all their rows included.
• A customer with both type 0 and type 1 orders should only keep the type 0 rows.
• A customer with multiple type 0 orders should keep all of them.
• A customer with exactly one order should still be handled correctly regardless of its type.

Approaches

Brute Force Approach

A straightforward solution is to examine every order individually and determine whether the same customer has any type 0 orders.

For each row in the table:

1. Scan the entire table again.
2. Check whether there exists another row with the same customer_id and order_type = 0.
3. If such a row exists:

• keep the current row only if its own order_type is 0

4. Otherwise:

• keep the row regardless of type

This approach is correct because every row independently verifies whether its customer belongs to the "has type 0 order" category.

However, the performance is poor because every row may require another full scan of the table. If there are n rows, this leads to O(n²) work.

Optimal Approach

The key observation is that the important information is whether a customer has at least one type 0 order.

Instead of repeatedly searching for this information, we can compute it once using a subquery or common table expression.

The optimal strategy is:

1. Identify all customers who have at least one type 0 order.
2. Keep:

• all type 0 rows
• type 1 rows only for customers not in that set

This transforms the repeated lookup into a single preprocessing step. SQL handles this efficiently using IN, NOT IN, EXISTS, or joins.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly scans the table for every row
Optimal	O(n)	O(n)	Precomputes customers with type 0 orders

Algorithm Walkthrough

Optimal SQL Algorithm

1. First, identify all customers who have at least one order of type 0.

We can do this using a subquery:

SELECT customer_id
FROM Orders
WHERE order_type = 0

This creates the set of customers whose type 1 orders must be removed. 2. Next, scan through all rows in the Orders table.

For every row, we decide whether to keep it. 3. If the row has order_type = 0, always keep it.

The problem statement explicitly says that type 0 orders must remain. 4. If the row has order_type = 1, keep it only if the customer is not in the set of customers with type 0 orders.

This ensures that customers with mixed order types lose their type 1 rows. 5. Return the filtered rows.

Since the result may be returned in any order, no sorting is required.

Why it works

The algorithm works because every customer falls into exactly one of two categories:

• customers with at least one type 0 order
• customers without any type 0 orders

For the first category, only type 0 rows are valid. For the second category, all rows are valid. The filtering condition exactly matches these rules, so every retained row is correct and every removed row is invalid.

Python Solution

Even though this is a Database problem, the following Python implementation demonstrates the equivalent logic programmatically.

from typing import List

class Solution:
    def filterOrders(self, orders: List[List[int]]) -> List[List[int]]:
        customers_with_type_zero = set()

        for order_id, customer_id, order_type in orders:
            if order_type == 0:
                customers_with_type_zero.add(customer_id)

        result = []

        for order_id, customer_id, order_type in orders:
            if order_type == 0:
                result.append([order_id, customer_id, order_type])
            elif customer_id not in customers_with_type_zero:
                result.append([order_id, customer_id, order_type])

        return result

The implementation follows the optimal algorithm directly.

The first loop identifies all customers who have at least one type 0 order. A Python set is used because membership checks are extremely fast, typically O(1).

The second loop builds the final answer. If an order is type 0, it is always included. If an order is type 1, it is included only when the customer does not appear in the set.

This mirrors the SQL filtering logic exactly.

Go Solution

package main

type Solution struct{}

func (s Solution) FilterOrders(orders [][]int) [][]int {
	customersWithTypeZero := make(map[int]bool)

	for _, order := range orders {
		customerID := order[1]
		orderType := order[2]

		if orderType == 0 {
			customersWithTypeZero[customerID] = true
		}
	}

	result := [][]int{}

	for _, order := range orders {
		customerID := order[1]
		orderType := order[2]

		if orderType == 0 {
			result = append(result, order)
		} else if !customersWithTypeZero[customerID] {
			result = append(result, order)
		}
	}

	return result
}

The Go implementation follows the same two-pass strategy as the Python version.

A map[int]bool is used to store customers who have type 0 orders. Go maps provide efficient lookup performance similar to Python sets.

Slices are used for storing the result. Since Go does not have Python style dynamic lists, append is used to grow the slice as valid orders are found.

There are no integer overflow concerns here because the operations only involve comparisons and lookups.

SQL Solution

SELECT *
FROM Orders
WHERE order_type = 0
   OR customer_id NOT IN (
       SELECT customer_id
       FROM Orders
       WHERE order_type = 0
   );

This query works by keeping:

• every row where order_type = 0
• rows belonging to customers who never appear in the subquery result

The subquery identifies all customers who have at least one type 0 order.

Worked Examples

Example 1

Input table:

order_id	customer_id	order_type
1	1	0
2	1	0
11	2	0
12	2	1
21	3	1
22	3	0
31	4	1
32	4	1

Step 1, Find customers with type 0 orders

We scan the table and collect customer IDs.

Current Row	Action	Set Contents
(1,1,0)	add customer 1	{1}
(2,1,0)	add customer 1	{1}
(11,2,0)	add customer 2	{1,2}
(12,2,1)	ignore	{1,2}
(21,3,1)	ignore	{1,2}
(22,3,0)	add customer 3	{1,2,3}
(31,4,1)	ignore	{1,2,3}
(32,4,1)	ignore	{1,2,3}

Final set:

{1, 2, 3}

Step 2, Filter rows

Row	Keep?	Reason
(1,1,0)	Yes	type 0 always kept
(2,1,0)	Yes	type 0 always kept
(11,2,0)	Yes	type 0 always kept
(12,2,1)	No	customer 2 has type 0
(21,3,1)	No	customer 3 has type 0
(22,3,0)	Yes	type 0 always kept
(31,4,1)	Yes	customer 4 has no type 0
(32,4,1)	Yes	customer 4 has no type 0

Final output:

order_id	customer_id	order_type
1	1	0
2	1	0
11	2	0
22	3	0
31	4	1
32	4	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to collect customers, one pass to filter
Space	O(n)	The set of customers with type 0 orders may contain all customers

The algorithm performs two linear scans of the input data. Each lookup in the hash set is constant time on average, so the overall runtime remains linear.

The additional memory comes from storing customer IDs that have at least one type 0 order. In the worst case, every customer may appear in the set.

Test Cases

def filter_orders(orders):
    customers_with_type_zero = set()

    for order_id, customer_id, order_type in orders:
        if order_type == 0:
            customers_with_type_zero.add(customer_id)

    result = []

    for order_id, customer_id, order_type in orders:
        if order_type == 0:
            result.append([order_id, customer_id, order_type])
        elif customer_id not in customers_with_type_zero:
            result.append([order_id, customer_id, order_type])

    return result

# Example from problem statement
assert sorted(filter_orders([
    [1, 1, 0],
    [2, 1, 0],
    [11, 2, 0],
    [12, 2, 1],
    [21, 3, 1],
    [22, 3, 0],
    [31, 4, 1],
    [32, 4, 1]
])) == sorted([
    [1, 1, 0],
    [2, 1, 0],
    [11, 2, 0],
    [22, 3, 0],
    [31, 4, 1],
    [32, 4, 1]
])  # mixed customer types

# Customer with only type 1 orders
assert filter_orders([
    [1, 1, 1],
    [2, 1, 1]
]) == [
    [1, 1, 1],
    [2, 1, 1]
]  # all rows retained

# Customer with only type 0 orders
assert filter_orders([
    [1, 1, 0],
    [2, 1, 0]
]) == [
    [1, 1, 0],
    [2, 1, 0]
]  # all type 0 rows retained

# Customer with both types
assert filter_orders([
    [1, 1, 0],
    [2, 1, 1]
]) == [
    [1, 1, 0]
]  # type 1 removed

# Multiple customers with mixed data
assert sorted(filter_orders([
    [1, 1, 1],
    [2, 2, 0],
    [3, 2, 1],
    [4, 3, 1]
])) == sorted([
    [1, 1, 1],
    [2, 2, 0],
    [4, 3, 1]
])  # independent customer handling

# Single order edge case
assert filter_orders([
    [1, 1, 1]
]) == [
    [1, 1, 1]
]  # minimal input

# Empty input
assert filter_orders([]) == []  # no orders

Test	Why
Mixed customer types	Validates the main filtering rule
Only type 1 orders	Ensures rows are preserved correctly
Only type 0 orders	Ensures type 0 rows are never removed
Customer with both types	Confirms type 1 rows are dropped
Multiple customers	Ensures filtering is customer-specific
Single order	Validates minimal non-empty input
Empty input	Confirms algorithm handles no data

Edge Cases

Customers with only type 1 orders

A common mistake is accidentally removing all type 1 rows globally. The filtering rule only applies to customers who also have type 0 orders.

For example:

(31, 4, 1)
(32, 4, 1)

Customer 4 has no type 0 orders, so both rows must remain. The implementation handles this correctly because customer 4 never enters the customers_with_type_zero set.

Customers with both order types

This is the core edge case of the problem.

For example:

(11, 2, 0)
(12, 2, 1)

Once customer 2 is identified as having a type 0 order, every type 1 order for that customer must be excluded. The implementation correctly removes only the type 1 rows while preserving type 0.

Multiple type 0 orders

A customer may have several type 0 orders:

(1,1,0)
(2,1,0)

A buggy implementation might accidentally keep only one of them if it treats the problem as deduplication. However, the problem requires returning all valid rows. Since the algorithm filters rows individually and does not collapse duplicates, every type 0 row is preserved.

Empty input table

Although not shown in the constraints, robust solutions should handle an empty table gracefully.

If the input contains no rows, the set remains empty and the result list also remains empty. The algorithm naturally returns an empty result without special handling.