Leetcode 1051. Height Checker

Problem Explanation and Walk-through

The problem is asking for us to find the minimum number of students that would need to move in order for all students to be standing in non-decreasing order of height. In other words, if the students were standing in a sorted order, how many students are standing out of place.

If we refer to the input array, [1,1,4,2,1,3], the sorted array would look like [1,1,1,2,3,4]. The first two students are standing in the correct positions as their height is 1. The third student however, has a height of 4, and is standing in the wrong place as there is a student with height 2 and 3 who should be before him. Similarly, the forth student with height 2, and the sixth student with a height of 1 also is standing in the wrong place. So, 3 students in total are standing in the wrong positions.

To count the score efficiently, we can make use of frequency table, where the index is the height and the value is the count of that height. Then, we go through the list again. If the student is in the wrong place, then increase the score by one. This approach is a variation of counting sort.

Python Solution

1
2python
3class Solution:
4    def heightChecker(self, heights) -> int:
5        # initialise frequency list
6        count = [0]*101
7        ans = 0
8        currentHeight = 1
9
10        # count frequency of each height
11        for height in heights:
12            count[height] += 1
13
14        # check if each student is in the correct position
15        for height in heights:
16            while count[currentHeight] == 0:
17                currentHeight += 1
18            if height != currentHeight:
19                ans += 1
20            count[currentHeight] -= 1
21
22        return ans

JAVA Solution

1
2java
3class Solution {
4    public int heightChecker(int[] heights) {
5        int[] frequency = new int[101];
6        int ans = 0, currentHeight = 1;
7
8        for (int height : heights)
9            frequency[height]++;
10
11        for (int height : heights) {
12            while (frequency[currentHeight] == 0)
13                currentHeight++;
14            if (height != currentHeight)
15                ans++;
16            frequency[currentHeight]--;
17        }
18
19        return ans;
20    }
21}

Javascript Solution

1
2javascript
3var heightChecker = function(heights) {
4    let count = new Array(101).fill(0),
5        ans = 0,
6        currentHeight = 1;
7
8    for (let height of heights)
9        count[height]++;
10        
11    for (let height of heights){
12        while(count[currentHeight] === 0)
13            currentHeight++;
14        if(height !== currentHeight)
15            ans++;
16        count[currentHeight]--;
17    }
18        
19    return ans;
20};

C++ Solution

1
2c++
3class Solution {
4public:
5    int heightChecker(vector<int>& heights) {
6        vector<int> count(101);
7        int ans = 0, currentHeight = 1;
8
9        for (int height : heights)
10            count[height]++;
11
12        for (int height : heights) {
13            while (count[currentHeight] == 0)
14                currentHeight++;
15            if (height != currentHeight)
16                ans++;
17            count[currentHeight]--;
18        }
19
20        return ans;
21    }
22};

C# Solution

1
2csharp
3public class Solution 
4{
5    public int HeightChecker(int[] heights) 
6    {
7        int[] count = new int[101];
8        int currentHeight = 1, ans = 0;
9
10        foreach (int height in heights)
11            count[height]++;
12        
13        foreach (int height in heights)
14        {
15            while (count[currentHeight] == 0)
16                currentHeight++;
17            if (height != currentHeight)
18                ans++;
19            count[currentHeight]--;
20        }
21    
22        return ans;
23    }
24}

In all these solutions, we initialize a frequency count array whose indexes are the possible heights of students and the values are their occurrence in the heights array. For every height, we increment the corresponding value in the count array by 1.

After that, we traverse through the heights array once again and compare each height with an incrementing variable called currentHeight. We also ensure that this currentHeight is not pointing to a non-existing height (with frequency as 0). If currentHeight is not equal to the student's height, it implies the student is standing in the wrong place, therefore we increment our answer variable. After this, we decrement the current count by 1 and update the pointer if there are no more students of currentHeight left.

By iterating the heights array only twice, and not sorting it, we can solve this problem much quicker resulting in a time complexity of O(n), where n is the size of the array.

This approach consolidates the basic concepts of array counting and index correspondence, which are important algorithmic skills for higher-level problem-solving.

A key part of this solution, is understanding that the order of the students does not matter, because the problem asks for the count of students out of their right place and not their order. This allows us to use counting sort method which can't be used if actual elements’ order is important.

This is a lesson that in the right circumstances and with a proper understanding of underlying data, even seemingly complex problems can be solved efficiently using conceptually simple methods.