# Height Checker (via Leetcode)

- April 12, 2020
- Key Terms: 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¶

```
# 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.

### Pseudocode¶

```
# 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¶

```
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¶

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

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

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