Number of Trusted Contacts of a Customer

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 the Customers table.)

Return the result table ordered by invoice_id.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


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.

Solution

Method 1 – SQL Aggregation and Join

Intuition

For each invoice, we need to count the number of contacts for the customer and how many of those contacts are also customers (trusted contacts). This can be done by joining the tables and using aggregation.

Approach

Join Invoices with Customers to get the customer name for each invoice.
Left join Contacts to count the number of contacts for each user.
For trusted contacts, join Contacts with Customers on email.
Group by invoice and aggregate the counts.

Code

1
2
3
4
5
6
7
8
9


SELECT i.invoice_id, c.customer_name, i.price,
       COUNT(DISTINCT ct.contact_email) AS contacts_cnt,
       COUNT(DISTINCT CASE WHEN cu2.email IS NOT NULL THEN ct.contact_email END) 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 cu2 ON ct.contact_email = cu2.email
GROUP BY i.invoice_id, c.customer_name, i.price
ORDER BY i.invoice_id;

1
2
3
4
5
6
7
8
9


SELECT i.invoice_id, c.customer_name, i.price,
       COUNT(DISTINCT ct.contact_email) AS contacts_cnt,
       COUNT(DISTINCT CASE WHEN cu2.email IS NOT NULL THEN ct.contact_email END) 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 cu2 ON ct.contact_email = cu2.email
GROUP BY i.invoice_id, c.customer_name, i.price
ORDER BY i.invoice_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


import pandas as pd
def number_of_trusted_contacts(customers, contacts, invoices):
    merged = invoices.merge(customers, left_on='user_id', right_on='customer_id', how='left')
    contacts_cnt = contacts.groupby('user_id')['contact_email'].nunique().reset_index(name='contacts_cnt')
    trusted = contacts.merge(customers, left_on='contact_email', right_on='email', how='inner')
    trusted_cnt = trusted.groupby('user_id')['contact_email'].nunique().reset_index(name='trusted_contacts_cnt')
    merged = merged.merge(contacts_cnt, left_on='user_id', right_on='user_id', how='left')
    merged = merged.merge(trusted_cnt, left_on='user_id', right_on='user_id', how='left')
    merged['contacts_cnt'] = merged['contacts_cnt'].fillna(0).astype(int)
    merged['trusted_contacts_cnt'] = merged['trusted_contacts_cnt'].fillna(0).astype(int)
    return merged[['invoice_id', 'customer_name', 'price', 'contacts_cnt', 'trusted_contacts_cnt']].sort_values('invoice_id')

Complexity

⏰ Time complexity: O(N + M + K) where N = #customers, M = #contacts, K = #invoices
🧺 Space complexity: O(N + M + K)

Problem#

Examples#

Solution#

Method 1 – SQL Aggregation and Join#

Intuition#

Approach#

Code#

Complexity#