Left join behavior in Pandas - Time & Space Complexity

Time Complexity: Left join behavior

O(n)

Understanding Time Complexity

When we combine two tables using a left 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 the tables increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

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

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

This code joins two tables on the 'key' column, keeping all rows from the left table and matching rows from the right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in the left table, find matching rows in the right table.
• How many times: This happens once per row in the left table.

How Execution Grows With Input

As the left table grows, the number of lookups grows too. The right table size affects lookup speed but is usually handled efficiently.

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

Pattern observation: The work grows roughly in direct proportion to the number of rows in the left table.

Final Time Complexity

Time Complexity: O(n)

This means the time to do a left join grows linearly with the number of rows in the left table.

Common Mistake

[X] Wrong: "The join time depends mostly on the size of the right table."

[OK] Correct: The left join keeps all left rows, so the main work is done once per left row. The right table is usually indexed for fast lookups, so its size affects performance less.

Interview Connect

Understanding how joins scale helps you explain data processing clearly and shows you know how databases handle big data efficiently.

Self-Check

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

Practice

1. What does a left join do in pandas when merging two DataFrames?

easy

A. Removes all rows that do not have matches in either DataFrame.

B. Keeps all rows from the left DataFrame and adds matching rows from the right DataFrame.

C. Keeps all rows from the right DataFrame and adds matching rows from the left DataFrame.

D. Keeps only rows that match in both DataFrames.

Solution

1. Step 1: Understand left join behavior

   A left join keeps all rows from the left DataFrame regardless of matches.

2. Step 2: Check how matching rows are added

   Matching rows from the right DataFrame are added; unmatched right rows are ignored.

3. Final Answer:

   Keeps all rows from the left DataFrame and adds matching rows from the right DataFrame. -> Option B

4. Quick Check:

   Left join = all left rows + matching right rows [OK]

Hint: Left join keeps all left rows, adds matching right rows [OK]

Common Mistakes:

• Confusing left join with inner join
• Thinking unmatched right rows appear in output
• Mixing up left and right join behavior

2. Which of the following is the correct syntax to perform a left join of DataFrames df1 and df2 on column 'id' in pandas?

easy

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

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

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

D. pd.concat([df1, df2], join='left')

Solution

1. Step 1: Identify correct merge function and parameters

   Use pd.merge with 'on' for join column and 'how="left"' for left join.

2. Step 2: Check each option's correctness

   pd.merge(df1, df2, on='id', how='left') uses correct function and parameters; others use wrong join type or method.

3. Final Answer:

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

4. Quick Check:

   Left join syntax = pd.merge(..., how='left') [OK]

Hint: Use pd.merge with how='left' for left join [OK]

Common Mistakes:

• Using how='inner' instead of 'left'
• Using pd.concat instead of pd.merge
• Confusing join methods like right join

3. Given these DataFrames:

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

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

medium

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

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

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

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

Solution

1. Step 1: Identify left join behavior on 'id'

   All rows from df1 (ids 1,2,3) appear; matching df2 rows added.

2. Step 2: Match rows and fill unmatched with NaN

   id=1 has no match in df2, so val2 is NaN; id=2 and 3 match with val2 'X' and 'Y'.

3. Final Answer:

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

4. Quick Check:

   Left join keeps all left rows, unmatched right columns = NaN [OK]

Hint: Left join keeps all left rows; unmatched right columns become NaN [OK]

Common Mistakes:

• Including rows from right DataFrame not in left
• Filling unmatched right columns with wrong values
• Confusing left join with inner join output

4. You wrote this code:

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

but got an error: KeyError: 'id'. What is the likely cause?

medium

A. The DataFrames have different lengths.

B. You used 'how="left"' instead of 'how="inner"'.

C. You forgot to import pandas as pd.

D. The 'id' column is missing in one or both DataFrames.

Solution

1. Step 1: Understand KeyError meaning

   KeyError means the specified column 'id' does not exist in one or both DataFrames.

2. Step 2: Check other options for relevance

   Join type or import issues cause different errors; DataFrame length does not cause KeyError.

3. Final Answer:

   The 'id' column is missing in one or both DataFrames. -> Option D

4. Quick Check:

   KeyError 'id' = missing column [OK]

Hint: KeyError on column means column missing in DataFrame [OK]

Common Mistakes:

• Assuming join type causes KeyError
• Ignoring import errors
• Thinking DataFrame length affects merge keys

5. You have two DataFrames:

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

You perform pd.merge(df1, df2, on='key', how='left'). How many rows will the result have?

hard

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Count rows in left DataFrame

   df1 has 4 rows with keys [1, 2, 2, 3].

2. Step 2: Understand left join with duplicate keys

   Each df1 row matches all df2 rows with the same key. Key=2 appears twice in df1 and twice in df2, creating 2x2=4 rows for key=2.

3. Step 3: Calculate total rows

   Key=1 and key=3 have no matches, so they remain as single rows with NaN for val2. Total rows = 1 (key=1) + 4 (key=2 matches) + 1 (key=3) = 6.

4. Final Answer:

   6 -> Option C

5. Quick Check:

   Duplicates multiply rows in left join [OK]

Hint: Duplicates in keys multiply rows in left join output [OK]

Common Mistakes:

• Ignoring duplicate keys causing row multiplication
• Counting only unique keys instead of rows
• Assuming unmatched keys are dropped