Problem Description

You have an array ranks where ranks[i] represents the rank of the i-th student arriving in order. A smaller rank number means a better rank (for example, rank 1 is better than rank 5).

Initially, the first student to arrive is automatically selected.

A replacement happens when a new student arrives with a strictly better rank (smaller number) than the currently selected student. When this happens, the new student replaces the currently selected one.

Your task is to count how many times a replacement occurs as students arrive one by one.

For example, if ranks = [3, 1, 4, 2]:

• Student with rank 3 arrives first and is selected (no replacement)
• Student with rank 1 arrives and replaces the current selection since 1 < 3 (1 replacement)
• Student with rank 4 arrives but doesn't replace since 4 > 1 (no replacement)
• Student with rank 2 arrives but doesn't replace since 2 > 1 (no replacement)
• Total replacements = 1

The solution tracks the current best rank using variable cur, starting with the first student's rank. For each subsequent student, if their rank is better (smaller) than cur, we update cur and increment our replacement counter. The final count is returned as the answer.

Intuition

The key insight is that we only care about tracking the best (smallest) rank seen so far. Since students arrive in order and we can only replace the current selection with someone better, we need to maintain a running minimum.

Think of it like a competition where the current champion can only be dethroned by someone with a better score. Each time we see a new student, we ask: "Is this student's rank better than our current champion?" If yes, we have a new champion (replacement occurs). If no, the current champion stays.

This naturally leads to a single-pass solution where we:

1. Start with the first student as our initial selection (they're selected by default)
2. For each new student, compare their rank with the current best
3. If they have a better rank (smaller number), they become the new selection and we count this as a replacement

The pattern here is essentially finding how many times the minimum value updates as we traverse the array from left to right. Each update represents a replacement event. This is why we only need to track the current minimum (cur) and count how many times it changes (ans).

Since we process students in arrival order and only make decisions based on the current best rank, we don't need to look ahead or store previous values - just maintain the running minimum and count the updates.

Solution Approach

We implement a simulation approach that processes students one by one in their arrival order.

The algorithm uses two variables:

• cur: tracks the rank of the currently selected student
• ans: counts the total number of replacements

Step-by-step implementation:

1. Initialize: Set cur = ranks[0] (the first student is selected by default) and ans = 0 (no replacements yet)

2. Iterate through all students: For each student's rank x in the array:

   • Check if x < cur (is this student's rank better than the current selection?)
   • If yes:
     • Update cur = x (this student becomes the new selection)
     • Increment ans += 1 (count this replacement)
   • If no: continue to the next student

3. Return the result: After processing all students, return ans as the total number of replacements

The code implementation:

class Solution:
    def totalReplacements(self, ranks: List[int]) -> int:
        ans, cur = 0, ranks[0]
        for x in ranks:
            if x < cur:
                cur = x
                ans += 1
        return ans

Time Complexity: O(n) where n is the length of the ranks array, as we make a single pass through the array.

Space Complexity: O(1) as we only use two variables regardless of input size.

The beauty of this solution is its simplicity - we're essentially tracking the running minimum and counting how many times it changes throughout the traversal.

Example Walkthrough

Let's trace through the algorithm with ranks = [5, 2, 6, 1, 3]:

Initial Setup:

• cur = ranks[0] = 5 (first student with rank 5 is selected)
• ans = 0 (no replacements yet)

Processing each student:

1. Student with rank 5 arrives (index 0):

   • Compare: 5 < 5? No
   • No replacement occurs
   • State: cur = 5, ans = 0

2. Student with rank 2 arrives (index 1):

   • Compare: 2 < 5? Yes!
   • Replacement occurs: student with rank 2 replaces rank 5
   • Update: cur = 2, ans = 1

3. Student with rank 6 arrives (index 2):

   • Compare: 6 < 2? No
   • No replacement (rank 6 is worse than rank 2)
   • State: cur = 2, ans = 1

4. Student with rank 1 arrives (index 3):

   • Compare: 1 < 2? Yes!
   • Replacement occurs: student with rank 1 replaces rank 2
   • Update: cur = 1, ans = 2

5. Student with rank 3 arrives (index 4):

   • Compare: 3 < 1? No
   • No replacement (rank 3 is worse than rank 1)
   • State: cur = 1, ans = 2

Final Result: Return ans = 2

The algorithm correctly identifies that 2 replacements occurred:

• When rank 2 replaced rank 5
• When rank 1 replaced rank 2

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the ranks list. The algorithm iterates through the list exactly once with a single for loop, performing constant-time operations (comparisons and assignments) for each element.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for the variables ans and cur, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Including the First Student in the Replacement Count

The Mistake: Some might incorrectly count the first student's arrival as a replacement:

# INCORRECT Implementation
def totalReplacements(self, ranks: List[int]) -> int:
    replacement_count = 0
    current_min = float('inf')  # Starting with infinity
  
    for rank_value in ranks:
        if rank_value < current_min:
            current_min = rank_value
            replacement_count += 1  # This counts the first student incorrectly!
  
    return replacement_count

This would return 2 for ranks = [3, 1, 4, 2] instead of 1, because it counts the initial selection of student with rank 3 as a replacement.

The Fix: Start with the first student as the initial selection (not counting it as a replacement):

# CORRECT Implementation
def totalReplacements(self, ranks: List[int]) -> int:
    replacement_count = 0
    current_min = ranks[0]  # First student is selected by default
  
    for rank_value in ranks[1:]:  # Start from second student
        if rank_value < current_min:
            current_min = rank_value
            replacement_count += 1
  
    return replacement_count

Pitfall 2: Using Wrong Comparison Operator

The Mistake: Using <= instead of < when checking for better rank:

# INCORRECT - counts equal ranks as replacements
if rank_value <= current_min:
    current_min = rank_value
    replacement_count += 1

This violates the "strictly better" requirement. A student with the same rank shouldn't trigger a replacement.

The Fix: Always use strict inequality (<) to ensure only strictly better ranks cause replacements.

Pitfall 3: Not Handling Edge Cases

The Mistake: Forgetting to handle arrays with only one element or empty arrays:

# Potential issues with edge cases
def totalReplacements(self, ranks: List[int]) -> int:
    current_min = ranks[0]  # IndexError if ranks is empty
    # ... rest of code

The Fix: Add proper edge case handling:

def totalReplacements(self, ranks: List[int]) -> int:
    if not ranks or len(ranks) == 1:
        return 0
  
    replacement_count = 0
    current_min = ranks[0]
  
    for rank_value in ranks[1:]:
        if rank_value < current_min:
            current_min = rank_value
            replacement_count += 1
  
    return replacement_count