Table: Person
+-------------+---------+ | Column Name | Type | +-------------+---------+ | personId | int | | lastName | varchar | | firstName | varchar | +-------------+---------+ personId is the primary key (column with unique values) for this table. This table contains information about the ID of some persons and their first and last names.
Table: Address
+-------------+---------+ | Column Name | Type | +-------------+---------+ | addressId | int | | personId | int | | city | varchar | | state | varchar | +-------------+---------+ addressId is the primary key (column with unique values) for this table. Each row of this table contains information about the city and state of one person with ID = PersonId.
Write a solution to report the first name, last name, city, and state of each person in the Person table. If the address of a personId is not present in the Address table, report null instead.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Person table: +----------+----------+-----------+ | personId | lastName | firstName | +----------+----------+-----------+ | 1 | Wang | Allen | | 2 | Alice | Bob | +----------+----------+-----------+ Address table: +-----------+----------+---------------+------------+ | addressId | personId | city | state | +-----------+----------+---------------+------------+ | 1 | 2 | New York City | New York | | 2 | 3 | Leetcode | California | +-----------+----------+---------------+------------+ Output: +-----------+----------+---------------+----------+ | firstName | lastName | city | state | +-----------+----------+---------------+----------+ | Allen | Wang | Null | Null | | Bob | Alice | New York City | New York | +-----------+----------+---------------+----------+ Explanation: There is no address in the address table for the personId = 1 so we return null in their city and state. addressId = 1 contains information about the address of personId = 2.
The key idea in #175 Combine Two Tables is understanding how to merge information stored across two related database tables. Each table contains partial information, and the goal is to produce a result set that shows a person's basic details along with their address information if it exists.
The typical approach is to use a SQL join operation based on a shared key between the tables. In this problem, the relationship is defined through a common identifier column. A LEFT JOIN is generally the most suitable strategy because it ensures that every record from the primary table is included, even if there is no matching entry in the secondary table. When a match is missing, the address-related fields simply appear as NULL.
This approach efficiently combines datasets while preserving all rows from the main table. The query mainly involves selecting the required columns and joining the tables using the shared key.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| SQL LEFT JOIN on key column | O(n + m) | O(1) additional space (query execution dependent) |
Frederik Müller
To solve this problem, we can utilize SQL's LEFT JOIN operation. The LEFT JOIN operation will allow us to join the Person table with the Address table on the personId. It returns all records from the left table (Person), and the matched records from the right table (Address). If there is no match, NULL values are returned for columns from the right table. This operation is suitable because we need to retrieve each person's details regardless of whether they have an address recorded. Thus, using LEFT JOIN will fulfill the requirement of including persons with NULL city and state when there is no matching entry in the Address table.
Time Complexity: O(n + m), where n is the number of rows in the Person table and m is the number of rows in the Address table.
Space Complexity: O(n), where n is the number of rows in the result set.
1SELECT p.firstName, p.lastName, A.city, A.state FROM Person p LEFT JOIN Address A ON p.personId = A.personId;This SQL query selects the first and last names from the Person table and combines them with the city and state fields from the Address table. We use a LEFT JOIN to ensure that even if a person's address doesn't exist, they still appear in the results, with NULL values for the city and state fields.
This approach involves using subqueries to fetch data from the Address table if it exists. This is done by selecting fields from the Person table and then using subqueries to attempt to find the corresponding city and state for each personId from the Address table. If there's no match, the subquery will result in NULL, which aligns with the problem's requirement of reporting NULL when no address is available.
Time Complexity: O(n * m), where n is the number of rows in the Person table and m is the number of rows in the Address table because each subquery runs a separate lookup operation for each person.
Space Complexity: O(n), where n is the number of rows in the result set.
1
2SELECT
3 p.firstName,
4This approach uses a hash map (or dict) to store elements for quick access. This is particularly useful if you need to quickly check for the existence of an element or store counts.
Time Complexity: O(1) average for insert/search, Space Complexity: O(n) where n is the number of elements.
1function
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
LEFT JOIN is used because the problem requires returning all rows from the main table even if there is no corresponding record in the address table. When a match does not exist, the related columns return NULL values.
Yes, similar SQL join problems are common in technical interviews at large tech companies. They help assess a candidate's ability to work with relational databases and combine data from multiple tables efficiently.
This problem primarily tests understanding of SQL joins, especially LEFT JOIN. It also evaluates how well you understand relational keys and how to retrieve columns from multiple tables in a single query.
The optimal approach is to use a SQL LEFT JOIN between the two tables using their shared key. This ensures every record from the main table appears in the result, while matching address information is added when available.
This solution fetches the first and last names directly from the Person table and utilizes subqueries to search for the corresponding city and state. Each subquery runs a lookup in the Address table for the personId. When no corresponding address is found, NULL is returned for both city and state.
We use the C standard library function qsort to sort the array. The compare function is used to define sorting order. Once sorted, you can easily perform further operations based on the problem requirements.
JavaScript's Map object provides efficient means to store key-value pairs and perform average O(1) time complexity operations for lookups and insertions.