Vultr DocsLatest Content

Height Checker

Updated on 02 June, 2025
Height Checker header image

Problem Statement

In an attempt to organize an annual school photograph, students are instructed to line up in a single file where their heights are ordered in a non-decreasing sequence. The desired order of students by height is conveyed through an integer array expected, where expected[i] refers to the height expected for the i-th student in the lineup.

However, there remains a complication. Students are initially standing in an order represented by another integer array, heights, where heights[i] corresponds to the actual height of the i-th student as they currently stand.

The task at hand is to determine how many students are standing out of the expected order. Specifically, the challenge is to return the number of indices i for which the height of the student at heights[i] does not match the height at expected[i].

This problem entails a direct comparison between the given ordering of heights and a sorted version of the same array to identify mismatches, thereby pinpointing students who are out of the desired sequential order.

Examples

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

Approach and Intuition

To solve the problem effectively:

  1. Begin by sorting the heights array to generate the expected array which is the correct non-decreasing order of student heights.
  2. Initialize a counter to zero. This will be used to keep track of indices where discrepancies occur.
  3. Compare the sorted heights array (now equivalent to expected) with the original heights array using a loop:
    • For each index, check if the value in the sorted array differs from the value in the original array.
    • If they do differ, increment the counter by one.
  4. Return the total count of these discrepancies, which represents the number of students out of place.

The essence of this approach is leveraging the ability to sort and directly compare arrays to find element-wise mismatches. The constraints are manageable, allowing efficient execution of sorting operations and comparisons within the given limits. This method ensures each misplacement is counted accurately, culminating in the total number of students who need to adjust their position in line to fulfill the expected order.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
    // Function to sort using a specific digit
    void sortOnDigit(vector<int>& nums, int digitFactor) {
        vector<vector<int>> storage(10, vector<int>());
        for (int& number : nums) {
            int digit = abs(number) / digitFactor % 10;
            storage[digit].push_back(number);
        }

        int position = 0;
        for (int index = 0; index < 10; ++index) {
            for (int& item : storage[index]) {
                nums[position++] = item;
            }
        }
    }

    // Function to perform radix sort
    void performRadixSort(vector<int>& nums) {
        int maxVal = nums[0];
        for (int& number : nums) {
            maxVal = max(abs(number), maxVal);
        }
        int totalDigits = 0;
        while (maxVal > 0) {
            totalDigits++;
            maxVal /= 10;
        }

        int currentPlace = 1;
        for (int digit = 0; digit < totalDigits; ++digit) {
            sortOnDigit(nums, currentPlace);
            currentPlace *= 10;
        }
    }

public:
    int heightChecker(vector<int>& heights) {
        vector<int> expected = heights;
        performRadixSort(expected);

        int mismatches = 0;
        for (size_t i = 0; i < expected.size(); ++i) {
            if (heights[i] != expected[i]) {
                mismatches++;
            }
        }
        return mismatches;
    }
};

The provided C++ code defines a solution to the problem of counting how many elements in an array differ from their position in a sorted version of the array. The class Solution features two main functionalities:

  • Radix Sort Implementation:

    • sortOnDigit method handles sorting based on individual digits
    • performRadixSort method manages the full process of radix sorting through multiple passes, determined by the number of digits in the largest number.

  • Height Checking:

    • heightChecker method first copies the heights vector to a new vector expected, then sorts expected using the performRadixSort method. It then compares elements in the original heights vector with the sorted expected vector, counts discrepancies, and returns this count.

By decomposing the task into sorting the array independently and then comparing it with the original order, the solution provides a clean and efficient way to determine the number of out-of-order height placements, leveraging the efficiency and stability of the radix sort algorithm.

java 
class Solution {
    
    // Helper function to sort numbers by individual digits
    private void digitSort(int[] array, int exp) {
        List<List<Integer>> bucket = new ArrayList<>(10);
        for (int j = 0; j < 10; j++) {
            bucket.add(new ArrayList<>());
        }

        // Distribute numbers based on current digit
        for (int number : array) {
            int digit = (Math.abs(number) / exp) % 10;
            bucket.get(digit).add(number);
        }

        // Collect back to original array
        int position = 0;
        for (int k = 0; k < 10; k++) {
            for (int value : bucket.get(k)) {
                array[position] = value;
                position++;
            }
        }
    }

    // Sorting function using digit-by-digit sorting
    private void sortDigits(int[] data) {
        // Determine the number of digits in the largest number
        int maximum = Arrays.stream(data).map(Math::abs).max().getAsInt();
        int maxDigits = 0;
        for (; maximum > 0; maxDigits++, maximum /= 10);
        
        // Sort for each digit
        for (int pos = 1, digit = 0; digit < maxDigits; digit++, pos *= 10) {
            digitSort(data, pos);
        }
    }

    public int heightChecker(int[] heights) {
        // Clone and sort the array heights
        int[] expected = heights.clone();
        sortDigits(expected);

        // Count mismatches between original and sorted arrays
        int mismatchCount = 0;
        for (int i = 0; i < expected.length; i++) {
            if (heights[i] != expected[i]) mismatchCount++;
        }
        
        // Return the count of heights that are out of order
        return mismatchCount;
    }
}

The provided Java solution defines a method to determine how many heights are out of order from their original positions after sorting. Here's a breakdown of the approach and components of the code:

  • A digitSort function sorts numbers based on individual digits from least significant to most significant. This function uses a bucket sort algorithm, where numbers are distributed into buckets based on their current significant digit and then collected back in order.
  • The sortDigits function leverages the digitSort to sort an entire array by iterating through each digit of the maximum value in the array. This ensures a complete and correct sort using digit-wise comparison.
  • Inside the heightChecker method:
    1. The original heights array is cloned to expected.
    2. The expected array is sorted using the sortDigits method.
    3. The number of positions where the sorted array (expected) doesn't match the original heights array is counted.
    4. This count is then returned, representing the number of heights in the wrong positions relative to a sorted list.

The result from heightChecker shows the degree of mismatch, offering a clear metric of how many elements (heights) are out of order. This solution smartly applies a non-comparison-based sort, bucket sort, adapted for numerical sorting via digit manipulation, which is both efficient and appropriate for the problem context.

python 
class Solution:
    # Organize numbers in buckets based on their digits.
    def digit_bucket_sort(self, nums, digit_place):
        container = [[] for _ in range(10)]

        # Distribute the numbers based on the current digit.
        for value in nums:
            index = abs(value) // digit_place % 10
            container[index].append(value)

        # Consolidate elements back to the list in sorted manner.
        position = 0
        for bucket_index in range(10):
            for item in container[bucket_index]:
                nums[position] = item
                position += 1

    # Main method for sorting using Radix sort by digit.
    def digit_radix_sort(self, nums):
        # Determine the maximum number of digits.
        maximum, num_digits = max(abs(x) for x in nums), 0
        while maximum:
            num_digits += 1
            maximum //= 10

        # Sort from least significant to most significant digit.
        base_place = 1
        for _ in range(num_digits):
            self.digit_bucket_sort(nums, base_place)
            base_place *= 10

    def heightChecker(self, heights: List[int]) -> int:
        # Sort heights using radix sort.
        expected_order = list(heights)
        self.digit_radix_sort(expected_order)

        # Count mismatches between the sorted and the original list.
        mismatch_count = 0
        for i in range(len(expected_order)):
            if heights[i] != expected_order[i]:
                mismatch_count += 1

        # Return the number of students not in the expected positions.
        return mismatch_count

This Python solution employs a sophisticated digit-based Radix sort algorithm to address the problem of determining how many students are not in their expected height order. Follow the detailed breakdown below to understand the implementation:

  • Radix Sort Mechanism:

    • Initialize a digit_radix_sort method that sorts an array of integers. This method uses the digit_bucket_sort repeatedly, each time sorting the numbers based on an increasing significant digit (from least to most significant).
    • Digit-Wise Distribution:
      • In the digit_bucket_sort method, numbers are distributed into buckets based on their current digit value. This distribution utilizes the modulus operation and integer division to isolate digit values.
    • Collection From Buckets:
      • After distribution, numbers are collected back from the buckets in order maintaining their sorted condition with respect to the current digit.

  • Height Checker Function:

    • This function uses the digit_radix_sort to sort the heights list and then assigns it to expected_order.
    • It iterates over the sorted expected_order and the original heights list simultaneously to count the mismatches, hence identifying students standing out of the expected ascending height order.

  • Count Mismatches:

    • The method finally returns the total number of positions where the original list of heights does not match the sorted expected_order list, indicating the number of students out of place.

By using Radix sort, the solution effectively handles the sorting process without relying on comparison-based sorting methods, which often have higher time complexities for larger input sizes. This approach is efficient, especially when dealing with non-negative integers in the list.

Comments

No comments yet.