Code Logo

Height Checker

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Height Checker

Solution Approach

Sort a copy. Count differences between original and sorted.

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

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

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;
    }
}