merge() for SQL-like joins in Pandas - Time & Space Complexity

Time Complexity: merge() for SQL-like joins

O(n + m)

Understanding Time Complexity

When we join two tables using pandas merge(), it takes some time depending on the size of the tables.

We want to understand how the time needed grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

# Two dataframes with n and m rows
df1 = pd.DataFrame({'key': range(n), 'value1': range(n)})
df2 = pd.DataFrame({'key': range(m), 'value2': range(m)})

# Merge on the key column
df_merged = pd.merge(df1, df2, on='key', how='inner')

This code merges two dataframes on a common column called 'key' using an inner join.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Hash-based matching of keys between the two dataframes.
• How many times: Each row in both dataframes is hashed and/or looked up once.

How Execution Grows With Input

As the number of rows in both dataframes grows, the work to find matching keys grows too.

Input Size (n, m)	Approx. Operations
10, 10	About 10 + 10 = 20 operations
100, 100	About 100 + 100 = 200 operations
1000, 1000	About 1000 + 1000 = 2000 operations

Pattern observation: The number of operations grows roughly by the sum of the sizes of the two dataframes.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to merge grows roughly by adding the number of rows in both tables.

Common Mistake

[X] Wrong: "Merging two dataframes always takes time proportional to the size of just one dataframe."

[OK] Correct: The merge compares rows from both dataframes, so the time depends on both sizes, not just one.

Interview Connect

Understanding how merge time grows helps you explain performance in data tasks and shows you think about efficiency clearly.

Self-Check

"What if we merge on a column that is already sorted or indexed? How would the time complexity change?"

Practice

1. What does the merge() function in pandas do?

easy

A. It filters rows based on a condition.

B. It sorts a DataFrame by column values.

C. It changes the data type of a column.

D. It combines two DataFrames based on matching columns.

Solution

1. Step 1: Understand the purpose of merge()

   The merge() function is designed to combine two tables (DataFrames) by matching values in specified columns.

2. Step 2: Compare with other options

   Sorting, filtering, and changing data types are different operations and not the main purpose of merge().

3. Final Answer:

   It combines two DataFrames based on matching columns. -> Option D

4. Quick Check:

   merge() joins tables on columns [OK]

Hint: merge() joins tables by matching columns [OK]

Common Mistakes:

• Confusing merge() with sort or filter functions
• Thinking merge() changes data types
• Assuming merge() works without matching columns

2. Which of the following is the correct syntax to perform an inner join of two DataFrames df1 and df2 on column 'id' using pandas?

easy

A. df1.merge(df2, by='id', join='inner')

B. pd.merge(df1, df2, on='id', how='inner')

C. pd.join(df1, df2, on='id', how='inner')

D. df1.merge(df2, on='id', how='outer')

Solution

1. Step 1: Recall correct merge syntax

   The correct pandas syntax for merging is pd.merge(left, right, on=column, how=type). Here, how='inner' specifies an inner join.

2. Step 2: Check each option

   pd.merge(df1, df2, on='id', how='inner') matches the correct syntax. df1.merge(df2, by='id', join='inner') uses wrong parameter names. pd.join(df1, df2, on='id', how='inner') uses pd.join which does not exist. df1.merge(df2, on='id', how='outer') uses how='outer' which is not inner join.

3. Final Answer:

   pd.merge(df1, df2, on='id', how='inner') -> Option B

4. Quick Check:

   Correct merge syntax = pd.merge(df1, df2, on='id', how='inner') [OK]

Hint: Use pd.merge(df1, df2, on='col', how='inner') [OK]

Common Mistakes:

• Using wrong parameter names like 'by' or 'join'
• Confusing merge() with join() method
• Mixing up 'inner' and 'outer' join types

3. Given the following code:

import pandas as pd

df1 = pd.DataFrame({'id': [1, 2, 3], 'value1': ['A', 'B', 'C']})
df2 = pd.DataFrame({'id': [2, 3, 4], 'value2': ['X', 'Y', 'Z']})
result = pd.merge(df1, df2, on='id', how='inner')
print(result)

What will be the output?

medium

A. id value1 value2
0 2 B X
1 3 C Y

B. id value1 value2
0 1 A NaN
1 2 B X
2 3 C Y

C. id value1 value2
0 2 B X
1 3 C Y
2 4 NaN Z

D. id value1
0 1 A
1 2 B
2 3 C

Solution

1. Step 1: Understand inner join behavior

   An inner join keeps only rows with matching 'id' values in both DataFrames. Here, common ids are 2 and 3.

2. Step 2: Check matching rows and columns

   Rows with id 2 and 3 appear in both df1 and df2, so their columns combine. Rows with id 1 or 4 are excluded.

3. Final Answer:

   id value1 value2 0 2 B X 1 3 C Y -> Option A

4. Quick Check:

   Inner join keeps only matching ids [OK]

Hint: Inner join keeps only rows with matching keys [OK]

Common Mistakes:

• Expecting all rows from both DataFrames
• Confusing inner join with left or outer join
• Ignoring NaN values in output

4. You run this code but get a KeyError:

import pandas as pd

df1 = pd.DataFrame({'key1': [1, 2], 'val': ['A', 'B']})
df2 = pd.DataFrame({'key2': [1, 2], 'val': ['X', 'Y']})
result = pd.merge(df1, df2, on='key1', how='inner')

What is the cause of the error?

medium

A. Column 'key1' does not exist in df2.

B. The merge function requires 'how' to be 'outer'.

C. DataFrames must have the same number of rows to merge.

D. You cannot merge on columns with different names.

Solution

1. Step 1: Check columns in both DataFrames

   df1 has column 'key1', but df2 has 'key2'. The merge tries to join on 'key1' which df2 lacks.

2. Step 2: Understand KeyError cause

   Because 'key1' is missing in df2, pandas raises a KeyError indicating the column is not found.

3. Final Answer:

   Column 'key1' does not exist in df2. -> Option A

4. Quick Check:

   Merge keys must exist in both DataFrames [OK]

Hint: Ensure join columns exist in both DataFrames [OK]

Common Mistakes:

• Assuming merge works with different column names without specifying
• Thinking 'how' parameter causes KeyError
• Believing row counts must match to merge

5. You have two DataFrames:

df_customers = pd.DataFrame({'customer_id': [1, 2, 3], 'name': ['Alice', 'Bob', 'Charlie']})
df_orders = pd.DataFrame({'order_id': [101, 102, 103], 'customer_id': [2, 2, 4], 'amount': [250, 125, 300]})

You want to create a DataFrame showing all customers and their orders, including customers with no orders and orders with no matching customer. Which merge() call achieves this?

hard

A. pd.merge(df_customers, df_orders, on='customer_id', how='left')

B. pd.merge(df_customers, df_orders, on='customer_id', how='inner')

C. pd.merge(df_customers, df_orders, on='customer_id', how='outer')

D. pd.merge(df_customers, df_orders, on='customer_id', how='right')

Solution

1. Step 1: Understand join types

   An outer join keeps all rows from both DataFrames, filling missing matches with NaN.

2. Step 2: Apply to problem context

   We want all customers (even without orders) and all orders (even without matching customers). Only outer join includes all rows from both sides.

3. Final Answer:

   pd.merge(df_customers, df_orders, on='customer_id', how='outer') -> Option C

4. Quick Check:

   Outer join includes all rows from both tables [OK]

Hint: Use how='outer' to keep all rows from both DataFrames [OK]

Common Mistakes:

• Using inner join excludes unmatched rows
• Left join excludes orders without customers
• Right join excludes customers without orders