Height Checker

Easy
205.

Height Checker

Height Checker is an easy coding problem on arrays, sorting and counting sort, asked in Amazon and Microsoft interviews.

A school is taking an annual photo of all the students, who should stand in non-decreasing order of height. Let expected be that correctly ordered line.

Given the current line heights, return the number of positions where heights[i] != expected[i].

Example 1

Input
heights = [1,1,4,2,1,3]
Output
3
Explanation
expected = [1,1,1,2,3,4]; indices 2, 4 and 5 differ.

Example 2

Input
heights = [5,1,2,3,4]
Output
5

Example 3

Input
heights = [1,2,3,4,5]
Output
0

Constraints

  • 1 <= heights.length <= 40
  • 1 <= heights[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} heights
 * @return {number}
 */
var heightChecker = function(heights) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Height Checker — Solution in Python, Java & C++

Height Checker solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and sorting.

Height Checker is an easy coding problem on arrays, sorting and counting sort, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Counting Sort
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A school is taking an annual photo of all the students, who should stand in non-decreasing order of height. Let expected be that correctly ordered line.

Given the current line heights, return the number of positions where heights[i] != expected[i].

Example 1

Input: heights = [1,1,4,2,1,3]
Output: 3
Explanation: expected = [1,1,1,2,3,4]; indices 2, 4 and 5 differ.

Example 2

Input: heights = [5,1,2,3,4]
Output: 5

Example 3

Input: heights = [1,2,3,4,5]
Output: 0

Constraints

  • 1 <= heights.length <= 40
  • 1 <= heights[i] <= 100

Hints for Height Checker

  1. Hint 1

    Sort a copy — the original order is what you are comparing against.

  2. Hint 2

    Then count positions where the two arrays disagree.

  3. Hint 3

    Heights are bounded by 100, so a counting sort makes it O(n + 100).

How to solve Height Checker

Sort a copy to get the expected line and count positions that disagree with the original.

Approach

  1. Sort a copy of heights.
  2. Count indices i with heights[i] != expected[i].

Why it works

The expected line is by definition the sorted order; comparing index by index counts exactly the students standing in the wrong slot.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Heights are ≤ 100, so a counting sort makes this O(n + 100).
  • Sorting in place destroys the original you must compare against.

Reference solution

Python

def heightChecker(heights):
    expected = sorted(heights)
    return sum(1 for i in range(len(heights)) if heights[i] != expected[i])

Java

public static int heightChecker(int[] heights) {
    int[] expected = Arrays.copyOf(heights, heights.length);
    Arrays.sort(expected);
    int count = 0;
    for (int i = 0; i < heights.length; i++) {
        if (heights[i] != expected[i]) count++;
    }
    return count;
}

C++

int heightChecker(vector<int>& heights) {
    vector<int> expected = heights;
    sort(expected.begin(), expected.end());
    int count = 0;
    for (size_t i = 0; i < heights.size(); i++) {
        if (heights[i] != expected[i]) count++;
    }
    return count;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms