Python Beginner Algorithms Tutorial

# Height Checker (via Leetcode)

This problem can be found on Leetcode.

Problem setup:

Students are presented in a line in a random height order. We want students to stand in an increasing order of height for an annual photo. How many students need to change positions?

### Test Cases¶

In :
# assert height_checker([1, 1, 4, 3, 2]) == 2


The correct order of students should be [1, 1, 2, 3, 4]. To reach this result from the original order of students, the students originally at index 2 and index 4 must be moved. That is 2 students.

In :
# assert height_checker([1, 2, 3]) == 0


This is the correct order of students in increasing height order so 0 students need to be moved.

In :
# assert height_checker([3, 1, 2]) == 3


Students in increasing height order would be [1, 2, 3]. None of the original students are in the corrent position for increasing height order. There's 3 total students and all 3 must be moved.

### Pseudocode¶

In :
# create a function that takes in an input list of heights

# create a new list of the heights sorted in increasing order

# assign variable positions_changed to 0

# iterate over original heights list and sorted_heights at the same time
# compare height value in original heights list and sorted_heights...
# if the values are unequal
# a student is in the wrong position...
# increase positions_changed by 1

# return positions_changed


### Code Solution¶

In :
 def height_checker(heights):
sorted_heights = sorted(heights)

positions_changed = 0
for position_old, position_new in zip(heights, sorted_heights):
if position_old != position_new:
positions_changed += 1

return positions_changed


### Complexity¶

Let n be the count of items in the heights input list.

Time complexity:

• Operation to sort heights is O(nlogn).
• Iteration over heights and sorted_heights zipped together as an iterator is O(n).

Total time complexity is O(2nlogn). The 2 is insignificant so it's simply O(n).

Space complexity:

• sorted_heights is an O(n) operation.

Total space complexity is O(n).

### Verify Solution with Test Cases¶

In :
assert height_checker([1, 1, 4, 3, 2]) == 2

In :
assert height_checker([1, 2, 3]) == 0

In :
assert height_checker([3, 1, 2]) == 3