This problem can be found on Leetcode.
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?
# 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.
# 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.
# 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.
# 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
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
n be the count of items in the
heights input list.
- Operation to sort
- Iteration over
sorted_heightszipped together as an iterator is O(n).
Total time complexity is O(2nlogn). The 2 is insignificant so it's simply O(n).
sorted_heightsis an O(n) operation.
Total space complexity is O(n).
assert height_checker([1, 1, 4, 3, 2]) == 2
assert height_checker([1, 2, 3]) == 0
assert height_checker([3, 1, 2]) == 3