Height Checker (via Leetcode)¶

Date published: 2020-04-12

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, sets

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

# 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

# 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

# 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

# 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

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

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

In [16]:

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

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

In [17]:

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

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