algoadvance

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. You are given an integer array heights representing the heights of the students in the order they are currently standing. Return the number of indices where the heights do not match the order when sorted.

Example:

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.

Clarifying Questions:

  1. Can the input array be empty?
    • No, the problem ensures there is at least one student.
  2. Are there any constraints on the elements of the input array?
    • The lengths of the heights are between 1 and 100.
  3. Should we consider heights with equal values as matching?
    • Yes, identical heights in their respective positions are considered matching.

Strategy

The solution involves comparing the given array with a sorted version of the same array and counting the number of discrepancies between the two lists.

  1. Copy and Sort: Create a sorted copy of the heights array.
  2. Count Mismatches: Compare the original and sorted arrays element by element and count how many indices differ.

Code

def heightChecker(heights):
    expected = sorted(heights)
    mismatch_count = 0
    
    for i in range(len(heights)):
        if heights[i] != expected[i]:
            mismatch_count += 1
    
    return mismatch_count

Time Complexity

  1. Sorting the Array: O(n log n), where n is the length of the heights array.
  2. Comparison Loop: O(n), since we iterate through the array once.

Overall time complexity: O(n log n) due to the sorting step, which is the most time-consuming operation.

Example Walkthrough

Let’s take the example provided: heights = [1,1,4,2,1,3]

  1. Sort the Array:
    • Original: [1, 1, 4, 2, 1, 3]
    • Sorted: [1, 1, 1, 2, 3, 4]
  2. Compare Elements:
    • Index 0: 1 == 1 → match
    • Index 1: 1 == 1 → match
    • Index 2: 4 != 1 → mismatch
    • Index 3: 2 == 2 → match
    • Index 4: 1 != 3 → mismatch
    • Index 5: 3 != 4 → mismatch
  3. Count of Mismatches: 3

Thus, the function returns 3.

Try our interview co-pilot at AlgoAdvance.com