LeetCode 1398 - Customers Who Bought Products A and B but Not C

The problem asks us to identify customers who meet a very specific purchasing pattern. We are given two tables: Customer

leetcodemediumdatabase

LeetCode Problem 1398

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to identify customers who meet a very specific purchasing pattern. We are given two tables: Customers and Orders. The Customers table contains the unique customer_id and the corresponding customer_name. The Orders table records purchases with order_id, customer_id, and product_name.

Our task is to find customers who bought both product "A" and product "B" but did not buy product "C". This is important for recommending product "C" to these customers. The output should return the customer_id and customer_name of such customers, sorted by customer_id.

The constraints suggest that a customer may have multiple orders, including multiple products, and that customer_id uniquely identifies a customer. Edge cases to consider include customers who bought none of the products, customers who only bought one of "A" or "B", and customers who bought all three products, including "C".

Approaches

Brute-Force Approach

The brute-force approach involves joining the Customers and Orders tables and checking each customer's purchases individually. For each customer, we would enumerate all their products, check if "A" and "B" are present, and confirm "C" is absent. While this works, it can be inefficient because it requires scanning the Orders table for every customer, resulting in multiple passes over the data.

Optimal Approach

The key observation for an optimal approach is that we can aggregate orders by customer and use conditional logic to count purchases of "A", "B", and "C". If the counts show the customer bought at least one "A" and one "B", and zero "C", then the customer qualifies. This uses a single scan of the Orders table grouped by customer_id and is much more efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(n) Check each customer individually, scanning all orders
Optimal O(n) O(k) Aggregate orders by customer_id and use conditional counts

Here, n is the number of orders, and k is the number of customers.

Algorithm Walkthrough

  1. Join Customers and Orders: Start by joining the Customers table with the Orders table on customer_id to associate each purchase with a customer.
  2. Group by Customer: Aggregate the orders by customer_id so that each customer becomes a single row for evaluation.
  3. Count Conditional Purchases: For each customer group, count whether "A" and "B" appear at least once and ensure that "C" appears zero times.
  4. Filter: Only keep customers that satisfy buying "A" and "B" but not "C".
  5. Select Result: Return the customer_id and customer_name of the filtered customers, sorted by customer_id.

Why it works: By grouping orders per customer and counting purchases conditionally, we ensure that all products bought by a customer are evaluated efficiently. Using aggregation guarantees that each customer is considered exactly once, preserving correctness.

Python Solution

class Solution:
    def customersWhoBoughtABNotC(self, customers: 'List[dict]', orders: 'List[dict]') -> 'List[dict]':
        from collections import defaultdict

        purchase_map = defaultdict(set)
        for order in orders:
            purchase_map[order['customer_id']].add(order['product_name'])

        result = []
        for customer in customers:
            cid = customer['customer_id']
            products = purchase_map.get(cid, set())
            if 'A' in products and 'B' in products and 'C' not in products:
                result.append({'customer_id': cid, 'customer_name': customer['customer_name']})

        return sorted(result, key=lambda x: x['customer_id'])

Implementation Walkthrough: We first build a dictionary mapping each customer_id to a set of products they purchased. This ensures O(1) lookups for product membership. Then, we iterate over the Customers table, check the conditions for "A", "B", and "C", and collect qualifying customers. Finally, we sort the result by customer_id.

Go Solution

package main

type Customer struct {
    CustomerID   int
    CustomerName string
}

type Order struct {
    OrderID     int
    CustomerID  int
    ProductName string
}

func CustomersWhoBoughtABNotC(customers []Customer, orders []Order) []Customer {
    purchaseMap := make(map[int]map[string]bool)

    for _, order := range orders {
        if purchaseMap[order.CustomerID] == nil {
            purchaseMap[order.CustomerID] = make(map[string]bool)
        }
        purchaseMap[order.CustomerID][order.ProductName] = true
    }

    var result []Customer
    for _, customer := range customers {
        products, exists := purchaseMap[customer.CustomerID]
        if !exists {
            continue
        }
        if products["A"] && products["B"] && !products["C"] {
            result = append(result, customer)
        }
    }

    // Sort by CustomerID
    for i := 0; i < len(result)-1; i++ {
        for j := i + 1; j < len(result); j++ {
            if result[i].CustomerID > result[j].CustomerID {
                result[i], result[j] = result[j], result[i]
            }
        }
    }

    return result
}

Go-Specific Notes: We use a map of maps to store purchases per customer. Boolean values indicate whether a product has been purchased. Go does not have a built-in sorting for structs without implementing sort.Interface, so a simple bubble sort is used for clarity.

Worked Examples

Example Input:

Customers: [{1, "Daniel"}, {2, "Diana"}, {3, "Elizabeth"}, {4, "Jhon"}]
Orders: [
    {10, 1, "A"}, {20, 1, "B"}, {30, 1, "D"}, {40, 1, "C"},
    {50, 2, "A"}, {60, 3, "A"}, {70, 3, "B"}, {80, 3, "D"},
    {90, 4, "C"}
]

Step Execution:

  1. Build purchase_map:
customer_id products
1 {A, B, C, D}
2 {A}
3 {A, B, D}
4 {C}
  1. Iterate over customers:
  • Customer 1: has C → excluded
  • Customer 2: missing B → excluded
  • Customer 3: has A, B, no C → included
  • Customer 4: missing A and B → excluded
  1. Sort result → Customer 3 ("Elizabeth").

Complexity Analysis

Measure Complexity Explanation
Time O(n + k log k) O(n) to scan orders, O(k log k) to sort customers where k is qualifying customers
Space O(n) O(n) for the dictionary mapping customer_id to purchased products

The algorithm efficiently scans orders once and uses a dictionary for fast membership checking, avoiding multiple scans or joins.

Test Cases

# test cases
customers = [
    {'customer_id': 1, 'customer_name': 'Daniel'},
    {'customer_id': 2, 'customer_name': 'Diana'},
    {'customer_id': 3, 'customer_name': 'Elizabeth'},
    {'customer_id': 4, 'customer_name': 'Jhon'}
]

orders = [
    {'order_id': 10, 'customer_id': 1, 'product_name': 'A'},
    {'order_id': 20, 'customer_id': 1, 'product_name': 'B'},
    {'order_id': 30, 'customer_id': 1, 'product_name': 'D'},
    {'order_id': 40, 'customer_id': 1, 'product_name': 'C'},
    {'order_id': 50, 'customer_id': 2, 'product_name': 'A'},
    {'order_id': 60, 'customer_id': 3, 'product_name': 'A'},
    {'order_id': 70, 'customer_id': 3, 'product_name': 'B'},
    {'order_id': 80, 'customer_id': 3, 'product_name': 'D'},
    {'order_id': 90, 'customer_id': 4, 'product_name': 'C'}
]

solution = Solution()
assert solution.customersWhoBoughtABNotC(customers, orders) == [{'customer_id': 3, 'customer_name': 'Elizabeth'}]  # Example case

# Edge cases
assert solution.customersWhoBoughtABNotC([], []) == []  # no customers
assert solution.customersWhoBoughtABNotC(customers, []) == []  # no orders
assert solution.customersWhoBoughtABNotC(customers, [{'order_id': 100, 'customer_id': 2, 'product_name': 'B'}]) == []  # only one product each
Test Why
Example case Validates typical scenario
No customers Tests empty input