Problem 1051

Abstract / Summary

Count how many students are not standing in the correct non decreasing height order.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1051.py

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        return sum( h != e for h, e in zip(heights, sorted(heights)) )
3 lines | 146 bytes | submitted October 26, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 82% (800k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Counting Sort
  • Sorting
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a single method heightChecker. The method receives a list of integers representing heights and returns the count of positions where the current ordering differs from the sorted ordering. The solution is concise, leveraging Python’s built-in functions to achieve the required result in a single expression.

Key Steps

Sorting the Input

The first logical operation is the creation of a sorted version of the input list.

sorted_heights = sorted(heights)

sorted returns a new list arranged in non-decreasing order. This step establishes the reference ordering against which the original list will be compared.

Pairwise Comparison

The method then pairs each element of the original list with the corresponding element of the sorted list using zip.

pairs = zip(heights, sorted_heights)

Each pair (h, e) consists of the height at a particular index in the original list (h) and the height that should appear at that index in a correctly ordered list (e).

Detecting Mismatches

For every pair, a boolean expression evaluates whether the two values differ.

mismatch = h != e

In Python, True evaluates to 1 and False to 0. This property enables the direct accumulation of mismatches.

Summation of Mismatches

The generator expression that yields the boolean results is passed directly to sum, which aggregates the total number of mismatched positions.

result = sum(h != e for h, e in zip(heights, sorted(heights)))

The final integer returned by the method represents the number of students standing in the wrong position.

Edge Cases Handled

When the input list is empty, sorted(heights) also yields an empty list. zip produces no pairs, and the generator expression yields no values, causing sum to return 0. This correctly indicates that no mismatches exist.

If the list contains a single element, the sorted version is identical to the original. The comparison h != e evaluates to False, and the sum remains 0, reflecting the absence of any discrepancy.

For lists that are already sorted, every comparison yields False, and the method returns 0. Conversely, for a list sorted in reverse order, each position differs from the sorted reference, and the sum equals the length of the list, accurately counting all mismatches.

When duplicate heights appear, the sorting process preserves the relative order of equal elements as defined by the stable sorting algorithm. The pairwise comparison still correctly identifies positions where a duplicate value is out of place relative to the stable sorted order.

Performance Optimizations

The implementation benefits from several built-in efficiencies. The sorted function employs Timsort, a hybrid stable sorting algorithm optimized for real-world data patterns, delivering fast sorting without additional code overhead. By using a generator expression inside sum, the code avoids constructing an intermediate list of boolean values, thereby reducing memory pressure and enabling lazy evaluation. The direct use of boolean-to-integer conversion eliminates the need for explicit conditional counting logic, streamlining the computation into a single pass over the zipped pairs. These choices collectively produce a compact and efficient solution.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a row of children standing in line, but they are all mixed up and not in order of how tall they are. This code first takes that line and makes a perfect, tidy copy where all the children are standing exactly from shortest to tallest. Then it looks at the original messy line and walks down it, comparing each child to the child standing in the same spot in the tidy copy. Every time it finds a child who is not in the spot where they belong, it marks them down. By the end, it counts up all the spots that had the wrong person in them so that you know how many children were standing in the wrong place.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 8.44 | σ = 1.03

Complexity Analysis

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go TS
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
Garvit244 Python
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
shreymehul C#
suxrobGM C#
varunu28 Java
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
Garvit244 Python
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
shreymehul C#
suxrobGM C#
varunu28 Java
33 links | 20 authors | 9 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

1 easy 5 medium
7 solutions   October 26, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality