In this article, we have solved the Height Checker Problem with two different approaches. This involve the concept of using Counting Sort efficiently.

Problem Statement

A school is attempting to get a yearly photo of every kid.

The kids are instructed to line up in a straight line, non-decreasing in height, as they stand.

Let expected[i], the predicted height of the ith student in line, be used to express this ordering as an integer array.

You are given an integer array heights that represents the students' current standing order.
The ith student in line's height is represented by each heights[i] (0-indexed).

The number of indices where heights[i]!= expected[i] is returned.

Example 1:
Input: heights = [7,8,7,9,5,4]
Output: 5
Explanation: heights: [7,8,7,9,5,4]
expected: [4,5,7,7,8,9]
Indices 0, 1, 3, 4 and 5 do not match.

Example 2:
Input: heights = [6,6,7,8,9]
Output: 0
Explanation:
heights: [6,6,7,8,9]
expected: [6,6,7,8,9]
All indices match.

Approach I - IN-BUILT SORTING

LOGIC:
We sort the array to get ourselves the expected array and then compare it with he heights array to get the differences in indexes.

Algorithm:

1. Made a duplicate of heights which we will call the expected array.
2. Sort the expected array
3. Compare heights and expected array to get the differences in indexes
4. if heights[i]!= expected[i]
5. count++

Implemented Code:

class Solution {
    public int heightChecker(int[] heights) {

        int []expected = new int[heights.length];

        for(int i=0;i<heights.length;i++){
            expected[i]=heights[i];
        }

        Arrays.sort(expected);

        int count=0;

        for(int i=0;i<heights.length;i++){
            if(heights[i] != expected[i]) count++;
        }

        return count;
        
    }
}

Explanation:
We make a new array called expected[] by looping in the heights array and copying the values in expected[] simultaneously. Expected array is then sort as asked in the problem. To get the point of difference between the two array we compare their indices.
If same then go to next index if not then count = count+1 where count is initially 0.

Example :
heights = [1,2,3,4,2]
On making an expected array and sorting it.
expected = [1,2,2,3,4]
Next we compare the two arrays by looping and checking at each index whether they are equal or not.
at indices - 2,3,4 we find dissimilarity.
So, output - 3

Complexity
Time complexity:O(nlogn)
Reason : Reason : Arrays.sort() is an inbuilt function has a time complexity of O(nlogn).
As for the linear search time complexity is O(n).
Hence total time complexity is O(nlog⁡n).

Space complexity:O(n)
Reason : Extra space has been used to form the expected array. Hence space complexity is O(n).

Approach II - COUNTING SORTING

Counting Sort
Counting sort is an efficient, stable sorting algorithm that operates by counting the number of occurrences of each distinct element in the input array, and then using that information to place the elements in their correct positions in the output array.

This algorithm is particularly well suited for sorting arrays with a small number of distinct elements, and has a time complexity of O(n+k) where n is the number of elements in the input array and k is the number of distinct elements.

Method - Instead of using the inbuilt method to sort array, we can implement count sort.

Implemented Code:

class Solution {
public int heightChecker(int[] heights) {
int[] count = new int[101];
for (int i = 0; i < heights.length; i++) {
count[heights[i]]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i-1];
}
int result = 0;
for (int i = heights.length-1; i >= 0; i--) {
count[heights[i]]--; // this is the correct location for heights[i] based on counting sort
if (heights[count[heights[i]]] != heights[i])
result++;
}
return result;
}
}

Explanation:
We sort the heights array using count sort by getting the frequency of height and storing it in a count array. After sorting the count array it become sour expected array. Next we compare the heights and expected array and raise the counter by one if the indices do not match. Finally we return the counter as answer.

Example :
heights = [1,2,3,4,2]
We make a count array that keeps tab of the frequency of values in heights array.
count = [0,1,2,1,4]
Next we sort this count array by decreasing the frequency since they are now arranged in ascending order. this will be our expected array.
expected = [1,2,2,3,4]
Next we compare the two arrays by looping and checking at each index whether they are equal or not.
at indices - 2,3,4 we find dissimilarity.
So, output - 3

Complexity
Time complexity:O(n)
Reason : Counting Sort has a time complexity of O(n) and linear search applied also has a time complexity of O(n). Hence total time complexity is O(n).

Space complexity:O(n)
Reason : Extra space has been used to form count array. Hence space complexity is O(n).

Conclusion

With this article at OpenGenus, we have solved the following Height Checker problem using sorting and count sorting algorithm.