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: You have two tables: Person and Address. Each person may or may not have an address entry. The task is to return every person's firstName and lastName along with their city and state. If an address does not exist for a person, the result should still include the person with NULL values for location fields.
Approach 1: Using SQL LEFT JOIN (O(n + m) time, O(1) extra space)
This is the canonical solution and the one interviewers expect. A LEFT JOIN returns all rows from the left table (Person) and matches rows from the right table (Address) based on personId. If no match exists, SQL fills the address columns with NULL. The key insight is that the problem explicitly requires returning every person even when no address exists, which makes a LEFT JOIN the correct relational operation. Databases internally optimize joins using indexing or join algorithms, so the effective complexity is roughly O(n + m) where n and m are table sizes. This approach is standard when working with SQL joins in relational databases.
Approach 2: Using Subqueries (O(n * m) time, O(1) extra space)
A correlated subquery can retrieve city and state for each row in the Person table. For every person, the query searches the Address table for the matching personId. While logically simple, this approach can degrade to O(n * m) time because the subquery may execute once per row. Database optimizers sometimes rewrite this internally as a join, but relying on that behavior is risky in interviews. Subqueries are still useful when you need conditional filtering or scalar lookups within database queries.
Approach 3: Using a Sorting Technique (O(n log n + m log m) time, O(1) extra space)
If the data were handled in application code instead of SQL, you could treat the tables as arrays and perform a merge-style join. First sort both datasets by personId. Then iterate through them simultaneously using two pointers. When IDs match, output the combined record. When the person ID appears without a corresponding address, emit the person with NULL fields. Sorting dominates the runtime at O(n log n + m log m), while the merge scan itself runs in linear time. This mirrors how some database engines implement merge joins internally.
Approach 4: Using a HashMap for Quick Lookup (O(n + m) time, O(m) space)
Another application-level strategy stores all addresses in a hash map keyed by personId. Then iterate through the Person list and perform constant-time lookups. If the ID exists in the map, append the stored city and state. Otherwise return NULL values. This produces linear time complexity because each lookup is O(1). The tradeoff is O(m) additional memory for the map. This technique relies on a hash map for efficient joins outside the database layer.
Recommended for interviews: The LEFT JOIN approach is the expected answer. It directly models the relational requirement: keep all rows from the Person table and optionally attach matching addresses. Explaining alternative strategies like hash-based joins or merge joins shows deeper understanding of how join operations work internally.
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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) average for insert/search, Space Complexity: O(n) where n is the number of elements.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL LEFT JOIN | O(n + m) | O(1) | Standard relational query; best and expected solution for SQL interviews |
| Subqueries | O(n * m) | O(1) | Simple to write but inefficient for large tables |
| Sorting Technique (Merge Join) | O(n log n + m log m) | O(1) | When processing datasets outside a database and IDs can be sorted |
| HashMap Lookup | O(n + m) | O(m) | Application-level join when using in-memory data structures |
LeetCode 175: Combine Two Tables [SQL] • Frederik Müller • 46,482 views views
Watch 9 more video solutions →Practice Combine Two Tables with our built-in code editor and test cases.
Practice on FleetCode