LeetCode 175 - Combine Two Tables

The problem is asking us to combine two relational database tables, Person and Address, in such a way that we report each person's first name, last name, city, and state.

leetcodeeasydatabase

LeetCode Problem 175

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem is asking us to combine two relational database tables, Person and Address, in such a way that we report each person's first name, last name, city, and state. The Person table contains identifiers and names of people, while the Address table contains identifiers, the corresponding personId, and the city and state of that person. Importantly, not every person will necessarily have an entry in the Address table. When a person has no corresponding address, we should return null for both city and state.

The input is relational table data, essentially two sets of structured records. The expected output is a combined table, where each row represents a person from the Person table along with their address if available. The ordering of the output rows is not important.

Key constraints and observations include: every personId in the Person table is unique, each addressId is unique in Address, and personId in Address may not exist in Person (irrelevant addresses can be ignored). Edge cases include people without addresses, addresses without matching people, and empty tables.

Approaches

A brute-force approach would iterate over every person and then search the Address table for a matching personId. For each person, you would scan the Address table linearly to find a match. This would give the correct output, but it is inefficient, with time complexity O(n*m), where n is the number of people and m is the number of addresses. For large tables, this approach is suboptimal.

The optimal approach leverages SQL JOIN operations. Specifically, a LEFT JOIN is appropriate here because it ensures that all records from the Person table are included, even if there is no matching personId in Address. The database engine internally indexes and optimizes the join operation, providing an efficient way to merge the tables in a single query.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*m) O(1) Iterate over each person and scan the address table for a match
Optimal O(n + m) O(1) Use SQL LEFT JOIN to efficiently merge tables on personId

Algorithm Walkthrough

  1. Start by selecting all columns you want from the Person table: firstName and lastName. These will form the basis of the output.
  2. Perform a LEFT JOIN with the Address table using the condition Person.personId = Address.personId. This ensures every person appears in the output.
  3. Select the city and state columns from the Address table. If a person does not have a corresponding address, these fields will automatically be NULL due to the LEFT JOIN semantics.
  4. Return the resulting table. No additional filtering or sorting is required because the problem does not impose ordering constraints.

Why it works: The LEFT JOIN guarantees that every person from the Person table is included, and the join condition ensures that the address information is correctly aligned with the person. If no address exists, the SQL engine automatically fills in NULLs for the missing fields, satisfying the problem requirement.

Python Solution

class Solution:
    def getPersonAddress(self) -> str:
        return """
        SELECT 
            p.firstName, 
            p.lastName, 
            a.city, 
            a.state
        FROM Person p
        LEFT JOIN Address a
        ON p.personId = a.personId;
        """

The Python solution simply returns a SQL query as a string. The query performs a LEFT JOIN of the Person table with the Address table, ensuring all people are included. It selects the desired columns, and NULL values are automatically handled for missing addresses.

Go Solution

func GetPersonAddress() string {
    return `
        SELECT 
            p.firstName, 
            p.lastName, 
            a.city, 
            a.state
        FROM Person p
        LEFT JOIN Address a
        ON p.personId = a.personId;
    `
}

The Go implementation mirrors the Python solution. The main difference is syntax for returning a multiline string using backticks. The logic of the SQL query remains identical.

Worked Examples

Example 1:

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

Step by step:

  1. LEFT JOIN matches personId = 1 with Address. No match, so city and state are NULL.
  2. LEFT JOIN matches personId = 2 with Address. Finds New York City and New York.
  3. personId = 3 in Address is ignored because it does not exist in Person.

Result:

firstName lastName city state
Allen Wang NULL NULL
Bob Alice New York City New York

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) SQL engine efficiently performs a LEFT JOIN using indexing or hash join internally
Space O(1) Query execution requires no extra space proportional to input; result set returned by database

The complexity is derived from SQL engine optimizations. Conceptually, the LEFT JOIN involves scanning both tables once and aligning records, which is linear in the size of the tables.

Test Cases

# Provided example
assert Solution().getPersonAddress() == """
        SELECT 
            p.firstName, 
            p.lastName, 
            a.city, 
            a.state
        FROM Person p
        LEFT JOIN Address a
        ON p.personId = a.personId;
    """

# Edge case: empty Person table
# Output should be an empty table

# Edge case: empty Address table
# All city and state should be NULL

# Edge case: multiple people with no addresses
# Each row's city and state should be NULL

# Edge case: address exists without matching person
# These addresses are ignored
Test Why
Provided example Validates standard merge and NULL handling
Empty Person table Ensures query handles zero rows gracefully
Empty Address table Ensures NULLs are returned for missing addresses
Multiple people no addresses Tests multiple NULL outputs
Address without matching person Confirms irrelevant addresses are ignored

Edge Cases

One important edge case is when the Person table is empty. In this case, the LEFT JOIN will produce no rows, which is correct and should not result in errors. Another edge case is when the Address table is empty, meaning every person in the output should have NULL for city and state; the LEFT JOIN correctly handles this automatically. A third edge case involves addresses that reference personIds not present in the Person table; the LEFT JOIN ignores these records since there is no corresponding row in Person, avoiding incorrect inclusion in the output. These edge cases ensure robustness of the solution across all possible input scenarios.