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

Difficulty: introductory

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 # Counter
        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:
        # my method 2: counting sort and compare difference O(n+r): r number of max_value O(n); only works for small numbers sorting
        
        maxVal = max(heights)
        
        # create frequency table for each digit from 0 to maxVal
        freq = [0] * (maxVal + 1)
        # get freq for all index
        for num in heights:
            freq[num] += 1
        # acc index by num[i] += num[i-1]
        for i in range(1,len(freq)):
            freq[i] += freq[i-1]
            
        # loop heights, find its freq and index back in places
        places = [0] * len(heights)
        for num in heights:
            # num has freq[num] th in ranking, but -1 to be index
            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:
        # my method 1: sort and compare different elements O(NlogN) O(n)
        heightsSorted = sorted(heights)
        
        # compare and acc different index
        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:
        return sum([1 if sorted(heights)[i] != heights[i] else 0 for i in range(len(heights))])

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