Inner join behavior in Pandas - Time & Space Complexity

Time Complexity: Inner join behavior

O(n)

Understanding Time Complexity

When we combine two tables using an inner join, we want to know 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 increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

# Two dataframes with columns 'key' and 'value'
n = 1000

df1 = pd.DataFrame({'key': range(n), 'value': range(n)})
df2 = pd.DataFrame({'key': range(n), 'value': range(n, 2*n)})

# Perform inner join on 'key'
result = pd.merge(df1, df2, on='key', how='inner')
    

This code joins two tables on a common column, keeping only rows with matching keys.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching keys between the two tables.
• How many times: Each row in the first table is checked against keys in the second table.

How Execution Grows With Input

As the number of rows in each table grows, the work to find matching keys grows roughly in proportion to the size of the tables.

Input Size (n)	Approx. Operations
10	About 10 checks per table
100	About 100 checks per table
1000	About 1000 checks per table

Pattern observation: The work grows roughly in a straight line as the tables get bigger.

Final Time Complexity

Time Complexity: O(n)

This means the time to join grows directly with the number of rows in the tables.

Common Mistake

[X] Wrong: "Joining two tables always takes time proportional to the product of their sizes."

[OK] Correct: Pandas uses efficient methods like hashing to avoid checking every pair, so it usually runs in time proportional to the total number of rows, not their product.

Interview Connect

Understanding how joins scale helps you explain data processing choices clearly and shows you know how to handle bigger datasets efficiently.

Self-Check

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

Practice

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

easy

A. Keeps only rows with matching keys in both DataFrames

B. Keeps all rows from the left DataFrame and fills missing with NaN

C. Keeps all rows from the right DataFrame and fills missing with NaN

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

Solution

1. Step 1: Understand join types in pandas

   Inner join keeps only rows where the key exists in both DataFrames.

2. Step 2: Compare with other join types

   Left join keeps all left rows, right join keeps all right rows, outer join keeps all rows from both.

3. Final Answer:

   Keeps only rows with matching keys in both DataFrames -> Option A

4. Quick Check:

   Inner join = matching keys only [OK]

Hint: Inner join keeps only common keys in both tables [OK]

Common Mistakes:

• Confusing inner join with left or outer join
• Thinking inner join keeps all rows
• Assuming inner join fills missing with NaN

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

easy

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

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

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

D. df1.merge(df2, left_on='id', right_on='id', how='left')

Solution

1. Step 1: Identify correct function and parameters

   Use pd.merge() with on='id' and how='inner' for inner join.

2. Step 2: Check other options for errors

   df1.join(df2, on='id') defaults to left join, pd.merge(df1, df2, on='id', how='outer') uses outer join, df1.merge(df2, left_on='id', right_on='id', how='left') uses left join.

3. Final Answer:

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

4. Quick Check:

   pd.merge + how='inner' + on='id' = correct syntax [OK]

Hint: Use pd.merge with how='inner' and on='column' [OK]

Common Mistakes:

• Using wrong join type like 'outer' or 'left'
• Using df.join() without specifying correct parameters
• Mixing left_on and right_on incorrectly

3. Given the following DataFrames:

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

What is the content of result?

medium

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

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

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

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

Solution

1. Step 1: Identify matching keys for inner join

   Inner join keeps rows where 'id' is in both df1 and df2: ids 2 and 3.

2. Step 2: Combine matching rows

   Rows with id 2 and 3 are merged with their respective val1 and val2 values.

3. Final Answer:

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

4. Quick Check:

   Inner join = only common ids 2 and 3 [OK]

Hint: Inner join keeps only keys present in both DataFrames [OK]

Common Mistakes:

• Including rows with id 1 or 4 which are not common
• Confusing inner join with outer join results
• Expecting NaN values in inner join output

4. You run this code:

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

But you get an error: ValueError: columns overlap but no suffix specified. What is the fix?

medium

A. Remove the 'on' parameter from pd.merge()

B. Change how='inner' to how='outer'

C. Rename columns before merge to avoid overlap

D. Add suffixes parameter like suffixes=('_left', '_right') in pd.merge()

Solution

1. Step 1: Understand cause of error

   Both DataFrames have a 'val' column causing overlap without suffixes.

2. Step 2: Apply fix by adding suffixes

   Use suffixes=('_left', '_right') in pd.merge() to differentiate overlapping columns.

3. Final Answer:

   Add suffixes parameter like suffixes=('_left', '_right') in pd.merge() -> Option D

4. Quick Check:

   Overlapping columns need suffixes to avoid error [OK]

Hint: Add suffixes to handle overlapping columns in merge [OK]

Common Mistakes:

• Changing join type does not fix column overlap
• Removing 'on' causes wrong join keys
• Ignoring need for suffixes with overlapping columns

5. You have two DataFrames:

df1 = pd.DataFrame({'id': [1, 2, 2, 3], 'score': [10, 20, 30, 40]})
df2 = pd.DataFrame({'id': [2, 2, 3], 'grade': ['A', 'B', 'C']})
result = pd.merge(df1, df2, on='id', how='inner')

How many rows will result have after the inner join?

hard

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Identify matching keys and duplicates

   Keys 2 and 3 are common. df1 has two rows with id=2, df2 has two rows with id=2.

2. Step 2: Calculate Cartesian product for duplicates

   For id=2: 2 rows in df1 x 2 rows in df2 = 4 rows; for id=3: 1 row x 1 row = 1 row; total = 5 rows.

3. Step 3: Count total rows

   Total rows = 4 (id=2) + 1 (id=3) = 5 rows.

4. Final Answer:

   5 -> Option B

5. Quick Check:

   Duplicates multiply rows in inner join [OK]

Hint: Duplicates multiply rows in inner join result [OK]

Common Mistakes:

• Counting unique keys instead of row combinations
• Ignoring duplicate rows in join keys
• Assuming row count equals unique keys count