Countries You Can Safely Invest In - Video Solutions
LeetCode 1501: Countries You Can Safely Invest In [SQL]
Countries You Can Safely Invest In - Video Solution
Watch 5 video solutions for Countries You Can Safely Invest In, a medium level problem involving Database. This walkthrough by Frederik Müller has 2,535 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Table Person:
+----------------+---------+ | Column Name | Type | +----------------+---------+ | id | int | | name | varchar | | phone_number | varchar | +----------------+---------+ id is the column of unique values for this table. Each row of this table contains the name of a person and their phone number. Phone number will be in the form 'xxx-yyyyyyy' where xxx is the country code (3 characters) and yyyyyyy is the phone number (7 characters) where x and y are digits. Both can contain leading zeros.
Table Country:
+----------------+---------+ | Column Name | Type | +----------------+---------+ | name | varchar | | country_code | varchar | +----------------+---------+ country_code is the column of unique values for this table. Each row of this table contains the country name and its code. country_code will be in the form 'xxx' where x is digits.
Table Calls:
+-------------+------+ | Column Name | Type | +-------------+------+ | caller_id | int | | callee_id | int | | duration | int | +-------------+------+ This table may contain duplicate rows. Each row of this table contains the caller id, callee id and the duration of the call in minutes. caller_id != callee_id
A telecommunications company wants to invest in new countries. The company intends to invest in the countries where the average call duration of the calls in this country is strictly greater than the global average call duration.
Write a solution to find the countries where this company can invest.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Person table: +----+----------+--------------+ | id | name | phone_number | +----+----------+--------------+ | 3 | Jonathan | 051-1234567 | | 12 | Elvis | 051-7654321 | | 1 | Moncef | 212-1234567 | | 2 | Maroua | 212-6523651 | | 7 | Meir | 972-1234567 | | 9 | Rachel | 972-0011100 | +----+----------+--------------+ Country table: +----------+--------------+ | name | country_code | +----------+--------------+ | Peru | 051 | | Israel | 972 | | Morocco | 212 | | Germany | 049 | | Ethiopia | 251 | +----------+--------------+ Calls table: +-----------+-----------+----------+ | caller_id | callee_id | duration | +-----------+-----------+----------+ | 1 | 9 | 33 | | 2 | 9 | 4 | | 1 | 2 | 59 | | 3 | 12 | 102 | | 3 | 12 | 330 | | 12 | 3 | 5 | | 7 | 9 | 13 | | 7 | 1 | 3 | | 9 | 7 | 1 | | 1 | 7 | 7 | +-----------+-----------+----------+ Output: +----------+ | country | +----------+ | Peru | +----------+ Explanation: The average call duration for Peru is (102 + 102 + 330 + 330 + 5 + 5) / 6 = 145.666667 The average call duration for Israel is (33 + 4 + 13 + 13 + 3 + 1 + 1 + 7) / 8 = 9.37500 The average call duration for Morocco is (33 + 4 + 59 + 59 + 3 + 7) / 6 = 27.5000 Global call duration average = (2 * (33 + 4 + 59 + 102 + 330 + 5 + 13 + 3 + 1 + 7)) / 20 = 55.70000 Since Peru is the only country where the average call duration is greater than the global average, it is the only recommended country.
Approach Overview
Problem Overview: Given Person, Country, and Calls tables, identify countries whose average call duration is greater than the global average duration of all calls. A person's country is determined by matching the phone prefix with the country's code, then aggregating call durations for people from that country.
Approach 1: Equi-Join + Group By + Subquery (O(n log n) time, O(n) space)
This approach explicitly builds the relationship between calls and countries using SQL joins. First map people to countries by matching LEFT(phone_number, 3) with country_code. Each call can involve two countries (caller and callee), so use UNION ALL to normalize both sides into a single stream of (country, duration) rows. After that, use GROUP BY country to compute the average duration per country. A subquery calculates the global average duration across the Calls table, and the outer query filters countries whose average exceeds this value. This method relies heavily on SQL joins and GROUP BY aggregation to perform the analysis directly inside the database.
Approach 2: Default Aggregation Approach (O(n log n) time, O(n) space)
This variant focuses on transforming the calls dataset first, then performing aggregation. Create a derived table that converts every call into two records: one for the caller and one for the callee. Join each participant to their country through the phone prefix mapping. Once the dataset contains a simple structure of (country, duration), calculating country averages becomes straightforward using GROUP BY. Compare each country’s average duration against the global average from a subquery over Calls. This approach keeps the logic modular and easier to reason about when working with database queries involving multiple entity relationships.
Recommended for interviews: The equi-join with GROUP BY and a subquery is the expected solution. Interviewers want to see that you can normalize relational data, handle multiple entity relationships (caller and callee), and perform aggregation with filtering using SQL. Demonstrating the union-based transformation shows a clear understanding of relational query design.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Equi-Join + Group By + Subquery | O(n log n) | O(n) | General SQL solution when calls must be mapped to countries through joins and aggregated |
| Derived Table Aggregation (Default) | O(n log n) | O(n) | When you prefer transforming the dataset first using UNION ALL and then applying aggregation |