LeetCode 1364 - Number of Trusted Contacts of a Customer

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze relationships between customers, their contacts, and invoices. We are given three tables: Customers, Contacts, and Invoices. The Customers table identifies each customer by customer_id along with their name and email. The Contacts table contains a list of contacts for each customer, with user_id referring to the customer and each contact listed by name and email. The Invoices table lists invoices linked to customers through user_id along with the invoice price.

The task is to produce, for every invoice, the customer name, invoice price, the number of contacts that customer has, and the number of “trusted contacts” - contacts whose email also exists in the Customers table, indicating that the contact is also a customer. The output should be ordered by invoice_id.

Key points to note are that a contact may not exist as a customer, a customer can have zero contacts, and the primary key of Contacts ensures no duplicate (user_id, contact_email) entries. The dataset may have multiple invoices for the same customer, and the solution must handle that properly.

Edge cases include customers with no contacts, contacts that are not registered customers, and multiple invoices for a single customer.

Approaches

The brute-force approach would join the Invoices table to the Customers table to get the name, then for each invoice, iterate over the contacts of the customer and count how many exist in the Customers table. While conceptually simple, this involves repeated subqueries or joins per invoice, which can be expensive if the tables are large.

The optimal approach uses SQL joins and aggregation efficiently. We first join Invoices to Customers to get the customer name. Then we left join Contacts to count all contacts. For trusted contacts, we do another left join from Contacts to Customers on the email field to see which contacts are also customers. We aggregate using COUNT and COUNT(DISTINCT) while grouping by invoice_id, customer_name, and price. This approach avoids multiple scans and leverages SQL’s set-based operations for efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(I * C)	O(1)	Iterate invoices, for each, scan contacts and customers
Optimal	O(I + C + K)	O(C + K)	Use joins and aggregations; single scan of tables

Algorithm Walkthrough

Start by joining Invoices with Customers on user_id = customer_id to get the customer_name for each invoice.
Left join Contacts on user_id = customer_id to include contact information for counting.
Left join Customers again on Contacts.contact_email = Customers.email to identify which contacts are trusted.
Group by invoice_id, customer_name, and price to allow aggregation.
Count the total contacts using COUNT(Contacts.contact_email) and count trusted contacts using COUNT(Customers.customer_id) (only non-null if the contact is a registered customer).
Order the results by invoice_id.

This works because SQL aggregation ensures we count exactly the relationships we want. Left joins allow us to include customers with zero contacts, and matching by email ensures correct identification of trusted contacts.

Python Solution

class Solution:
    def trustedContacts(self):
        query = """
        SELECT 
            i.invoice_id,
            c.customer_name,
            i.price,
            COUNT(ct.contact_email) AS contacts_cnt,
            COUNT(c2.customer_id) AS trusted_contacts_cnt
        FROM Invoices i
        JOIN Customers c ON i.user_id = c.customer_id
        LEFT JOIN Contacts ct ON i.user_id = ct.user_id
        LEFT JOIN Customers c2 ON ct.contact_email = c2.email
        GROUP BY i.invoice_id, c.customer_name, i.price
        ORDER BY i.invoice_id
        """
        return query

This SQL query is encapsulated in a Python method to match the typical LeetCode SQL problem stub. The first join connects invoices to customers to get names. The first left join includes contacts, and the second left join checks which contacts are trusted. Aggregation counts total contacts and trusted contacts, and the final ordering ensures the output is sorted by invoice_id.

Go Solution

func TrustedContacts() string {
    return `
    SELECT 
        i.invoice_id,
        c.customer_name,
        i.price,
        COUNT(ct.contact_email) AS contacts_cnt,
        COUNT(c2.customer_id) AS trusted_contacts_cnt
    FROM Invoices i
    JOIN Customers c ON i.user_id = c.customer_id
    LEFT JOIN Contacts ct ON i.user_id = ct.user_id
    LEFT JOIN Customers c2 ON ct.contact_email = c2.email
    GROUP BY i.invoice_id, c.customer_name, i.price
    ORDER BY i.invoice_id;
    `
}

The Go version returns the SQL query as a string. Functionally it mirrors the Python solution. Go does not require any special handling of SQL results at this stage; the SQL engine executes the query and returns the aggregated result.

Worked Examples

For the first invoice 77 linked to Alice:

Join Invoices to Customers → invoice 77 → Alice
Left join Contacts → Bob, John, Jal
Left join Customers on contact_email → Bob and John match customers
Count total contacts → 3
Count trusted contacts → 2
Result → 77, Alice, 100, 3, 2

For invoice 55 linked to John:

Join Invoices to Customers → invoice 55 → John
Left join Contacts → no contacts
Trusted contacts → none
Result → 55, John, 500, 0, 0

This process repeats for all invoices, producing the output as requested.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(I + C + K)	One scan of Invoices (I), Contacts (C), and Customers (K) with joins
Space	O(C + K)	Joins may temporarily store results in memory

The complexity is efficient because joins are handled by SQL engines in optimized ways, often using indexes.

Test Cases

# Example test case from problem
assert Solution().trustedContacts() is not None  # SQL query correctness
# Edge cases: customer with no contacts
# Edge cases: contact not in customers
# Multiple invoices per customer

Test	Why
Invoice 77 for Alice	Tests multiple contacts and trusted contacts
Invoice 55 for John	Tests zero contacts
Invoice 44 for Alex	Tests single contact who is trusted
Multiple invoices for same user	Tests correct grouping

Edge Cases

The first edge case is a customer with zero contacts. A naive join without left join may exclude these customers entirely. The solution handles this with left joins, counting nulls correctly as zero.

The second edge case is a contact that is not a customer. A naive inner join would exclude these from counting. The solution counts contacts regardless, and only counts trusted contacts when a customer match exists.

The third edge case is multiple invoices for a single customer. Aggregation must be done per invoice, not per customer. Grouping by invoice_id ensures each invoice is treated independently even if the customer appears multiple times.