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.
Problem Overview: The task joins information from two tables: Person and Address. Each person may or may not have an address entry. You must return every person's first name and last name along with their city and state if the address exists. Missing address rows should still keep the person in the result.
Approach 1: Using SQL LEFT JOIN (Time: O(n), Space: O(1))
The most direct solution uses a LEFT JOIN between the Person and Address tables on PersonId. A left join guarantees that every row from Person appears in the result even if no matching address exists. When no match is found, SQL fills City and State with NULL. Database engines typically optimize joins using indexes or hash join strategies, so the operation runs in roughly linear time relative to the number of rows. This is the cleanest and most idiomatic database solution and heavily relies on concepts from database querying.
Approach 2: Using Subqueries (Time: O(n), Space: O(1))
A correlated or nested subquery can retrieve the city and state for each person. For every row in Person, a subquery searches the Address table using the same PersonId. Modern SQL optimizers often rewrite this internally into a join, so practical performance remains close to O(n). This approach works when you want to fetch related values without explicitly writing join syntax, but it is usually less readable than a direct join.
Approach 3: Using a Sorting Technique (Time: O(n log n), Space: O(1) or O(n))
If the data were provided as in-memory arrays rather than database tables, one approach is to sort both datasets by PersonId. After sorting, iterate through both lists using two pointers, similar to a merge step in merge sort. When the IDs match, attach the address information to the person record. If a person has no matching address, output NULL values. Sorting enables deterministic matching but increases the runtime to O(n log n). This pattern appears frequently in problems involving ordered data and relates to sorting strategies.
Approach 4: Using a HashMap for Quick Lookup (Time: O(n), Space: O(n))
A more efficient in-memory solution builds a hash map keyed by PersonId from the Address dataset. Then iterate through the Person list and perform a constant-time lookup to find the corresponding address. If the key is missing, output NULL fields. Hash maps eliminate sorting and reduce the runtime to O(n) with additional memory overhead. This technique mirrors classic lookup optimization problems and uses concepts from hash maps.
Recommended for interviews: The expected database answer is the LEFT JOIN solution. Interviewers want to see that you understand relational joins and how to preserve rows from the primary table when matches are missing. Mentioning the subquery alternative shows SQL familiarity, while discussing hash-map or sorting approaches demonstrates how you would solve the same relationship problem outside a database environment.
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.
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.
SQL
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.
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.
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.
SQL
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.
This approach involves sorting the input data, which allows us to leverage properties of sorted sequences to efficiently solve the problem.
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.
Time Complexity: O(n log n), Space Complexity: O(1) for in-place sorting
This 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.
Here, we implemented a simple hash table using linear probing for collision resolution. Insert allows storing keys with associated values and search provides quick lookup capabilities. This structure supports quick find operations routinely needed.
Time Complexity: O(1) average for insert/search, Space Complexity: O(n) where n is the number of elements.
We can use a left join to join the Person table with the Address table on the condition Person.personId = Address.personId, which will give us the first name, last name, city, and state of each person. If the address of a personId is not in the Address table, it will be reported as null.
| Approach | Complexity |
|---|---|
| Using SQL LEFT JOIN | Time Complexity: O(n + m), where n is the number of rows in the |
| Using Subqueries | Time Complexity: O(n * m), where n is the number of rows in the |
| Approach 1: Using a Sorting Technique | Time Complexity: O(n log n), Space Complexity: O(1) for in-place sorting |
| Approach 2: Using a HashMap for Quick Lookup | Time Complexity: O(1) average for insert/search, Space Complexity: O(n) where n is the number of elements. |
| LEFT JOIN | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL LEFT JOIN | O(n) | O(1) | Standard relational database queries where all rows from the main table must appear |
| SQL Subqueries | O(n) | O(1) | When retrieving related values without explicitly writing join syntax |
| Sorting + Two Pointers | O(n log n) | O(1)–O(n) | When datasets are arrays and can be sorted before matching records |
| HashMap Lookup | O(n) | O(n) | Best for in-memory datasets needing fast key-based lookups |
LeetCode 175: Combine Two Tables [SQL] • Frederik Müller • 48,898 views views
Watch 9 more video solutions →Practice Combine Two Tables with our built-in code editor and test cases.
Practice on FleetCode