Height Checker

Easy

Bloomberg LP

0 views

Topics:

Arrays

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

Height Checker

Easy

Bloomberg LP

0 views

Topics:

Arrays

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the `heights` array?
Can the `heights` array contain negative numbers, zero, or only positive integers?
Are there any constraints on the range of values within the `heights` array?
If the `heights` array is empty, what should be returned?
Are duplicate height values allowed in the `heights` array, and if so, how should they be handled in determining the number of incorrect positions?

Brute Force Solution

Approach

The height checker problem wants to know how many students are out of order. The simplest way to solve this is to figure out what the correct order should be and then compare it to the given order.

Here's how the algorithm would work step-by-step:

First, make a copy of the original list of student heights.
Next, figure out how to sort the copied list from shortest to tallest.
Now, go through the original list and the sorted list at the same time, comparing them one by one.
Every time you find a student in the original list who is not in the same position as the student of the same rank in the sorted list, count it as a mismatch.
After comparing every student, report the total number of mismatches.

Code Implementation

def height_checker(heights):
    # Create a copy to avoid modifying the original
    expected_heights = heights.copy()

    # Sort the copied list to represent the ideal order
    expected_heights.sort()

    mismatched_students = 0

    # Compare the original and sorted lists
    for index in range(len(heights)):
        # Count the students that are not in the correct position
        if heights[index] != expected_heights[index]:
            mismatched_students += 1

    return mismatched_students

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is sorting the copied list of student heights. Sorting algorithms like merge sort or quicksort, which are typically used in standard library sort functions, have a time complexity of O(n log n), where n is the number of students. The other operations, such as copying the list and comparing the original and sorted lists, take O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm creates a copy of the original input list of student heights, which requires additional space proportional to the number of students, N. The sorted copy is stored in auxiliary space. While there may be constant space usage for index variables, the dominant factor is the sorted copy of size N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The efficient way to solve this problem is to avoid comparing the original order to every single possible reordering. Instead, we create a perfectly sorted version and then compare it to the original to see where they differ.

Here's how the algorithm would work step-by-step:

Make a copy of the original group of numbers.
Arrange the copied numbers in perfect order from smallest to largest.
Go through the original and the sorted group of numbers, one number at a time.
Every time a number in the original is different from the number in the sorted version, count it as a mismatch.
The total number of mismatches tells you how many students are out of place.

Code Implementation

def heightChecker(heights):    # Create a sorted copy of the original heights    expected_heights = sorted(heights[:])
    mismatched_students = 0
    # Compare the original and sorted lists    for i in range(len(heights)):        # Count discrepancies between the two lists
        if heights[i] != expected_heights[i]:            mismatched_students += 1
    return mismatched_students

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant factor in the time complexity is the sorting of the copied array. Common efficient sorting algorithms, such as merge sort or quicksort, have a time complexity of O(n log n), where n is the number of elements in the input array. The subsequent comparison of the original and sorted arrays involves a single loop iterating through n elements, which is O(n). Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The algorithm creates a copy of the original input list of numbers to sort it. This sorted copy requires additional space proportional to the size of the original input, N, where N is the number of elements in the input list. The variables used for iteration and counting mismatches take up constant space. Therefore, the auxiliary space complexity is dominated by the sorted copy, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty, as there are no students to compare.
Input array with only one element	Return 0 because if there is only one student, they are trivially in the correct position.
Input array with all elements the same	Return 0 because the sorted array will be identical to the original array.
Input array already sorted in non-decreasing order	Return 0 as no students are out of place.
Input array sorted in strictly decreasing order	The return value will be equal to the number of elements, since every student is out of place.
Input array with a large number of elements (scalability)	Using an efficient sorting algorithm (e.g., merge sort, quicksort) ensures the solution scales well.
Input array containing large integer values	The sorting algorithm should handle large integer values without overflow issues (using `int` or `long` appropriately).
Array with duplicate heights mixed with non-sorted heights	The standard sorting algorithm correctly handles duplicate heights in `heights` to generate `expected` array.