1051. Height Checker

Sort

T: O(nlogn)

S: O(n)

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

Bucket sort

T: O(max), see if max is too large or not

S: O(max)

class Solution {
    public int heightChecker(int[] heights) {
        int max = 0;
        for (int h : heights) {
            max = Math.max(max, h);
        }
        int[] bucket = new int[max+1];
        for (int h : heights) {
            bucket[h]++;
        }

        int result = 0;
        int bucketIdx = 0;
        for (int h : heights) {
            while (bucket[bucketIdx] == 0) {
                bucketIdx++;
            }
            if (bucketIdx != h) { // bucketIdx is the actual height
                result++;
            }
            bucket[bucketIdx]--;
        }
        return result;
    }
}