Out Of Place Count
Problem
Students stand in a line, each described by a height. They were supposed to be lined up from shortest to tallest. Count the positions holding a student whose height differs from the height that should be standing there. Equal heights are interchangeable, so a position holding the right height is never counted.
Examples
Input: heights = [1, 1, 4, 2, 1, 3]
Output: 3
Why: the correct line is 1 1 1 2 3 4, and three positions disagreeInput: heights = [5, 4, 3, 2, 1]
Output: 4
Why: only the middle student happens to already stand correctlyInput: heights = [1, 2, 3]
Output: 0
Why: edge case, an already correct line has nothing out of placeHints
0 / 3
The question compares the line you were given against a line you have to work out first, so produce that second line before counting anything.
The target line is simply the same heights arranged from shortest to tallest, so a sorted copy of the input is exactly what you need to compare against.
Sort a copy of the heights, then walk both lines together position by position and count the positions where the two heights differ. Compare the copy, never the original, or the comparison destroys the very thing being checked.
Solution
The target line is just the input sorted, so the whole task is producing that copy and comparing position by position. Sorting a copy rather than the input itself matters: sorting in place would overwrite the line being judged and the count would always come out as zero. Comparing heights rather than students is enough, because two students of equal height are interchangeable and a position holding the right height is correct whoever is standing there. Time is O(n log n) for the sort, and space is O(n) for the copy.
def count_out_of_place(heights):
target = sorted(heights) # a COPY, so the original line survives
mismatches = 0
for standing, expected in zip(heights, target):
if standing != expected: # this position holds the wrong height
mismatches += 1
return mismatches
print(count_out_of_place([1, 1, 4, 2, 1, 3])) # -> 3
print(count_out_of_place([5, 4, 3, 2, 1])) # -> 4
print(count_out_of_place([1, 2, 3])) # -> 0Stuck on the idea rather than the code? Sorting Basics covers it.