Day-11 Height Checker

This problem statement is a part of Leetcode's Introduction to Data Structures Fun with Arrays-101. Under the sub-heading Conclusion.

Problem Statement

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.

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

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

Constraints:

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

There was one hint given. Sort the array and compare the two arrays. Hence, some steps followed.

Solution Approach

1. Using sorted sort the initial list. Remember, sorted returns a new sorted list.
2. Compare the new sorted list with the original list. Now, compare the value of each element at the same index in the original list and in the new sorted list.
3. On indexes where the values are different. Increment the counter by 1.

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

Learnings

1. Currently, the solution is correct but unoptimized. Time complexity is O(nlogn), space complexity is 0(n).
2. Time complexity of sorted - 0(nlogn)

Pending TODO

1. The solution can be derived without using an extra array though. This would make the time complexity O(n), space complexity 0(1).

NOTE

I am an absolute beginner in data structures and algorithms. Practicing these topic wise. Hence, there is also a possibility that there is some concept I am unaware of at the moment that might help in the optimization.