Height Checker

Problem Statement

In an attempt to organize an annual school photograph, students are instructed to line up in a single file where their heights are ordered in a non-decreasing sequence. The desired order of students by height is conveyed through an integer array expected, where expected[i] refers to the height expected for the i-th student in the lineup.

However, there remains a complication. Students are initially standing in an order represented by another integer array, heights, where heights[i] corresponds to the actual height of the i-th student as they currently stand.

The task at hand is to determine how many students are standing out of the expected order. Specifically, the challenge is to return the number of indices i for which the height of the student at heights[i] does not match the height at expected[i].

This problem entails a direct comparison between the given ordering of heights and a sorted version of the same array to identify mismatches, thereby pinpointing students who are out of the desired sequential order.

Examples

Example 1

Input:

heights = [1,1,4,2,1,3]

Output:

3

Explanation:

heights: [1,1,4,2,1,3]
expected: [1,1,1,2,3,4]
Indices 2, 4, and 5 do not match.

Example 2

Input:

heights = [5,1,2,3,4]

Output:

5

Explanation:

heights: [5,1,2,3,4]
expected: [1,2,3,4,5]
All indices do not match.

Example 3

Input:

heights = [1,2,3,4,5]

Output:

0

Explanation:

heights: [1,2,3,4,5]
expected: [1,2,3,4,5]
All indices match.

Constraints

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

Approach and Intuition

To solve the problem effectively:

1. Begin by sorting the heights array to generate the expected array which is the correct non-decreasing order of student heights.
2. Initialize a counter to zero. This will be used to keep track of indices where discrepancies occur.
3. Compare the sorted heights array (now equivalent to expected) with the original heights array using a loop:
   • For each index, check if the value in the sorted array differs from the value in the original array.
   • If they do differ, increment the counter by one.
4. Return the total count of these discrepancies, which represents the number of students out of place.

The essence of this approach is leveraging the ability to sort and directly compare arrays to find element-wise mismatches. The constraints are manageable, allowing efficient execution of sorting operations and comparisons within the given limits. This method ensures each misplacement is counted accurately, culminating in the total number of students who need to adjust their position in line to fulfill the expected order.

Solutions

class Solution {
    // Function to sort using a specific digit
    void sortOnDigit(vector<int>& nums, int digitFactor) {
        vector<vector<int>> storage(10, vector<int>());
        for (int& number : nums) {
            int digit = abs(number) / digitFactor % 10;
            storage[digit].push_back(number);
        }
    
        int position = 0;
        for (int index = 0; index < 10; ++index) {
            for (int& item : storage[index]) {
                nums[position++] = item;
            }
        }
    }
    
    // Function to perform radix sort
    void performRadixSort(vector<int>& nums) {
        int maxVal = nums[0];
        for (int& number : nums) {
            maxVal = max(abs(number), maxVal);
        }
        int totalDigits = 0;
        while (maxVal > 0) {
            totalDigits++;
            maxVal /= 10;
        }
    
        int currentPlace = 1;
        for (int digit = 0; digit < totalDigits; ++digit) {
            sortOnDigit(nums, currentPlace);
            currentPlace *= 10;
        }
    }
    
public:
    int heightChecker(vector<int>& heights) {
        vector<int> expected = heights;
        performRadixSort(expected);
    
        int mismatches = 0;
        for (size_t i = 0; i < expected.size(); ++i) {
            if (heights[i] != expected[i]) {
                mismatches++;
            }
        }
        return mismatches;
    }
};