Skip to main content
Talentd

Height Checker - Solution & Explanation

EasyArraySortingCounting Sort16 min readAsked at: Amazon, Microsoft, IBM +3
Practice this problem

Problem Statement

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 ith 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 ith 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

Approach Overview

Problem Overview: You receive an array heights representing student heights in the order they currently stand. Students should be arranged in non‑decreasing order. The task is to count how many indices contain a height different from the height that would appear in the correctly sorted order.

Approach 1: Sorting and Comparison (O(n log n) time, O(n) space)

The most direct solution is to compute what the correct ordering should look like. Create a copy of the heights array and sort it using a standard sorting algorithm. Then iterate through both arrays simultaneously and count how many indices differ. Each mismatch represents a student who is not in the position they would occupy in the sorted lineup. This approach is simple, easy to implement in any language, and works well because the problem only requires comparison against the sorted order rather than modifying the original array.

The key insight is that the sorted array represents the expected arrangement. By comparing index by index, you avoid complex rearrangement logic. The algorithm performs one sort operation and one linear pass through the array, leading to O(n log n) time complexity and O(n) additional space for the copy.

Approach 2: Counting Sort Optimization (O(n + k) time, O(k) space)

The constraints of the problem reveal that student heights fall within a small fixed range (1 to 100). Instead of sorting explicitly, you can use counting sort. Create a frequency array where index i stores how many students have height i. This structure lets you reconstruct the sorted order implicitly without performing comparisons.

Traverse the original heights array while maintaining a pointer that represents the current expected height in sorted order. Move this pointer forward through the frequency array until you find a height with remaining count. If the expected height differs from the current element in the original array, increment the mismatch counter. Decrease the frequency and continue. Because each element is processed once and the height range k is constant (100), the runtime becomes O(n + k), which effectively behaves like O(n).

This approach uses ideas from array frequency counting and works best when the value range is limited. It avoids the O(n log n) cost of general sorting and is considered the optimal solution for this problem.

Recommended for interviews: Start with the sorting comparison solution because it clearly demonstrates understanding of the problem. After that, mention the counting sort optimization once you recognize the bounded height range. Interviewers often expect candidates to notice this constraint and reduce the complexity from O(n log n) to near O(n).

Approach 1: Sorting and Comparison

This approach involves creating an 'expected' array by sorting the given 'heights' array. Once sorted, you compare each element of the original 'heights' array with the corresponding element in the 'expected' array. Count the number of mismatches, which will be your answer.

In C, we first copy the original 'heights' array into an 'expected' array. We then sort the 'expected' array using quicksort, provided by the standard library. We iterate over both arrays, counting indices where 'heights[i]' differs from 'expected[i]'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store the 'expected' array.

Try this approach in the editor →

Approach 2: Counting Sort Optimization

Given the constraint that heights range between 1 and 100, we can use a counting sort based approach to find deviations from the expected array without explicitly sorting.

In C, maintain an array 'countHeights' to track frequency of each height from 1 to 100. Use this to simulate creating a sorted version of 'heights' without actually sorting, while counting mismatches directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + k) where k is 100 (a constant, heights range). Space Complexity: O(k) for the count array.

Try this approach in the editor →

Approach 3: Sorting

We can first sort the heights of the students, then compare the sorted heights with the original heights, and count the positions that are different.

The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of students.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Counting Sort

Since the height of the students in the problem does not exceed 100, we can use counting sort. Here we use an array cnt of length 101 to count the number of times each height h_i appears.

The time complexity is O(n + M), and the space complexity is O(M). Where n is the number of students, and M is the maximum height of the students. In this problem, M = 101.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Comparison

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store the 'expected' array.

Counting Sort Optimization

Time Complexity: O(n + k) where k is 100 (a constant, heights range). Space Complexity: O(k) for the count array.

Sorting—
Counting Sort—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and ComparisonO(n log n)O(n)General solution when no assumptions about value range are used
Counting Sort OptimizationO(n + k)O(k)Best when heights fall within a small bounded range such as 1–100

Video Solution

Height Checker - Leetcode 1051 - Python • NeetCodeIO • 10,475 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Height Checker easy or hard?
Height Checker is classified as an easy problem. The straightforward solution uses sorting and a linear comparison pass. The slightly more advanced insight is recognizing that counting sort can reduce the time complexity to near O(n) because the height range is small.
How to solve Height Checker in O(n)?
Use counting sort with a frequency array of size 101 to store occurrences of each height. Iterate through the original array while tracking the expected height from the frequency array. Each mismatch between the expected height and the current value increments the result counter. This processes each element once, giving O(n + k) time.
What is the best approach for Height Checker?
Counting sort is the most efficient approach because student heights are limited to a small range (1–100). By storing frequencies of each height and reconstructing the expected order, you compare positions in O(n + k) time. This effectively runs in O(n) for the given constraints and avoids the O(n log n) cost of sorting.
Is Height Checker asked at Google/Amazon/Meta?
Height Checker is categorized as an easy array and sorting problem and commonly appears in practice sets used for companies like Amazon and Google. It tests basic algorithm selection and the ability to recognize when counting sort can replace standard sorting.
What data structure is used in Height Checker?
The problem primarily uses arrays. The optimized approach introduces a frequency array to implement counting sort, which stores counts for each possible height value and allows reconstruction of the sorted order without comparison-based sorting.
What is the time complexity of Height Checker?
The common sorting-based solution runs in O(n log n) time due to the sort operation, followed by an O(n) comparison pass. Using counting sort reduces the complexity to O(n + k), where k is the range of heights (up to 100). Because k is constant, the optimized solution behaves like O(n).
Height Checker Python or Java solution approach?
Both Python and Java implementations typically follow the same pattern: copy the array, sort it, and count mismatched indices. For the optimized version, create a frequency array of size 101, iterate through the original list, and compare each value against the expected height derived from the frequency counts.

Ready to solve this problem?

Practice Height Checker with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays