1051. Height Checker

EasyArrayCounting SortSorting
Leetcode Link

Problem Description

In this problem, we are given two arrays; expected, which represents the non-decreasing order of students' heights for a school photo, and heights, which is the current order of students standing in a line for the photo. The goal is to find out how many students are standing in the wrong position compared to the expected order. To do this, we need to compare the elements of the two arrays and count the number of positions where the heights do not match.

The comparison is based on the index of the array, meaning we look at the height of each student at a particular position in the heights array and check if it matches the height at the same position in the expected array. The result will be the total number of students who need to move to match the expected height order.

Intuition

To find the solution, we need to follow these steps:

  1. Create a sorted version of the heights array, which we can call expected. This sorted array represents the students in the correct order.
  2. We then compare each element in the sorted expected array with the corresponding element in the original heights array.
  3. Every time we find a mismatch, we know that the student is not in the correct order.
  4. To find the total number of mismatches, we iterate through both arrays simultaneously, comparing the students' heights element by element.
  5. Each mismatch contributes to the count of students who are not in their correct position.
  6. Finally, the sum of all mismatches gives us the total number of students standing out of order.

The given solution uses list comprehension to compare the two arrays and count the mismatches using the sum function, all in one compact line of code.

Learn more about Sorting patterns.

Solution Approach

The solution provided implements a straightforward algorithm for solving the problem using the following steps:

  1. Sorting: We start by sorting the heights array which gives us the expected order of heights. Sorting is done using Python's built-in sorted() function, which typically implements the Timsort algorithm—a hybrid sorting algorithm derived from merge sort and insertion sort. The complexity of this operation is O(n log n), where n is the number of students.

    1expected = sorted(heights)
  2. Comparison: After sorting, we need to compare the elements of the expected (sorted) array with the heights (original) array. This is done to check for any discrepancies between the current order and the expected order.

  3. Count Mismatches: We count the number of positions where the heights do not match by iterating through both arrays simultaneously. For each pair of elements at the same index, we check if they are different.

    1return sum(a != b for a, b in zip(heights, expected))
    • The zip() function is used to create pairs of elements from both arrays that share the same index.
    • The expression (a != b for a, b in zip(heights, expected)) creates a generator that yields True for each mismatch and False for each match.
    • sum() is used to count how many times True appears in the generator, which corresponds to the number of mismatches since True is interpreted as 1 and False as 0.
  4. Return Result: The sum, representing the count of mismatches, is then returned as the final result.

In terms of data structures, the solution makes use of lists (arrays in other programming languages) and employs list comprehension for concise iteration and comparison. This solution is efficient due to its simplicity and Python's optimization of list operations and sorting. The space complexity of the solution is O(n), because we are creating a new list expected which is a sorted copy of heights, and the time complexity is dominated by the sorting operation, making it O(n log n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following arrays:

  • heights : [3, 1, 2, 4]
  • expected: [1, 2, 3, 4] (this is the sorted order of heights)
  1. Sorting: First, we sort the heights array which should look like the expected array:

    1expected = sorted(heights)  # expected becomes [1, 2, 3, 4]
  2. Comparison: We then compare heights with expected:

    IndexheightsexpectedMatch?
    031No
    112No
    223No
    344Yes

    We see that at indices 0, 1, and 2, the values don't match, while at index 3, they do.

  3. Count Mismatches: We count the mismatches using the zip() function and a generator expression within the sum() function:

    1mismatches = sum(a != b for a, b in zip(heights, expected))
    2# The comparison (a != b for a, b in zip([3, 1, 2, 4], [1, 2, 3, 4]))
    3# yields [True, True, True, False] which sums up to 3.
  4. Return Result: The value 3 is then returned, indicating that three students are standing in the wrong positions.

Following this example, by comparing the sorted order (which is the expected correct order) with the current heights, we identified that 3 out of the 4 students are out of order, which shows our solution correctly identifies and counts the number of mismatches.

Solution Implementation

1from typing import List
2
3class Solution:
4    def heightChecker(self, heights: List[int]) -> int:
5        # Create a sorted version of the heights list, which will represent 
6        # the expected order after sorting by height
7        expected = sorted(heights)
8      
9        # Use zip() to pair elements from the actual order and the expected order
10        # and then use sum() with a generator to count differences between paired elements,
11        # which indicates how many students are not in the correct positions
12        mismatch_count = sum(actual_height != expected_height for actual_height, expected_height in zip(heights, expected))
13      
14        # Return the total count of mismatches found
15        return mismatch_count
16
1class Solution {
2    public int heightChecker(int[] heights) {
3        // Clone the original array to create a separate array which we can sort
4        int[] expectedHeights = heights.clone();
5      
6        // Sort the expectedHeights array to have the heights in ascending order
7        Arrays.sort(expectedHeights);
8      
9        // Initialize a counter to keep track of the number of heights in the wrong position
10        int countMismatchedHeights = 0;
11      
12        // Iterate over the heights array to compare each element with the corresponding element in the sorted expectedHeights array
13        for (int i = 0; i < heights.length; ++i) {
14            // If the height in original order does not match the height in sorted order, increment the counter
15            if (heights[i] != expectedHeights[i]) {
16                countMismatchedHeights++;
17            }
18        }
19      
20        // Return the total number of heights that are out of place when compared to the sorted order
21        return countMismatchedHeights;
22    }
23}
24
1class Solution {
2public:
3    int heightChecker(vector<int>& heights) {
4        // Create a copy of the original 'heights' vector to store the expected sorted order
5        vector<int> sortedHeights = heights;
6
7        // Sort the 'sortedHeights' vector to represent the expected heights order
8        sort(sortedHeights.begin(), sortedHeights.end());
9
10        // Initialize a counter to track the number of students not in the correct position
11        int misplacedCount = 0;
12
13        // Iterate over the original 'heights' vector to compare with the 'sortedHeights'
14        for (int i = 0; i < heights.size(); ++i) {
15            // Increment the counter when the current height does not match the expected height
16            misplacedCount += heights[i] != sortedHeights[i];
17        }
18
19        // Return the total count of students who are not in the correct position
20        return misplacedCount;
21    }
22};
23
1// Define a function to count how many students are not in the correct positions based 
2// on their heights compared to a sorted array of heights
3function heightChecker(heights: number[]): number {
4    // Create a copy of the original 'heights' array to store the expected sorted order
5    const sortedHeights = [...heights];
6
7    // Sort the 'sortedHeights' array to represent the expected heights order
8    sortedHeights.sort((a, b) => a - b);
9
10    // Initialize a counter to track the number of students not in the correct position
11    let misplacedCount: number = 0;
12
13    // Iterate over the original 'heights' array to compare it with the 'sortedHeights'
14    for (let i = 0; i < heights.length; i++) {
15        // Increment the counter when the current height does not match the expected height
16        if (heights[i] !== sortedHeights[i]) {
17            misplacedCount++;
18        }
19    }
20
21    // Return the total count of students who are not in the correct position
22    return misplacedCount;
23}
24

Time and Space Complexity

Time Complexity

The time complexity of the given function is determined by two main operations: sorting the heights array and comparing the elements of the two arrays.

  1. Sorting: The sorted() function in Python uses the Timsort algorithm, which has a worst-case time complexity of O(n log n) where n is the number of elements in the heights array.
  2. Comparison: The sum() function with a generator expression that iterates over the zipped pairs of the original and sorted heights arrays runs in O(n) time since each element is visited exactly once.

Therefore, the combined time complexity of these operations is O(n log n) + O(n) which simplifies to O(n log n) because the O(n log n) term dominates for large values of n.

Space Complexity

The space complexity of the function is primarily due to the storage requirement for the sorted list expected.

  1. Creating a sorted array: This requires additional space to hold all the n elements from the original heights array, so this operation has a space complexity of O(n).

The generator expression used in the sum does not require additional space as it uses the iterator protocol, therefore, the space needed for the iterators themselves is negligible.

In conclusion, the space complexity of the given function is O(n) due to the extra array created to hold the sorted heights.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄