Height Checker - Practice Coding Problems

Height Checker - Problem

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 i^th 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 i^th student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Input & Output

Example 1 — Basic Case

$ Input: heights = [1,1,4,2,1,3]

› Output: 3

💡 Note: Expected order is [1,1,1,2,3,4]. Positions 2, 3, and 5 have wrong heights (4≠1, 2≠2, 3≠4), so 3 students need to move.

Example 2 — Already Sorted

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

› Output: 5

💡 Note: Expected order is [1,2,3,4,5]. All positions except none match, so all 5 students are in wrong positions.

Example 3 — Perfect Order

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

› Output: 0

💡 Note: Already in non-decreasing order. No students need to move.

Constraints

1 ≤ heights.length ≤ 100
1 ≤ heights[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Current Line

Students standing in current order

Expected Line

How students should be arranged by height

Count Misplaced

Number of students in wrong positions

Key Takeaway

🎯 Key Insight: Compare current arrangement with sorted arrangement to find how many students are out of place

Asked in

a Amazon 25 G Google 20 Apple 15

The key insight is that we need to compare the current arrangement with the sorted arrangement to count misplaced students. The optimal approach uses counting sort since heights are limited to range 1-100. Time: O(n), Space: O(1) extra.

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Compare	O(n log n)	O(n)	Sort a copy of the array and compare with original positions
Counting Sort Approach	O(n + k)	O(k + n)	Use counting sort since heights have limited range (1-100)

Sort and Compare — Algorithm Steps

Step 1: Create a copy of the heights array
Step 2: Sort the copy to get expected positions
Step 3: Compare each position and count differences

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Current heights arrangement

Sort Copy

Create sorted version for comparison

Count Differences

Compare positions and count mismatches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* heights, int size) {
    int* expected = (int*)malloc(size * sizeof(int));
    memcpy(expected, heights, size * sizeof(int));
    qsort(expected, size, sizeof(int), compare);
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (heights[i] != expected[i]) {
            count++;
        }
    }
    free(expected);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int heights[1000], size = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        heights[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    printf("%d\n", solution(heights, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the array takes O(n log n) time

⚡ Linearithmic

Space Complexity

O(n)

Extra array to store the sorted copy

⚡ Linearithmic Space

78.0K Views

Medium Frequency

~8 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Compare — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler