3616. Number of Student Replacements 🔒

MediumArraySimulation

Problem Description

You are given an integer array ranks where ranks[i] represents the rank of the ith student arriving in order. A lower number indicates a better rank.

Initially, the first student is selected by default.

A replacement occurs when a student with a strictly better rank arrives and replaces the current selection.

Return the total number of replacements made.

Explanation: You start by selecting the first student. As each new student arrives (in order given by the array), you check if their rank is strictly better (meaning their rank number is less) than the currently selected student's rank. If so, the selection is replaced and you count this as a replacement. Your task is to count how many such replacements happen in total as you process all the students.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

We want to track whenever a new student with a better (smaller number) rank arrives and takes the place of the current selection. By simply keeping track of the current best rank we have seen so far, we can compare each arriving student's rank to it. If a student's rank is less than the current selection, it means this is a new "replacement," and we update our selection to this student. This way, each replacement directly corresponds to finding a new minimum rank as we scan the list from left to right.

Solution Approach

We use a simple simulation approach. We keep a variable cur to track the rank of the currently selected student, initially set to ranks[0] since the first student is always selected at the beginning.

We also use a counter ans to track the number of replacements. We iterate through the array ranks. Each time we encounter a student with a strictly better rank (that is, ranks[i] < cur), we update cur to this new rank and increment our counter.

Here is how the algorithm works step-by-step:

Initialize cur = ranks[0] and ans = 0.
For each rank x in ranks, check if x < cur.
If the condition is true, set cur = x and increment ans by 1.
After going through all students, ans contains the total number of replacements made.

In code, it looks like this:

ans, cur = 0, ranks[0]
for x in ranks:
    if x < cur:
        cur = x
        ans += 1
return ans

This solution uses a single pass through the array and just a few variables, making it efficient in both time and space.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with the example ranks = [5, 3, 6, 2, 4, 1].

Step-by-step:

The first student (rank 5) is selected by default.
Next student arrives (rank 3): 3 < 5 ⇒ replacement occurs. Now, cur = 3, replacements = 1.
Next student arrives (rank 6): 6 < 3 is false, so no replacement.
Next student arrives (rank 2): 2 < 3 ⇒ replacement occurs. Now, cur = 2, replacements = 2.
Next (rank 4): 4 < 2 is false — no replacement.
Last (rank 1): 1 < 2 ⇒ replacement occurs. Now, cur = 1, replacements = 3.

So, the answer is 3 replacements.

This walk-through shows that, by always comparing the incoming student's rank to the current best, and replacing only when a strictly better rank is found, the algorithm efficiently counts the total replacements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def totalReplacements(self, ranks: List[int]) -> int:
5        ans = 0               # Counter for replacements
6        cur = ranks[0]        # Initialize with the first rank
7
8        for x in ranks:
9            # If a smaller rank is found, update cur and increment ans
10            if x < cur:
11                cur = x
12                ans += 1
13
14        return ans            # Return the total number of replacements
15

1class Solution {
2    public int totalReplacements(int[] ranks) {
3        int replacements = 0;               // Count of replacements made
4        int currentRank = ranks[0];         // Track the current minimum rank
5
6        // Iterate through each rank in the array
7        for (int rank : ranks) {
8            // If the current rank is less than the tracked minimum, update and count
9            if (rank < currentRank) {
10                currentRank = rank;         // Update the minimum rank seen so far
11                ++replacements;             // Increment the count of replacements
12            }
13        }
14
15        return replacements;                // Return the total replacements
16    }
17}
18

1class Solution {
2public:
3    // Function to count the total number of replacements
4    int totalReplacements(std::vector<int>& ranks) {
5        int replacements = 0;                    // To keep track of number of replacements
6        int currentMin = ranks[0];               // Initialize the minimum value with the first element
7
8        // Iterate through each element in the ranks vector
9        for (int rank : ranks) {
10            // If a new lower value is found, update currentMin and increment replacements
11            if (rank < currentMin) {
12                currentMin = rank;
13                ++replacements;
14            }
15        }
16        return replacements;                     // Return the total number of replacements
17    }
18};
19

1/**
2 * Calculates the number of replacements required when encountering
3 * a lower rank in the sequence.
4 * @param ranks - Array of rank numbers
5 * @returns Number of replacements
6 */
7function totalReplacements(ranks: number[]): number {
8    // Initialize the answer (replacement count) to 0
9    // Initialize current minimum rank to the first element
10    let ans = 0;
11    let cur = ranks[0];
12
13    // Iterate through each rank in the array
14    for (const rank of ranks) {
15        // If the current rank is lower than the minimum so far
16        if (rank < cur) {
17            // Update the minimum rank
18            cur = rank;
19            // Increment the replacement count
20            ans++;
21        }
22    }
23
24    // Return the total number of replacements
25    return ans;
26}
27

Time and Space Complexity

The time complexity is O(n), where n is the length of the ranks list, since the code iterates through the list once.

The space complexity is O(1), as only a fixed amount of extra space is used regardless of the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: