Outer join behavior in Pandas - Time & Space Complexity

Time Complexity: Outer join behavior

O(n * m)

Understanding Time Complexity

When we combine two tables using an outer join, we want to see how the time it takes grows as the tables get bigger.

We ask: How does the work increase when the number of rows in each table grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

left = pd.DataFrame({'key': [1, 2, 3], 'value_left': ['A', 'B', 'C']})
right = pd.DataFrame({'key': [2, 3, 4], 'value_right': ['D', 'E', 'F']})

result = pd.merge(left, right, on='key', how='outer')

This code merges two tables on a key column, keeping all rows from both tables.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching keys between the two tables to combine rows.
• How many times: Each row in the first table is compared to rows in the second table to find matches.

How Execution Grows With Input

As the number of rows in each table grows, the work to find matching keys grows too.

Input Size (n)	Approx. Operations
10	About 100 comparisons
100	About 10,000 comparisons
1000	About 1,000,000 comparisons

Pattern observation: The work grows quickly as both tables get bigger, roughly multiplying their sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to join grows roughly by multiplying the number of rows in each table.

Common Mistake

[X] Wrong: "Outer joins always take the same time no matter the table size."

[OK] Correct: The time depends on how many rows each table has because the join checks many pairs of rows.

Interview Connect

Understanding how joins scale helps you explain database performance clearly and shows you know how data size affects work.

Self-Check

"What if we changed the join type from outer to inner? How would the time complexity change?"

Practice

1. What does an outer join do when merging two DataFrames in pandas?

easy

A. Keeps only rows from the right DataFrame

B. Keeps only rows that match in both DataFrames

C. Keeps all rows from both DataFrames, filling missing values with NaN

D. Keeps only rows from the left DataFrame

Solution

1. Step 1: Understand the join types in pandas

   Inner join keeps only matching rows, left join keeps all from left, right join keeps all from right, outer join keeps all from both.

2. Step 2: Identify behavior of outer join

   Outer join includes all rows from both DataFrames and fills missing matches with NaN.

3. Final Answer:

   Keeps all rows from both DataFrames, filling missing values with NaN -> Option C

4. Quick Check:

   Outer join = all rows kept with NaN for missing [OK]

Hint: Outer join keeps all rows, fills missing with NaN [OK]

Common Mistakes:

• Confusing outer join with inner join
• Thinking outer join keeps only left or right rows
• Assuming missing data is dropped instead of NaN

2. Which of the following is the correct syntax to perform an outer join on DataFrames df1 and df2 using pandas?

easy

A. pd.merge(df1, df2, how='outer')

B. pd.merge(df1, df2, join='outer')

C. df1.join(df2, join='outer')

D. df1.merge(df2, type='outer')

Solution

1. Step 1: Recall the pandas merge syntax

   The function pd.merge() takes parameters including left DataFrame, right DataFrame, and how to join.

2. Step 2: Identify correct parameter for outer join

   The parameter to specify join type is how='outer'. Other options like join='outer' or type='outer' are invalid.

3. Final Answer:

   pd.merge(df1, df2, how='outer') -> Option A

4. Quick Check:

   Use how='outer' in pd.merge() [OK]

Hint: Use how='outer' in pd.merge() for outer join [OK]

Common Mistakes:

• Using join='outer' instead of how='outer'
• Using type='outer' which is invalid
• Using df1.join() without specifying correct parameters

3. Given the following DataFrames:

df1 = pd.DataFrame({'key': ['A', 'B'], 'val1': [1, 2]})
df2 = pd.DataFrame({'key': ['B', 'C'], 'val2': [3, 4]})

What is the result of pd.merge(df1, df2, on='key', how='outer')?

medium

A. {'key': ['A', 'B'], 'val1': [1, 2], 'val2': [NaN, 3]}

B. {'key': ['A', 'B', 'C'], 'val1': [1, 2, NaN], 'val2': [NaN, 3, 4]}

C. {'key': ['B'], 'val1': [2], 'val2': [3]}

D. {'key': ['B', 'C'], 'val1': [2, NaN], 'val2': [3, 4]}

Solution

1. Step 1: Identify keys and values in both DataFrames

   df1 keys: A, B with val1 1, 2; df2 keys: B, C with val2 3, 4.

2. Step 2: Perform outer join on 'key'

   Outer join keeps all keys: A, B, C. For A val2 is missing (NaN), for C val1 is missing (NaN), B has both values.

3. Final Answer:

   {'key': ['A', 'B', 'C'], 'val1': [1, 2, NaN], 'val2': [NaN, 3, 4]} -> Option B

4. Quick Check:

   Outer join keeps all keys with NaN for missing values [OK]

Hint: Outer join keys = union of keys, missing values become NaN [OK]

Common Mistakes:

• Confusing outer join with inner join (only B)
• Missing keys from either DataFrame
• Not filling missing values with NaN

4. You wrote this code but got an error:

pd.merge(df1, df2, how='outer', on='key', left_index=True)

What is the likely cause of the error?

medium

A. Cannot use both 'on' and 'left_index=True' together in merge

B. Missing 'right_index=True' parameter

C. The 'how' parameter should be 'outerjoin' not 'outer'

D. DataFrames must have the same columns to merge

Solution

1. Step 1: Understand parameters 'on' and 'left_index'

   'on' specifies column to join on; 'left_index=True' uses index for join. Both cannot be used simultaneously.

2. Step 2: Identify conflict causing error

   Using 'on' and 'left_index=True' together causes pandas to raise an error because join keys are ambiguous.

3. Final Answer:

   Cannot use both 'on' and 'left_index=True' together in merge -> Option A

4. Quick Check:

   'on' and 'left_index=True' conflict in merge [OK]

Hint: Don't mix 'on' with 'left_index=True' in merge [OK]

Common Mistakes:

• Assuming 'how'='outerjoin' is valid
• Forgetting that 'on' and 'left_index' conflict
• Thinking DataFrames must have same columns to merge

5. You have two DataFrames:

df1 = pd.DataFrame({'id': [1, 2, 3], 'score': [10, 20, 30]})
df2 = pd.DataFrame({'id': [2, 3, 4], 'grade': ['B', 'A', 'C']})

You want to merge them with an outer join but replace all NaN in 'score' with 0 and in 'grade' with 'N/A'. Which code correctly does this?

hard

A. result = pd.merge(df1, df2, on='id', how='outer').fillna({'score': 0})

B. result = pd.merge(df1, df2, on='id', how='outer').fillna(0).fillna('N/A')

C. result = pd.merge(df1, df2, on='id', how='outer').fillna({'score': 'N/A', 'grade': 0})

D. result = pd.merge(df1, df2, on='id', how='outer').fillna({'score': 0, 'grade': 'N/A'})

Solution

1. Step 1: Perform outer join on 'id'

   Outer join keeps all ids: 1, 2, 3, 4. Missing 'score' or 'grade' will be NaN.

2. Step 2: Replace NaN with correct values per column

   Use fillna with a dictionary to specify 0 for 'score' and 'N/A' for 'grade'. Other options either fill all with 0 or wrong values.

3. Final Answer:

   result = pd.merge(df1, df2, on='id', how='outer').fillna({'score': 0, 'grade': 'N/A'}) -> Option D

4. Quick Check:

   Use fillna with dict for column-specific NaN replacement [OK]

Hint: Use fillna({'col1': val1, 'col2': val2}) for different columns [OK]

Common Mistakes:

• Using fillna(0) for all columns, replacing strings incorrectly
• Swapping fillna values between columns
• Not filling NaN for all missing columns