rank() method and ranking methods in Pandas - Time & Space Complexity

Time Complexity: rank() method and ranking methods

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to rank data grows as the data size grows.

How does pandas rank() method's speed change when we have more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

df = pd.DataFrame({'score': [10, 20, 20, 30, 40]})
df['rank'] = df['score'].rank(method='average')

This code creates a DataFrame and ranks the 'score' column using the average ranking method.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the column values to determine rank order.
• How many times: The sorting operation processes all rows once.
• Additional steps: Assigning ranks involves scanning the sorted data once more.

How Execution Grows With Input

As the number of rows increases, the time to sort and assign ranks grows.

Input Size (n)	Approx. Operations
10	About 10 * log(10) ≈ 33 operations
100	About 100 * log(100) ≈ 664 operations
1000	About 1000 * log(1000) ≈ 9966 operations

Pattern observation: The operations grow a bit faster than the number of rows because sorting takes more time as data grows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to rank grows a little faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "Ranking is just a simple pass through the data, so it takes linear time O(n)."

[OK] Correct: Ranking needs sorting first, which takes more time than just one pass, so it is slower than O(n).

Interview Connect

Understanding how ranking scales helps you explain performance when working with large datasets in real projects.

Self-Check

What if we used a ranking method that does not require sorting, like assigning ranks based on a pre-sorted column? How would the time complexity change?

Practice

1. What does the rank() method in pandas do?

easy

A. Assigns ranks to values in a Series or DataFrame column based on their order

B. Sorts the data in ascending order permanently

C. Removes duplicate values from the data

D. Calculates the sum of all values in the data

Solution

1. Step 1: Understand the purpose of rank()

   The rank() method assigns a rank number to each value based on its position in sorted order.

2. Step 2: Differentiate from sorting and aggregation

   Unlike sorting or summing, rank() does not change order or calculate totals but gives position numbers.

3. Final Answer:

   Assigns ranks to values in a Series or DataFrame column based on their order -> Option A

4. Quick Check:

   rank() = Assign ranks [OK]

Hint: Remember: rank() gives position, not sorting or sums [OK]

Common Mistakes:

• Confusing rank() with sort()
• Thinking rank() removes duplicates
• Assuming rank() calculates sums

2. Which of the following is the correct syntax to rank a pandas Series s with method 'min'?

easy

A. s.rank(min='method')

B. s.rank(method='min')

C. rank(s, method='min')

D. s.rank(method=min)

Solution

1. Step 1: Recall the correct method call syntax

   In pandas, the rank method is called on the Series object with parameters inside parentheses and method as a string.

2. Step 2: Check each option for syntax errors

   s.rank(method='min') uses correct syntax: s.rank(method='min'). s.rank(min='method') wrongly uses parameter name. rank(s, method='min') uses wrong function call. s.rank(method=min) misses quotes around 'min'.

3. Final Answer:

   s.rank(method='min') -> Option B

4. Quick Check:

   Method name as string in rank() call [OK]

Hint: Use object.method(parameter='value') syntax [OK]

Common Mistakes:

• Omitting quotes around method name
• Using wrong parameter names
• Calling rank as a standalone function

3. Given the pandas Series s = pd.Series([3, 1, 4, 4, 2]), what is the output of s.rank(method='average')?

medium

A. [2.0, 1.0, 4.5, 4.5, 3.0]

B. [3.0, 1.0, 4.0, 5.0, 2.0]

C. [2.0, 1.0, 5.0, 5.0, 3.0]

D. [3.0, 1.0, 4.5, 4.5, 2.0]

Solution

1. Step 1: Sort values and assign ranks with 'average' method

   Sorted values: 1 (rank 1), 2 (rank 2), 3 (rank 3), 4 and 4 (ranks 4 and 5). For ties (4 and 4), average ranks = (4+5)/2 = 4.5.

2. Step 2: Map ranks back to original positions

   Original values: 3 -> rank 3, 1 -> rank 1, 4 -> rank 4.5, 4 -> rank 4.5, 2 -> rank 2. So ranks are [3,1,4.5,4.5,2].

3. Step 3: Check options carefully

   [2.0, 1.0, 4.5, 4.5, 3.0] matches ranks but with 3 replaced by 2.0. Re-examining, 3 is the third smallest value, so rank 3.0 is correct. [2.0, 1.0, 4.5, 4.5, 3.0] shows 2.0 for first value which is 3, so [2.0, 1.0, 4.5, 4.5, 3.0] is incorrect. [3.0, 1.0, 4.5, 4.5, 2.0] shows [3.0,1.0,4.5,4.5,2.0] which matches our calculation.

4. Final Answer:

   [3.0, 1.0, 4.5, 4.5, 2.0] -> Option D

5. Quick Check:

   Average method averages tie ranks correctly [OK]

Hint: Average method assigns mean rank to ties [OK]

Common Mistakes:

• Not averaging ranks for ties
• Assigning ranks in descending order by mistake
• Mixing up rank positions

4. You run df['rank'] = df['score'].rank(method='first') but get unexpected ranks. What is a likely cause?

medium

A. The 'method' parameter does not accept 'first'

B. You forgot to import pandas

C. The 'score' column contains duplicate values and 'first' ranks by order of appearance

D. You need to sort the DataFrame before ranking

Solution

1. Step 1: Understand 'first' method behavior

   The 'first' method assigns ranks in order of appearance for ties, so duplicates get ranks based on their position in the data.

2. Step 2: Identify why ranks seem unexpected

   If duplicates exist, ranks may not be sorted by value but by order, causing confusion if expecting sorted ranks.

3. Final Answer:

   The 'score' column contains duplicate values and 'first' ranks by order of appearance -> Option C

4. Quick Check:

   'first' ranks ties by appearance order [OK]

Hint: Check if duplicates affect 'first' method ranking [OK]

Common Mistakes:

• Assuming 'first' sorts before ranking
• Thinking 'first' is invalid method
• Forgetting duplicates affect rank order

5. You have a DataFrame df with a 'score' column. You want to rank scores in descending order, assign average ranks for ties, and get the rank as a percentage of total rows. Which code achieves this?

hard

A. df['rank'] = df['score'].rank(ascending=False, method='average', pct=True)

B. df['rank'] = df['score'].rank(ascending=True, method='average', pct=True)

C. df['rank'] = df['score'].rank(ascending=False, method='min', pct=False)

D. df['rank'] = df['score'].rank(method='average', pct=True)

Solution

1. Step 1: Set descending order and average method

   To rank highest scores first, set ascending=False. To assign average ranks for ties, use method='average'.

2. Step 2: Get rank as percentage

   Set pct=True to get ranks as percentage of total rows.

3. Step 3: Verify options

   df['rank'] = df['score'].rank(ascending=False, method='average', pct=True) matches all requirements. df['rank'] = df['score'].rank(ascending=True, method='average', pct=True) ranks ascending, wrong order. df['rank'] = df['score'].rank(ascending=False, method='min', pct=False) uses 'min' method and no percentage. df['rank'] = df['score'].rank(method='average', pct=True) misses descending order.

4. Final Answer:

   df['rank'] = df['score'].rank(ascending=False, method='average', pct=True) -> Option A

5. Quick Check:

   Descending + average + pct=True = df['rank'] = df['score'].rank(ascending=False, method='average', pct=True) [OK]

Hint: Use ascending=False and pct=True for descending percent ranks [OK]

Common Mistakes:

• Forgetting ascending=False for descending rank
• Using wrong method for ties
• Missing pct=True for percentage rank