Height Checker

EASY

Description

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].

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

Approaches

Checkout 2 different approaches to solve Height Checker. Click on different approaches to view the approach and algorithm in detail.

Comparison Sort

This straightforward approach involves first determining the expected order of students. This is achieved by creating a copy of the heights array and sorting it in non-decreasing order. Once we have both the original heights array and the sorted expected array, we can iterate through them simultaneously and count the number of positions where the heights do not match.

Algorithm

Create a copy of the heights array, let's call it expected.
Sort the expected array using a standard comparison-based sorting algorithm (e.g., Arrays.sort() in Java).
Initialize a counter variable, mismatchCount, to zero.
Iterate from i = 0 to heights.length - 1.
In each iteration, compare heights[i] with expected[i].
If heights[i] != expected[i], increment mismatchCount.
After the loop completes, return mismatchCount.

The core idea is to generate the target sorted array and then perform a direct comparison.

Create a Copy: We first create an exact copy of the heights array. We cannot sort the original array in-place because we need it for the final comparison.
Sort: We use a standard library function, like Arrays.sort(), to sort the copied array. This function typically implements an efficient comparison sort algorithm like Quicksort or Timsort, resulting in an O(N log N) time complexity.
Compare and Count: We then loop through both the original heights array and the newly sorted expected array from the first to the last element. A counter is used to keep track of the number of indices i where heights[i] is not equal to expected[i]. This count is the final answer.

import java.util.Arrays;

class Solution {
    public int heightChecker(int[] heights) {
        int n = heights.length;
        int[] expected = new int[n];
        // Create a copy of the heights array.
        System.arraycopy(heights, 0, expected, 0, n);
        
        // Sort the copied array to get the expected order.
        Arrays.sort(expected);
        
        int mismatchCount = 0;
        // Compare the original array with the sorted array.
        for (int i = 0; i < n; i++) {
            if (heights[i] != expected[i]) {
                mismatchCount++;
            }
        }
        
        return mismatchCount;
    }
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of students. The dominant operation is sorting the array. Copying the array and the final comparison loop both take O(N) time, which is overshadowed by the sort.Space Complexity: O(N), where N is the number of students. This space is required to store the copy of the `heights` array.

Pros and Cons

Pros:

Easy to understand and implement.
The code is concise and relies on well-tested built-in functions.

Cons:

Sub-optimal time complexity compared to other methods that can leverage the problem's constraints.
Requires extra space proportional to the input size (O(N)) to store the copied array.

Code Solutions

Checking out 3 solutions in different languages for Height Checker. Click on different languages to view the code.

class Solution {
public
  int heightChecker(int[] heights) {
    int[] expected = heights.clone();
    Arrays.sort(expected);
    int ans = 0;
    for (int i = 0; i < heights.length; ++i) {
      if (heights[i] != expected[i]) {
        ++ans;
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Height Checker

Algorithms:

SortingCounting Sort

Data Structures:

Array

Companies:

Salesforce |