Merging on index in Pandas - Time & Space Complexity

Time Complexity: Merging on index

O(n)

Understanding Time Complexity

When we combine two tables by matching their row labels, it takes some time depending on how big the tables are.

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

n = 10  # Example size
# Create two dataframes with indexes
left = pd.DataFrame({'A': range(n)}, index=range(n))
right = pd.DataFrame({'B': range(n)}, index=range(n))

# Merge on index
result = pd.merge(left, right, left_index=True, right_index=True)

This code merges two dataframes by matching their indexes, combining rows with the same index label.

Identify Repeating Operations

• Primary operation: Checking each index in one dataframe and finding the matching index in the other.
• How many times: Once for each row in the first dataframe, so n times.

How Execution Grows With Input

As the number of rows grows, the work to match indexes grows roughly in the same way.

Input Size (n)	Approx. Operations
10	About 10 index matches
100	About 100 index matches
1000	About 1000 index matches

Pattern observation: The number of operations grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to merge grows in a straight line as the number of rows increases.

Common Mistake

[X] Wrong: "Merging on index is instant no matter how big the dataframes are."

[OK] Correct: Even though indexes help find matches quickly, the operation still needs to check each row, so it takes longer as the data grows.

Interview Connect

Understanding how merging on index scales helps you explain data combining tasks clearly and shows you know how data size affects performance.

Self-Check

"What if the indexes were not sorted or unique? How would the time complexity change?"

Practice

1. What does setting left_index=True and right_index=True do when merging two pandas DataFrames?

easy

A. It merges the DataFrames by ignoring the indexes completely.

B. It merges the DataFrames using their column names as the key.

C. It merges the DataFrames by concatenating columns without any key.

D. It merges the DataFrames using their row indexes as the key.

Solution

1. Step 1: Understand the role of indexes in merge

   Indexes are row labels in pandas DataFrames. Using left_index=True and right_index=True tells pandas to join on these row labels instead of columns.

2. Step 2: Effect of these parameters in merge

   When both are True, pandas matches rows based on their index values, combining rows with the same index from both DataFrames.

3. Final Answer:

   It merges the DataFrames using their row indexes as the key. -> Option D

4. Quick Check:

   Merging on indexes = left_index=True and right_index=True [OK]

Hint: Indexes join rows by labels, not columns [OK]

Common Mistakes:

• Thinking merge always uses columns as keys
• Confusing index merge with concatenation
• Ignoring the need to set both left_index and right_index

2. Which of the following is the correct syntax to merge two DataFrames df1 and df2 on their indexes with an inner join?

easy

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

B. pd.merge(df1, df2, left_index=True, right_index=True, how='inner')

C. pd.merge(df1, df2, index=True, how='inner')

D. pd.merge(df1, df2, left_on='index', right_on='index', how='inner')

Solution

1. Step 1: Identify correct parameters for index merge

   To merge on indexes, pandas requires left_index=True and right_index=True. Using on='index' or left_on='index' is incorrect because 'index' is not a column name.

2. Step 2: Confirm the join type

   The how='inner' parameter specifies an inner join, which keeps only matching index rows.

3. Final Answer:

   pd.merge(df1, df2, left_index=True, right_index=True, how='inner') -> Option B

4. Quick Check:

   Use left_index and right_index for index merge [OK]

Hint: Use left_index and right_index, not 'on' for index merge [OK]

Common Mistakes:

• Using on='index' instead of left_index=True
• Confusing index merge with column merge
• Forgetting to set both left_index and right_index

3. Given the following DataFrames:

df1:
       A
idx
1      10
2      20
3      30


df2:
       B
idx
2     200
3     300
4     400

What is the result of pd.merge(df1, df2, left_index=True, right_index=True, how='inner')?

medium

A. {'idx': [2, 3], 'A': [20, 30], 'B': [200, 300]}

B. {'idx': [1, 2, 3], 'A': [10, 20, 30], 'B': [null, 200, 300]}

C. {'idx': [1, 2, 3, 4], 'A': [10, 20, 30, null], 'B': [null, 200, 300, 400]}

D. {'idx': [2, 3, 4], 'A': [20, 30, null], 'B': [200, 300, 400]}

Solution

1. Step 1: Understand inner join on indexes

   An inner join keeps only rows where the index exists in both DataFrames. Here, indexes 2 and 3 are common.

2. Step 2: Combine matching rows

   Rows with index 2 have A=20 and B=200, index 3 have A=30 and B=300. Rows with index 1 and 4 are excluded.

3. Final Answer:

   {'idx': [2, 3], 'A': [20, 30], 'B': [200, 300]} -> Option A

4. Quick Check:

   Inner join keeps only common indexes [OK]

Hint: Inner join keeps only matching index rows [OK]

Common Mistakes:

• Including rows with indexes not in both DataFrames
• Confusing inner join with outer join
• Expecting nulls in inner join result

4. Consider this code snippet:

import pandas as pd

df1 = pd.DataFrame({'A': [1, 2]}, index=[0, 1])
df2 = pd.DataFrame({'B': [3, 4]}, index=[1, 2])

result = pd.merge(df1, df2, left_index=True, right_index=True, how='outer')
print(result)

What is the error in this code?

medium

A. No error; the code runs and merges correctly.

B. Missing 'on' parameter causes a KeyError.

C. left_index and right_index cannot be used together.

D. DataFrames must have the same index values for merge.

Solution

1. Step 1: Check parameters used in merge

   The code uses left_index=True and right_index=True correctly to merge on indexes with how='outer'.

2. Step 2: Understand outer join behavior

   Outer join includes all indexes from both DataFrames, filling missing values with NaN. This is valid and runs without error.

3. Final Answer:

   No error; the code runs and merges correctly. -> Option A

4. Quick Check:

   left_index and right_index merge works fine [OK]

Hint: Outer join merges all indexes, no error with index merge [OK]

Common Mistakes:

• Assuming missing 'on' causes error when using index merge
• Thinking left_index and right_index cannot be combined
• Believing indexes must match exactly for merge

5. You have two DataFrames:

df1:
       Score
Student
Alice     85
Bob       90
Charlie   78


df2:
       Grade
Student
Bob       B
Charlie   C
David     A

You want to merge them so that all students from df1 appear, and matching grades from df2 are added. Missing grades should show as NaN. Which code achieves this?

hard

A. pd.merge(df1, df2, left_index=True, right_index=True, how='right')

B. pd.merge(df1, df2, left_index=True, right_index=True, how='inner')

C. pd.merge(df1, df2, left_index=True, right_index=True, how='left')

D. pd.merge(df1, df2, left_on='Student', right_on='Student', how='outer')

Solution

1. Step 1: Identify merge type for all df1 rows

   To keep all rows from df1 and add matching data from df2, use a left join.

2. Step 2: Merge on indexes

   Both DataFrames use 'Student' as index, so set left_index=True and right_index=True to merge on indexes.

3. Final Answer:

   pd.merge(df1, df2, left_index=True, right_index=True, how='left') -> Option C

4. Quick Check:

   Left join on indexes keeps all df1 rows [OK]

Hint: Left join keeps all left DataFrame rows [OK]

Common Mistakes:

• Using inner join which drops unmatched df1 rows
• Using right join which keeps df2 rows instead
• Merging on columns instead of indexes