This problem statement is a part of Leetcode's Introduction to Data Structures Fun with Arrays-101. Under the sub-heading Conclusion.
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.
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
- 1 <= heights.length <= 100
- 1 <= heights[i] <= 100
There was one hint given. Sort the array and compare the two arrays. Hence, some steps followed.
- Using sorted sort the initial list. Remember, sorted returns a new sorted list.
- 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.
- 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
- Currently, the solution is correct but unoptimized. Time complexity is O(nlogn), space complexity is 0(n).
- Time complexity of sorted - 0(nlogn)
- The solution can be derived without using an extra array though. This would make the time complexity O(n), space complexity 0(1).
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.