Problem Description

The Height Checker problem gives you an array of integers called heights, where each integer represents the height of a student standing in a line. Your task is to determine how many students are not standing in the position they would be if the students were ordered in non-decreasing order of height.

In other words, you need to compare the current arrangement (heights) to what the arrangement would look like if the array was sorted. For each position, if the student's height does not match the height at the same position in the sorted array, you count it as a mismatch. Return the number of mismatches.

• All heights are positive integers.
• The input array heights can have up to 100 elements.
• Each student is unique by position, so do not remove or swap elements—just count mismatches.

Thought Process

The core idea is to compare the current order of students with the order they would have if sorted by height. The brute-force way would be to repeatedly find the minimum height and compare, but that's inefficient. Instead, if we sort the array and compare each position, we can quickly identify mismatches.

Think of this as lining up students and then looking at a "perfect" lineup (sorted by height) to see who is out of place. For each student, if their height does not match the sorted lineup at their position, they are counted as out of place.

This approach avoids unnecessary complexity and leverages the efficiency of built-in sorting and simple iteration.

Solution Approach

We can solve this problem efficiently by following these steps:

1. Copy and Sort: Create a sorted copy of the heights array. This represents the "ideal" lineup.
2. Compare: Iterate through both arrays (original and sorted) simultaneously.
3. Count Mismatches: For each position, compare the height in the original array to the height in the sorted array. If they differ, increment a counter.
4. Return the Count: After the loop, return the total number of mismatches.

This method is efficient because sorting is O(n \log n) and comparing is O(n). No extra data structures are needed beyond the sorted copy.

Example Walkthrough

Let's walk through an example:

• Input: heights = [1, 1, 4, 2, 1, 3]
• Step 1: Sorted copy: [1, 1, 1, 2, 3, 4]
• Step 2: Compare each index:
  • Index 0: 1 vs 1 → match
  • Index 1: 1 vs 1 → match
  • Index 2: 4 vs 1 → mismatch
  • Index 3: 2 vs 2 → match
  • Index 4: 1 vs 3 → mismatch
  • Index 5: 3 vs 4 → mismatch
• Total mismatches: 3 (indices 2, 4, 5)

Output: 3

Time and Space Complexity

Brute-force approach: If you tried to compare each element to every other to find its correct position, you could hit O(n^2) time, which is inefficient.

Optimized approach (sorting and comparing):

• Time Complexity: Sorting the array takes O(n \log n). Comparing each element is O(n). So overall, the time complexity is O(n \log n).
• Space Complexity: We use O(n) extra space for the sorted copy of the array.

Summary

The Height Checker problem is elegantly solved by sorting the input array and comparing it to the original. This approach is efficient, easy to implement, and avoids unnecessary complexity. The key insight is that the number of mismatches between the original and sorted arrays directly gives the answer, making the solution both simple and powerful for this type of problem.

Code Implementation

class Solution:
    def heightChecker(self, heights):
        expected = sorted(heights)
        count = 0
        for h1, h2 in zip(heights, expected):
            if h1 != h2:
                count += 1
        return count
      

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;
            }
        }
        return count;
    }
};
      

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

var heightChecker = function(heights) {
    let expected = [...heights].sort((a, b) => a - b);
    let count = 0;
    for (let i = 0; i < heights.length; i++) {
        if (heights[i] !== expected[i]) {
            count++;
        }
    }
    return count;
};