We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Height Checker

Number: 1137

Difficulty: Easy

Paid? No

Companies: IBM, Google, Meta, Salesforce

Problem Description

Given an array of student heights, determine how many positions do not match the expected order when the heights are sorted in non-decreasing order. Essentially, count the mismatches between the current ordering and the sorted (expected) ordering.

Key Insights

  • Create a copy of the original heights array and sort it to form the expected order.
  • Compare each element of the original array with the sorted array.
  • Count the indices where the two arrays differ.
  • The problem focuses on counting mismatches without needing to physically rearrange the array.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(n) for storing the sorted copy of the array.

Solution

The approach is to first sort a copy of the given array to know the correct order of heights. Then, iterate through both arrays simultaneously and count the positions where the elements differ. This gives the number of students that are not in their correct positions. The primary data structures used are arrays, and the algorithm leverages sorting followed by a simple linear scan.

Code Solutions

Below are solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

# Function to determine the number of indices where heights differ from the sorted order
def heightChecker(heights):
    # Create a sorted copy of the heights array to represent the expected order
    expected = sorted(heights)
    count = 0
    # Loop through each index and compare the original and expected heights
    for index in range(len(heights)):
        if heights[index] != expected[index]:
            count += 1  # Increment count if there is a mismatch
    return count

# Example usage
if __name__ == "__main__":
    heights = [1, 1, 4, 2, 1, 3]
    # Expected output is 3 because there are 3 positions that differ from the sorted order
    print(heightChecker(heights))
← Back to All Questions