Solution 1 - Sort and Compare

Count indices where heights differ from sorted copy.

TimeComplexity: O(n \log n)

SpaceComplexity: O(n)

""" 1051.1 - Height Checker - Solution 1 - Sort and Compare """

from typing import List

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        expected = sorted(heights)
        return sum(1 for a, b in zip(heights, expected) if a != b)

package main

import "sort"

func heightChecker(heights []int) int {
	expected := append([]int(nil), heights...)
	sort.Ints(expected)
	c := 0
	for i := range heights {
		if heights[i] != expected[i] { c++ }
	}
	return c
}

func main() {}

fn height_checker(mut heights: Vec<i32>) -> i32 {
	let mut expected = heights.clone();
	expected.sort();
	let mut c = 0;
	for i in 0..heights.len() {
		if heights[i] != expected[i] { c += 1; }
	}
	c
}
fn main() {}

1051 - Height Checker

Solution 1 - Sort and Compare