LeetCode Entry

1051. Height Checker

10.06.2024 easy 2024 kotlin rust

Count unsorted elements in array

1051. Height Checker easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/635

Problem TLDR

Count unsorted elements in array #easy

Intuition

We can use bucket sort to do this in O(n).

Approach

Let’s just use a simple sort to save the effort.

Complexity

• Time complexity: \(O(nlog(n))\)

• Space complexity: \(O(n)\)

Code

    fun heightChecker(heights: IntArray) = heights
        .toList().sorted().withIndex()
        .count { (i, h) -> h != heights[i] }

    pub fn height_checker(heights: Vec<i32>) -> i32 {
        let mut s = heights.clone(); s.sort_unstable();
        (0..s.len()).map(|i| (s[i] != heights[i]) as i32).sum()
    }