Students are asked to stand in non-decreasing order of heights for an annual photo.
Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.
Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.
 
Example 1:
Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: 
Current array : [1,1,4,2,1,3]
Target array  : [1,1,1,2,3,4]
On index 2 (0-based) we have 4 vs 1 so we have to move this student.
On index 4 (0-based) we have 1 vs 3 so we have to move this student.
On index 5 (0-based) we have 3 vs 4 so we have to move this student.

Example 2:
Input: heights = [5,1,2,3,4]
Output: 5

Example 3:
Input: heights = [1,2,3,4,5]
Output: 0

 
Constraints:

1 <= heights.length <= 100
1 <= heights[i] <= 100

Source: leetcode | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        

Solutions:
class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		max_val = max(heights)
		freq = [0] * (max_val + 1)
		for num in heights:
			freq[num] += 1
		for num in range(1, len(freq)):
			freq[num] += freq[num - 1]
		places = [0] * len(heights)
		for num in heights:
			places[freq[num] - 1] = num
			freq[num] -= 1
		return sum((a != b for (a, b) in zip(places, heights)))


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		count = 0
		b = sorted(heights)
		for x in range(len(heights)):
			if heights[x] != b[x]:
				count += 1
		return count


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		heights_sort = sorted(heights)
		cnt = 0
		i = 0
		while i < len(heights):
			if heights[i] != heights_sort[i]:
				cnt += 1
			i += 1
		return cnt


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		count = 0
		for (idx, num) in enumerate(sorted(heights)):
			if heights[idx] != num:
				count += 1
		return count


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		maxVal = max(heights)
		freq = [0] * (maxVal + 1)
		for num in heights:
			freq[num] += 1
		for i in range(1, len(freq)):
			freq[i] += freq[i - 1]
		places = [0] * len(heights)
		for num in heights:
			places[freq[num] - 1] = num
			freq[num] -= 1
		ans = 0
		for i in range(len(heights)):
			if heights[i] != places[i]:
				ans += 1
		return ans


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		sortedHeights = sorted(heights)
		return sum([1 if sortedHeights[i] != heights[i] else 0 for i in range(len(heights))])


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		heightsSorted = sorted(heights)
		ans = 0
		for i in range(len(heights)):
			if heights[i] != heightsSorted[i]:
				ans += 1
		return ans


class Solution:

	def heightChecker(self, h: List[int]) -> int:
		return sum([x != y for (x, y) in zip(h, sorted(h))])


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		diff = [sorted(heights)[k] - heights[k] for k in range(len(heights))]
		move = 0
		for x in diff:
			if x != 0:
				move = move + 1
		return move


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		hs = heights[:]
		for e in range(len(hs) - 1, 0, -1):
			(mx, ix) = (float('-inf'), -1)
			for (i, h) in enumerate(hs[:e + 1]):
				if h >= mx:
					(ix, mx) = (i, h)
			(hs[e], hs[ix]) = (hs[ix], hs[e])
		return sum((a != b for (a, b) in zip(hs, heights)))


class Solution:

	def heightChecker(self, heights: List[int]) -> int:
		sorted_arry = []
		for x in heights:
			sorted_arry.append(x)
		for i in range(len(sorted_arry)):
			curr_ele = sorted_arry[i]
			j = i + 1
			curr_index = i
			while j < len(sorted_arry):
				if curr_ele > sorted_arry[j]:
					curr_ele = sorted_arry[j]
					curr_index = j
				j = j + 1
			sorted_arry[curr_index] = sorted_arry[i]
			sorted_arry[i] = curr_ele
		change_count = 0
		for i in range(len(heights)):
			if heights[i] != sorted_arry[i]:
				change_count = change_count + 1
		return change_count