Outer join in Data Analysis Python - Time & Space Complexity

Time Complexity: Outer join

O(n * m)

Understanding Time Complexity

When combining two tables with an outer join, we want to understand how the time to do this grows as the tables get bigger.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

def outer_join(df1, df2, key):
    result = pd.merge(df1, df2, on=key, how='outer')
    return result

# df1 and df2 are dataframes with n and m rows respectively

This code performs an outer join on two dataframes using a common key, combining all rows from both tables.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching rows from both tables based on the join key.
• 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 rows grows too.

Input Size (n rows in df1, m rows in df2)	Approx. Operations
10, 10	About 100 comparisons
100, 100	About 10,000 comparisons
1000, 1000	About 1,000,000 comparisons

Pattern observation: The number of operations grows roughly by the product of the sizes of the two tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to do the outer join grows roughly by multiplying the number of rows in the first table by the number of rows in the second table.

Common Mistake

[X] Wrong: "The outer join time grows only with the size of one table."

[OK] Correct: Because the join must compare rows from both tables, the time depends on both sizes, not just one.

Interview Connect

Understanding how joins scale helps you explain database performance and write efficient queries, a useful skill in many data roles.

Self-Check

"What if one table is indexed on the join key? How would the time complexity change?"

Practice

1. What does an outer join do when combining two tables?

easy

A. Keeps all rows from both tables, filling missing matches with nulls

B. Keeps only rows that match in both tables

C. Keeps only rows from the first table

D. Keeps only rows from the second table

Solution

1. Step 1: Understand join types

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

2. Step 2: Define outer join behavior

   Outer join fills missing matches with null (or NaN) values to keep all data.

3. Final Answer:

   Keeps all rows from both tables, filling missing matches with nulls -> Option A

4. Quick Check:

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

Hint: Outer join keeps all rows from both tables with nulls for missing [OK]

Common Mistakes:

• Confusing outer join with inner join
• Thinking outer join keeps only one table's rows
• Assuming missing matches are dropped

2. Which of the following is the correct syntax to perform a full outer join using pandas?

easy

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

B. pd.join(df1, df2, type='full')

C. df1.outer_join(df2)

D. pd.merge(df1, df2, how='fulljoin')

Solution

1. Step 1: Recall pandas merge syntax

   Use pd.merge() with how='outer' for full outer join.

2. Step 2: Check options for correctness

   pd.merge(df1, df2, how='outer') matches correct syntax; others use invalid methods or parameters.

3. Final Answer:

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

4. Quick Check:

   pandas full outer join = merge with how='outer' [OK]

Hint: Use pd.merge with how='outer' for full outer join in pandas [OK]

Common Mistakes:

• Using pd.join instead of pd.merge for outer join
• Wrong parameter names like 'fulljoin' or 'type'
• Calling non-existent methods like outer_join

3. Given these two DataFrames:

df1 = pd.DataFrame({'id': [1, 2], 'val1': ['A', 'B']})
df2 = pd.DataFrame({'id': [2, 3], 'val2': ['X', 'Y']})

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

medium

A. [{'id':1, 'val1':'A'}, {'id':2, 'val1':'B'}]

B. [{'id':2, 'val1':'B', 'val2':'X'}]

C. [{'id':1, 'val1':'A', 'val2':NaN}, {'id':2, 'val1':'B', 'val2':'X'}, {'id':3, 'val1':NaN, 'val2':'Y'}]

D. [{'id':3, 'val2':'Y'}]

Solution

1. Step 1: Identify keys and join type

   Joining on 'id' with full outer join keeps all ids from both DataFrames.

2. Step 2: Combine rows with matching and missing data

   id=1 only in df1, id=2 in both, id=3 only in df2; missing values become NaN.

3. Final Answer:

   [{'id':1, 'val1':'A', 'val2':NaN}, {'id':2, 'val1':'B', 'val2':'X'}, {'id':3, 'val1':NaN, 'val2':'Y'}] -> Option C

4. Quick Check:

   Outer join keeps all ids with NaN for missing columns [OK]

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

Common Mistakes:

• Expecting only matching rows (inner join)
• Ignoring NaN for missing matches
• Confusing left or right join results

4. What is wrong with this code snippet for an outer join?

result = pd.merge(df1, df2, on='key', how='outside')

medium

A. df1 and df2 must have the same columns

B. The 'on' parameter should be a list, not a string

C. pd.merge cannot perform outer joins

D. The 'how' parameter value 'outside' is invalid

Solution

1. Step 1: Check 'how' parameter values

   Valid values are 'left', 'right', 'inner', 'outer'; 'outside' is invalid.

2. Step 2: Validate other parameters

   'on' can be string or list; pd.merge supports outer joins; columns can differ.

3. Final Answer:

   The 'how' parameter value 'outside' is invalid -> Option D

4. Quick Check:

   Invalid join type causes error [OK]

Hint: Check 'how' parameter spelling for join type [OK]

Common Mistakes:

• Using invalid join type strings
• Thinking 'on' must be a list always
• Assuming pd.merge can't do outer joins

5. You have two DataFrames:

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

You want to perform a full outer join on 'id' and get all combinations of matching rows (including duplicates). Which code correctly achieves this?

hard

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

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

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

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

Solution

1. Step 1: Understand join type needed

   Full outer join keeps all rows from both DataFrames, including duplicates.

2. Step 2: Check code options for duplicates

   pd.merge(df1, df2, on='id', how='outer') keeps duplicates; pd.merge(df1, df2, on='id', how='outer').drop_duplicates() removes duplicates; pd.merge(df1, df2, on='id', how='inner') is inner join; pd.merge(df1, df2, on='id', how='outer', indicator=True) adds indicator but doesn't affect duplicates.

3. Final Answer:

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

4. Quick Check:

   Full outer join keeps duplicates unless dropped [OK]

Hint: Full outer join keeps duplicates; don't drop them unless needed [OK]

Common Mistakes:

• Using inner join instead of outer join
• Dropping duplicates unintentionally
• Confusing indicator parameter with join behavior