aboutsummaryrefslogtreecommitdiff
path: root/height_checker.py
diff options
context:
space:
mode:
Diffstat (limited to 'height_checker.py')
-rw-r--r--height_checker.py42
1 files changed, 42 insertions, 0 deletions
diff --git a/height_checker.py b/height_checker.py
new file mode 100644
index 0000000..8443737
--- /dev/null
+++ b/height_checker.py
@@ -0,0 +1,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]))