aboutsummaryrefslogtreecommitdiff
path: root/height_checker.py
blob: 8443737e5ed1d9b7b4efb5c949004395324537ee (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 1051. Height Checker

"""
a school is trying to take an annual photo of all the students. the students
are asked to stand in a single file line in non decreasing order by height.
let this ordering be represented by the integer array 'expected' where
'expected[i]' is the expected height of the i'th student in line. you are
given an integer array 'heights' representing the current order that the
students are standing in. each 'heights[i]' is the height of the i'th student
in line. return the number of indices where 'heights[i] != expected[i]'
"""


class Solution(object):
    def heightChecker(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        max_nr = max(heights)
        cnt = [0] * (max_nr + 1)
        for n in heights:
            cnt[n] += 1
        sum_cnt = [0] * (max_nr + 1)
        for i, n in enumerate(cnt[1:], start=1):
            sum_cnt[i] = n + sum_cnt[i - 1]
        output = [0] * len(heights)
        for i in range(len(heights) - 1, -1, -1):
            output[sum_cnt[heights[i]] - 1] = heights[i]
            sum_cnt[heights[i]] -= 1
        ans = 0
        for i, n in enumerate(heights):
            if n != output[i]:
                ans += 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.heightChecker(heights=[1, 1, 4, 2, 1, 3]))
    print(obj.heightChecker(heights=[5, 1, 2, 3, 4]))
    print(obj.heightChecker(heights=[1, 2, 3, 4, 5]))