Leetcode # 1051. Height Checker

Problem

https://leetcode.com/problems/height-checker

Solution: Merge Sort

Time Complexity: O(n * log(n)), n := len(heights)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def heightChecker(self, heights: List[int]) -> int:

    def merge_sort(array):
      if len(array) < 2: return array
      
      mid = (len(array) + 1) // 2

      left  = merge_sort(array[:mid])
      right = merge_sort(array[mid:])

      ret = []
      i = j = 0
      while i < len(left) or j < len(right):
        if i == len(left) or \
             (i < len(left) and j < len(right) and left[i] > right[j]):
          ret.append(right[j])
          j += 1
        else:
          ret.append(left[i])
          i += 1
      return ret

    expected = merge_sort(heights)

    return sum([(1 if heights[i] != expected[i] else 0) for i in range(len(heights))])

Last Updated on 2024/06/10 by A1go