> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-06-2022-1051.-height-checker.md).

# 06/06/2022 1051. Height Checker

Method 1: make a copy of the heights array. Then sort it and compare it to the original array to see how many difference they have.

Time O(nlogn)

Space O(n)

Method 2: using bucketsort. Create an array map with the size 101. Scan the array to get the frequency of each element in the map. Initate two vairables, one is for the counter, one is for current height.  While the frequency of currentHeight is 0, we increment currentHeight. Then we check if currentHeight is equal to the heights\[i]. if not, we increment counter.

Time o(n)

Space O(n)