# Height Checker
**Difficulty:** EASY
[External](https://leetcode.com/problems/height-checker)
Canonical: https://scaleengineer.com/dsa/problems/height-checker
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array
**Companies:** [Salesforce](https://scaleengineer.com/companies/salesforce)
---
## 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]`.

**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`

# Approaches
## Comparison Sort
This straightforward approach involves first determining the `expected` order of students. This is achieved by creating a copy of the `heights` array and sorting it in non-decreasing order. Once we have both the original `heights` array and the sorted `expected` array, we can iterate through them simultaneously and count the number of positions where the heights do not match.
**Time:** O(N log N), where N is the number of students. The dominant operation is sorting the array. Copying the array and the final comparison loop both take O(N) time, which is overshadowed by the sort. · **Space:** O(N), where N is the number of students. This space is required to store the copy of the `heights` array.
**Pros:** Easy to understand and implement.; The code is concise and relies on well-tested built-in functions.
**Cons:** Sub-optimal time complexity compared to other methods that can leverage the problem's constraints.; Requires extra space proportional to the input size (O(N)) to store the copied array.
### Explanation
The core idea is to generate the target sorted array and then perform a direct comparison. 

1.  **Create a Copy**: We first create an exact copy of the `heights` array. We cannot sort the original array in-place because we need it for the final comparison.
2.  **Sort**: We use a standard library function, like `Arrays.sort()`, to sort the copied array. This function typically implements an efficient comparison sort algorithm like Quicksort or Timsort, resulting in an O(N log N) time complexity.
3.  **Compare and Count**: We then loop through both the original `heights` array and the newly sorted `expected` array from the first to the last element. A counter is used to keep track of the number of indices `i` where `heights[i]` is not equal to `expected[i]`. This count is the final answer.

```java
import java.util.Arrays;

class Solution {
    public int heightChecker(int[] heights) {
        int n = heights.length;
        int[] expected = new int[n];
        // Create a copy of the heights array.
        System.arraycopy(heights, 0, expected, 0, n);
        
        // Sort the copied array to get the expected order.
        Arrays.sort(expected);
        
        int mismatchCount = 0;
        // Compare the original array with the sorted array.
        for (int i = 0; i < n; i++) {
            if (heights[i] != expected[i]) {
                mismatchCount++;
            }
        }
        
        return mismatchCount;
    }
}
```
### Algorithm
- Create a copy of the `heights` array, let's call it `expected`.
- Sort the `expected` array using a standard comparison-based sorting algorithm (e.g., `Arrays.sort()` in Java).
- Initialize a counter variable, `mismatchCount`, to zero.
- Iterate from `i = 0` to `heights.length - 1`.
- In each iteration, compare `heights[i]` with `expected[i]`.
- If `heights[i] != expected[i]`, increment `mismatchCount`.
- After the loop completes, return `mismatchCount`.

## Counting Sort
This approach leverages the specific constraints of the problem, namely that the heights are integers within a small, fixed range (1 to 100). Instead of a general-purpose comparison sort, we can use a counting sort-based method. We count the occurrences of each height and then reconstruct the sorted sequence to compare against the original array, leading to a more efficient solution.
**Time:** O(N + K), where N is the number of students and K is the range of heights. The first loop to populate the frequency array is O(N). The second loop also runs N times, and the inner `while` loop's pointer `currentHeight` traverses the range of K just once in total across all iterations. Thus, the total time is O(N + K). Since K is a constant (100), this simplifies to O(N). · **Space:** O(K), where K is the range of possible heights (101 in this case). Since K is a constant, the space complexity is O(1).
**Pros:** Optimal time complexity of O(N) for this problem.; Constant space complexity, as the frequency array's size is fixed and does not depend on the input size N.
**Cons:** The logic is slightly more complex than the comparison sort approach.; This method's efficiency is highly dependent on the constraint that the range of values is small. It would be inefficient for a large range of heights.
### Explanation
Because the range of heights is small and known, we can avoid an O(N log N) sort. 

1.  **Frequency Count**: We create an auxiliary array, `heightFreq`, of size 101. We iterate through the input `heights` array once, and for each height, we increment its corresponding index in `heightFreq`. For example, if we see a height of 5, we do `heightFreq[5]++`. After this step, `heightFreq[h]` will store the number of students with height `h`.
2.  **Simultaneous Traversal and Comparison**: We can determine the number of mismatches in a single pass. We iterate through the original `heights` array from left to right (index `i`). For each position, we determine what the *expected* height should be. We can find this by keeping a pointer, `currentHeight`, to the smallest height that is supposed to be in the line. We find the first non-zero entry in our `heightFreq` array; this is our `currentHeight`. We compare `heights[i]` with this `currentHeight`. If they don't match, we increment a counter. Then, we decrement the count for `currentHeight` in our frequency map and move to the next position `i+1` in the `heights` array. This way, we effectively compare the original array with the sorted version without explicitly creating the sorted array.

```java
class Solution {
    public int heightChecker(int[] heights) {
        // Heights are between 1 and 100.
        int[] heightFreq = new int[101];
        
        // Populate the frequency array.
        for (int height : heights) {
            heightFreq[height]++;
        }
        
        int mismatchCount = 0;
        int currentHeight = 1;
        
        // Iterate through the original heights array to compare with the expected order.
        for (int i = 0; i < heights.length; i++) {
            // Find the next height that should be in the sorted line.
            while (heightFreq[currentHeight] == 0) {
                currentHeight++;
            }
            
            // If the student at the current position doesn't have the expected height, it's a mismatch.
            if (heights[i] != currentHeight) {
                mismatchCount++;
            }
            
            // Decrement the frequency for the current expected height, as we've accounted for one student.
            heightFreq[currentHeight]--;
        }
        
        return mismatchCount;
    }
}
```
### Algorithm
- Create a frequency array, `heightFreq`, of size 101 (since heights are between 1 and 100) and initialize all its values to 0.
- Iterate through the input `heights` array. For each height `h`, increment the count at `heightFreq[h]`.
- Initialize a `mismatchCount` to 0 and a pointer `currentHeight` to 1.
- Iterate through the original `heights` array using an index `i` from 0 to `n-1`.
- Inside the loop, find the next valid expected height by advancing `currentHeight` as long as `heightFreq[currentHeight]` is 0.
- Compare the actual height `heights[i]` with the expected `currentHeight`. If they are different, increment `mismatchCount`.
- Decrement `heightFreq[currentHeight]` to signify that one student of this height has been placed in the expected line.
- Return `mismatchCount` after the loop.

# Solutions
### Java

```java
class Solution {
public
  int heightChecker(int[] heights) {
    int[] expected = heights.clone();
    Arrays.sort(expected);
    int ans = 0;
    for (int i = 0; i < heights.length; ++i) {
      if (heights[i] != expected[i]) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def heightChecker(self, heights: List[int]) -> int: expected = sorted(heights) return sum(a != b for a, b in zip(heights, expected))

```

### CPP

```cpp
class Solution {
public:
  int heightChecker(vector<int> &heights) {
    vector<int> expected = heights;
    sort(expected.begin(), expected.end());
    int ans = 0;
    for (int i = 0; i < heights.size(); ++i)
      ans += heights[i] != expected[i];
    return ans;
  }
};

```