Code Logo

Height Checker

Published at24 Jul 2026
Created by
Easy 4 views
Like0

Students are standing in a line at a height check. The heights are recorded in an array. To check if students are in non-decreasing order by height, sort the array and compare. Count the number of positions where the heights differ from the sorted order.

Create a sorted copy of the heights array using the built-in sort function. Iterate through both arrays simultaneously, counting indices where the values differ. This count represents the minimum number of students that need to move to achieve sorted order.

Time is O(n log n) for sorting plus O(n) for the comparison pass. Space is O(n) for the sorted copy. Edge cases include an empty array (return 0), a single student (return 0), and an already sorted array (return 0).

The height checker problem is commonly used to assess understanding of sorting and array comparison operations. It demonstrates how sorting creates a reference ordering against which the original arrangement can be measured.

An alternative approach uses counting sort since heights are in a limited range (1 to 100 in the problem constraints), achieving O(n + k) time where k is the range of heights.

The counting sort alternative achieves O(n + k) time where k is the height range (1-100), demonstrating how problem constraints can enable more efficient solutions than general-purpose sorting.

Example Input & Output

Example 1
Input
[1,2,3,4,5]
Output
0
Explanation

Already sorted.

Example 2
Input
[1,1,4,2,1,3]
Output
3
Explanation

Differences at indices 2,4,5.

Example 3
Input
[5,1,2,3,4]
Output
5
Explanation

All out of order.

Example 4
Input
[]
Output
0
Explanation

Empty.

Example 5
Input
[1]
Output
0
Explanation

Single.

Algorithm Flow

Recommendation Algorithm Flow for Height Checker

Solution Approach

Compare the original array with its sorted version element by element, counting how many positions differ. The count of mismatches is the minimum number of students that need to move.

function heightChecker(heights) {
  var expected = heights.slice().sort(function(a, b) { return a - b; });
  var count = 0;
  for (var i = 0; i < heights.length; i++) {
    if (heights[i] !== expected[i]) count++;
  }
  return count;
}

Create a sorted copy of the array. Compare each position between the original and sorted arrays. Every position where the values differ represents a student that is not in the correct sorted position. The total count is the minimum number of students that must move.

Time complexity is O(n log n) for the sort, space complexity is O(n) for the sorted copy.

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] heights) {
        int[] s=heights.clone();
        Arrays.sort(s);
        int c=0;
        for (int i=0;i<heights.length;i++) if (heights[i]!=s[i]) c++;
        return c;
    }
}