1051. Height Checker
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:
- Create a sorted version of the
heights
array, which we can callexpected
. This sorted array represents the students in the correct order. - We then compare each element in the sorted
expected
array with the corresponding element in the originalheights
array. - Every time we find a mismatch, we know that the student is not in the correct order.
- To find the total number of mismatches, we iterate through both arrays simultaneously, comparing the students' heights element by element.
- Each mismatch contributes to the count of students who are not in their correct position.
- 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:
-
Sorting: We start by sorting the
heights
array which gives us theexpected
order of heights. Sorting is done using Python's built-insorted()
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)
-
Comparison: After sorting, we need to compare the elements of the
expected
(sorted) array with theheights
(original) array. This is done to check for any discrepancies between the current order and the expected order. -
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 yieldsTrue
for each mismatch andFalse
for each match. sum()
is used to count how many timesTrue
appears in the generator, which corresponds to the number of mismatches sinceTrue
is interpreted as1
andFalse
as0
.
- The
-
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).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 ofheights
)
-
Sorting: First, we sort the
heights
array which should look like theexpected
array:1expected = sorted(heights) # expected becomes [1, 2, 3, 4]
-
Comparison: We then compare
heights
withexpected
:Index heights expected Match? 0 3 1 No 1 1 2 No 2 2 3 No 3 4 4 Yes We see that at indices 0, 1, and 2, the values don't match, while at index 3, they do.
-
Count Mismatches: We count the mismatches using the
zip()
function and a generator expression within thesum()
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.
-
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.
- Sorting: The
sorted()
function in Python uses the Timsort algorithm, which has a worst-case time complexity ofO(n log n)
wheren
is the number of elements in theheights
array. - Comparison: The
sum()
function with a generator expression that iterates over the zipped pairs of the original and sortedheights
arrays runs inO(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
.
- Creating a sorted array: This requires additional space to hold all the
n
elements from the originalheights
array, so this operation has a space complexity ofO(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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.