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 [10]:
# 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 [11]:
# 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 [12]:
# 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 [13]:
# 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 [14]:
 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 [15]:
assert height_checker([1, 1, 4, 3, 2]) == 2
In [16]:
assert height_checker([1, 2, 3]) == 0
In [17]:
assert height_checker([3, 1, 2]) == 3