Height Checker

Problem

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line.

You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Constraints

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

Solution

The problem Height Checker can be solved by sorting given heights and counting the number of elements that have changed.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    int heightChecker(vector<int> &heights)
    {
        vector<int> expected = heights;
        sort(expected.begin(), expected.end());

        int count = 0;
        for (int i = 0; i < heights.size(); i++)
            if (heights[i] != expected[i])
                count += 1;

        return count;
    }
};