1051. Height Checker

Description

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 (0-indexed).

Return the number of indices where heights[i] != expected[i].

Example 1:

• Input: heights = [1,1,4,2,1,3]
• Output: 3
• Explanation:
  _heights : [1,1,4,2,1,3]
  expected: [1,1,1,2,3,4]
  Indices 2, 4, and 5 do not match.

Example 2:

• Input: heights = [5,1,2,3,4]
• Output: 5
• Explanation:
  _heights : [5,1,2,3,4]
  expected: [1,2,3,4,5]
  All indices do not match.

Example 3:

• Input: heights = [1,2,3,4,5]
• Output: 0
• Explanation:
  _heights : [1,2,3,4,5]
  expected: [1,2,3,4,5]
  All indices match.

Constraints:

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

💡 Hint 1:
Build the correct order of heights by sorting another array, then compare the two arrays.

Submitted Code

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        countdown = len(heights)
        expected = sorted(heights)

        for i in range(len(heights)):
            if heights[i] == expected[i]:
                countdown -= 1
        
        return countdown

Runtime: 0 ms | Beats 100.00%
Memory: 17.64 MB | Beats 78.49%

sorted()로 정렬된 리스트를 하나 더 만든 후 두 리스트를 비교하면 된다.

Other Solutions

1st

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        return sum(h1 != h2 for h1, h2 in zip(heights, sorted(heights)))

time complexity: 𝑂(𝑛log𝑛)
space complexity: 𝑂(𝑛)

조금 더 파이썬스러운 코드도 참고했다.