DEV Community

loading...

Day-11 Height Checker

mridubhatnagar profile image Mridu Bhatnagar ・2 min read

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.

Discussion

pic
Editor guide
Collapse
lishagopi profile image
Lishagopi

Can you please explain me the function line...being the absolute python beginner...I can't understand the thing after self keyword.

Collapse
mridubhatnagar profile image
Mridu Bhatnagar Author

This structure is actually particular to Leetcode. After self the following things are happening:

  1. parameter named heights is being passed to the method.
  2. List[int] - This mean built-in object is List. And list contains integer elements.
  3. -> int - This means the method will return an integer.

In the python code that we normally write. We don't usually use this format. Hence, this might be appearing unusual. This is just another way of passing the parameters.

You can read more about a library named mypy in python. To find more examples.

Collapse
lishagopi profile image
Lishagopi

Thanks a lot...❤