↓Skip to main content
  1. LeetCode/

LeetCode 1051: Height Checker

·1 min· ·
LeetCode Easy Array Sorting Counting-Sort Bubble-Sort
Wei Yi Chung
Author
Wei Yi Chung
Working at the contributing of open source, distributed systems, and data engineering.
Table of Contents

Meta Data
#

Difficulty: easy First Attempt: 2022-09-30

  • Submissions: Accepted (first try)

Approach
#

The expected order is the sorted array, so count the positions where the two differ. Heights are 1..100, so counting sort gives O(n + 100) (Bucket Sort).

My Solution
#

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

Complexity
#

Time O(n log n), space O(n).

Mistakes to Avoid
#

  • Build a sorted copy with sorted; do not sort the original in place.

Interview Explanation
#

The expected order is the sorted array, so I compare it position by position with the original and count differences, in O(n log n), or linear with counting sort.

Related

LeetCode 561: Array Partition
·1 min
LeetCode Easy Array Greedy Sorting Counting-Sort
LeetCode 561 note: sort and pair neighbors; each pair’s minimum is the element at an even index, so sum those
LeetCode 594: Longest Harmonious Subsequence
·1 min
LeetCode Easy Array Hash-Table Sliding-Window Sorting
LeetCode 594 note: subsequences need not be contiguous, so just count; for each x add the counts of x and x + 1
LeetCode 506: Relative Ranks
·1 min
LeetCode Easy Array Sorting Heap-Priority-Queue
LeetCode 506 note: sort indices by score descending, give medals to the top three and rank strings to the rest, writing back into the original positions
LeetCode 1030: Matrix Cells in Distance Order
·2 mins
LeetCode Easy Array Math Geometry Sorting
LeetCode 1030 note: list every coordinate and sort by Manhattan distance to the center; return coordinates, not distances
LeetCode 1005: Maximize Sum Of Array After K Negations
·1 min
LeetCode Easy Array Greedy Sorting
LeetCode 1005 note: negate the smallest value each time; once the smallest is positive, only the parity of the remaining count matters
LeetCode 977: Squares of a Sorted Array
·1 min
LeetCode Easy Array Two-Pointers Sorting
LeetCode 977 note: the largest squares are at the two ends, so compare the ends with two pointers and fill the result from the back