Number of Trusted Contacts of a Customer solution and explanation
2 more videos on this problem
LeetCode 1364: Number of Trusted Contacts of a Customer [SQL]Frederik Müller · 10:42 · 2K views
Leetcode MEDIUM 1364 - Number of Trusted Contacts MULTIPLE JOINS- Explained by Everyday Data ScienceEveryday Data Science · 11:05 · 681 views
LeetCode 1364: Number of Trusted ContactsAlitaCode · 23:04 · 2 views
The problem
Table: Customers
+---------------+---------+ | Column Name | Type | +---------------+---------+ | customer_id | int | | customer_name | varchar | | email | varchar | +---------------+---------+ customer_id is the column of unique values for this table. Each row of this table contains the name and the email of a customer of an online shop.
Table: Contacts
+---------------+---------+ | Column Name | Type | +---------------+---------+ | user_id | id | | contact_name | varchar | | contact_email | varchar | +---------------+---------+ (user_id, contact_email) is the primary key (combination of columns with unique values) for this table. Each row of this table contains the name and email of one contact of customer with user_id. This table contains information about people each customer trust. The contact may or may not exist in the Customers table.
Table: Invoices
+--------------+---------+ | Column Name | Type | +--------------+---------+ | invoice_id | int | | price | int | | user_id | int | +--------------+---------+ invoice_id is the column of unique values for this table. Each row of this table indicates that user_id has an invoice with invoice_id and a price.
Write a solution to find the following for each invoice_id:
customer_name: The name of the customer the invoice is related to.price: The price of the invoice.contacts_cnt: The number of contacts related to the customer.trusted_contacts_cnt: The number of contacts related to the customer and at the same time they are customers to the shop. (i.e their email exists in theCustomerstable.)
Return the result table ordered by invoice_id.
The result format is in the following example.
Example 1:
Input: Customers table: +-------------+---------------+--------------------+ | customer_id | customer_name | email | +-------------+---------------+--------------------+ | 1 | Alice | alice@leetcode.com | | 2 | Bob | bob@leetcode.com | | 13 | John | john@leetcode.com | | 6 | Alex | alex@leetcode.com | +-------------+---------------+--------------------+ Contacts table: +-------------+--------------+--------------------+ | user_id | contact_name | contact_email | +-------------+--------------+--------------------+ | 1 | Bob | bob@leetcode.com | | 1 | John | john@leetcode.com | | 1 | Jal | jal@leetcode.com | | 2 | Omar | omar@leetcode.com | | 2 | Meir | meir@leetcode.com | | 6 | Alice | alice@leetcode.com | +-------------+--------------+--------------------+ Invoices table: +------------+-------+---------+ | invoice_id | price | user_id | +------------+-------+---------+ | 77 | 100 | 1 | | 88 | 200 | 1 | | 99 | 300 | 2 | | 66 | 400 | 2 | | 55 | 500 | 13 | | 44 | 60 | 6 | +------------+-------+---------+ Output: +------------+---------------+-------+--------------+----------------------+ | invoice_id | customer_name | price | contacts_cnt | trusted_contacts_cnt | +------------+---------------+-------+--------------+----------------------+ | 44 | Alex | 60 | 1 | 1 | | 55 | John | 500 | 0 | 0 | | 66 | Bob | 400 | 2 | 0 | | 77 | Alice | 100 | 3 | 2 | | 88 | Alice | 200 | 3 | 2 | | 99 | Bob | 300 | 2 | 0 | +------------+---------------+-------+--------------+----------------------+ Explanation: Alice has three contacts, two of them are trusted contacts (Bob and John). Bob has two contacts, none of them is a trusted contact. Alex has one contact and it is a trusted contact (Alice). John doesn't have any contacts.
Approach overview
Problem Overview: Each invoice belongs to a customer. For every invoice, return the customer name, invoice price, the number of contacts that customer has, and how many of those contacts are trusted. A contact becomes trusted if the contact's email matches the email of an existing customer. The result must be produced using SQL joins and aggregations.
Approach 1: Correlated Subqueries (O(n * m) time, O(1) extra space)
A straightforward solution uses correlated subqueries for each invoice row. First join Invoices with Customers to get the invoice owner. Then compute contacts_cnt by counting rows in Contacts where Contacts.user_id = Customers.customer_id. To compute trusted_contacts_cnt, add another subquery that checks whether the contact email exists in the Customers table. Each invoice triggers multiple nested lookups, so performance degrades as the number of contacts grows. This approach works for small datasets but becomes inefficient with large tables because each row repeatedly scans related records.
Approach 2: Join + Aggregation (Optimal SQL Approach) (O(n log n) time, O(n) space)
The efficient solution uses joins and a single aggregation pass. Start by joining Invoices with Customers to identify the invoice owner. Next, left join the Contacts table on Customers.customer_id = Contacts.user_id to bring in all contacts for that customer. To detect trusted contacts, join Contacts.contact_email with Customers.email (using another alias of the Customers table). Now you can count total contacts with COUNT(Contacts.contact_email) and trusted contacts using conditional counting such as COUNT(trusted_customer.customer_id). Finally, group by invoice attributes to aggregate results correctly. This reduces repeated scans and lets the database optimizer handle indexing and join planning efficiently.
This pattern is common in relational queries where you need both total relationships and filtered relationships in the same result set. Mastering joins and conditional aggregation is critical for database interview questions and real production analytics queries.
Recommended for interviews: The join + aggregation solution is what interviewers expect. It demonstrates understanding of SQL joins and relational aggregation. Showing the subquery approach first proves you understand the logic, but the optimized join-based solution shows you know how to write scalable SQL.
Solution
# Write your MySQL query statement below
SELECT
invoice_id,
t2.customer_name,
price,
COUNT(t3.user_id) AS contacts_cnt,
COUNT(t4.email) AS trusted_contacts_cnt
FROM
Invoices AS t1
LEFT JOIN Customers AS t2 ON t1.user_id = t2.customer_id
LEFT JOIN Contacts AS t3 ON t1.user_id = t3.user_id
LEFT JOIN Customers AS t4 ON t3.contact_email = t4.email
GROUP BY invoice_id
ORDER BY invoice_id;Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subqueries | O(n * m) | O(1) | Quick prototype or small datasets where query readability matters more than performance |
| Join + Aggregation (Optimal) | O(n log n) | O(n) | Production queries and interview settings requiring efficient relational joins |
Frequently asked questions
Is Number of Trusted Contacts of a Customer easy or hard?
The problem is rated Medium because it requires combining multiple joins with conditional counting. Understanding how to aggregate while preserving invoice-level rows is the main challenge.
Number of Trusted Contacts of a Customer Python/Java solution
This problem is designed for SQL rather than Python or Java. The expected solution is a MySQL query using joins and GROUP BY aggregation to compute contacts_cnt and trusted_contacts_cnt for each invoice.
How to solve Number of Trusted Contacts of a Customer in O(n)?
Near O(n) performance is possible when proper indexes exist on Customers.email and Contacts.user_id. The query joins Invoices → Customers → Contacts and performs a conditional count of trusted contacts where contact_email matches a customer email. Aggregation with GROUP BY computes both counts in one pass.
What is the best approach for Number of Trusted Contacts of a Customer?
The optimal approach uses SQL joins with aggregation. Join Invoices with Customers to identify the invoice owner, left join Contacts to count total contacts, and join Customers again on email to detect trusted contacts. Use GROUP BY to aggregate counts per invoice. This avoids repeated subqueries and runs in roughly O(n log n) depending on indexing.
Is Number of Trusted Contacts of a Customer asked at Google/Amazon/Meta?
SQL aggregation and join problems like this frequently appear in database interviews at companies such as Amazon, Meta, and other data-heavy teams. The exact question may vary, but counting relationships and filtered relationships in one query is a common interview pattern.
What data structure is used in Number of Trusted Contacts of a Customer?
The problem relies on relational database tables and SQL join operations rather than in-memory data structures. Conceptually, the solution behaves like hash lookups between tables when indexes are present, especially when matching contact_email with customer email.
What is the time complexity of Number of Trusted Contacts of a Customer?
The optimized join-based solution runs in about O(n log n) time because the database performs indexed joins and grouped aggregation. Without indexes, joins may approach O(n^2). The correlated subquery approach can be significantly slower since it performs repeated scans for each invoice row.