Problem Statement

A school is organizing its annual photo session, and students must stand in a single line arranged by height in non-decreasing order. The expected order of heights is represented by an array expected, where expected[i] is the height of the i^th student in line.

Given an array heights representing the current order in which students are standing, determine how many positions in the heights array do not match the expected order.

Examples

1. Example 1:

   • Input: heights = [5, 1, 2, 3, 4, 8, 1]
   • Expected Output: 3
   • Justification: The expected order is [1, 1, 2, 3, 4, 5, 8]. Comparing with heights, the positions that do not match are 0, 5 and 6.

2. Example 2:

   • Input: heights = [10, 6, 8, 5, 9]
   • Expected Output: 3
   • Justification: The expected order is [5, 6, 8, 9, 10]. Comparing with heights, the positions that do not match are 0, 3 and 4.

3. Example 3:

   • Input: heights = [7, 3, 2, 1, 4]
   • Expected Output: 5
   • Justification: The expected order is [1, 2, 3, 4, 7]. All positions differ from heights.

Constraints:

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

Solution

To solve this problem, we use a counting sort approach to determine how many students are standing in incorrect positions. We start by creating a frequency array to count the occurrences of each height in the heights array. This frequency array helps us understand how many times each height appears, making it easy to reconstruct the sorted order of heights. By leveraging the count of each height, we can then build the expected sorted array without actually sorting the original array, which is more efficient.

Next, we compare the original heights array with the reconstructed sorted array. We iterate through the heights array and, for each position, check if the height matches the expected height from the sorted array. If there is a mismatch, we increment a counter. This approach works efficiently because it avoids the need for a traditional sorting algorithm, instead relying on the counting sort's linear time complexity to handle the sorting implicitly.

Step-by-Step Algorithm

1. Initialize Variables:

   • Define max_height as the maximum value in the heights array (given as 100 for simplicity).
   • Create a frequency array count of size max_height + 1 initialized to zero.

2. Count Frequencies:

   • Iterate through each height in the heights array.
   • For each height, increment the corresponding index in the count array.

3. Initialize Result and Current Height:

   • Initialize result to zero, which will count the mismatches.
   • Initialize currentHeight to zero, which will track the current height being processed.

4. Compare Arrays:

   • Iterate through the heights array using an index i.
   • For each height in heights, find the next non-zero count in the count array:
     • This step will give us next height in the sorted order, and we will compare it with the height[i].
     • While count[currentHeight] is zero, increment currentHeight. In this step, we skip index related to elements which are not in the heights array.
     • Compare heights[i] with currentHeight:
       • If they do not match, increment result.
     • Decrement the count of currentHeight in the count array.

5. Return Result:

   • Return result as the number of positions where the heights do not match the expected order.

Algorithm Walkthrough

Given heights = [5, 1, 2, 3, 4, 8, 1]:

1. Initialize Variables:

   • max_height = 100.
   • count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (array of size max_height + 1).

2. Count Frequencies:

   • Iterate through heights:
     • For height 5: count[5] becomes 1.
     • For height 1: count[1] becomes 1.
     • For height 2: count[2] becomes 1.
     • For height 3: count[3] becomes 1.
     • For height 4: count[4] becomes 1.
     • For height 8: count[8] becomes 1.
     • For height 1: count[1] becomes 2.
   • Resulting count array: [0, 2, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].

3. Initialize Result and Current Height:

   • result = 0.
   • currentHeight = 0.

4. Compare Arrays:

   • Iterate through heights with index i:
     • For i = 0, heights[0] = 5:
       • While count[currentHeight] == 0, increment currentHeight to 1.
       • Compare 5 with 1: Mismatch, increment result to 1.
       • Decrement count[1] to 1.
     • For i = 1, heights[1] = 1:
       • Compare 1 with 1: Match, result remains 1.
       • Decrement count[1] to 0.
     • For i = 2, heights[2] = 2:
       • Increment currentHeight to 2 (since count[1] is 0).
       • Compare 2 with 2: Match, result remains 1.
       • Decrement count[2] to 0.
     • For i = 3, heights[3] = 3:
       • Increment currentHeight to 3 (since count[2] is 0).
       • Compare 3 with 3: Match, result remains 1.
       • Decrement count[3] to 0.
     • For i = 4, heights[4] = 4:
       • Increment currentHeight to 4 (since count[3] is 0).
       • Compare 4 with 4: Match, result remains 1.
       • Decrement count[4] to 0.
     • For i = 5, heights[5] = 8:
       • Increment currentHeight to 5 (since count[4] is 0).
       • Compare 8 with 5: Mismatch, increment result to 2.
       • Decrement count[5] to 0.
     • For i = 6, heights[6] = 1:
       • Increment currentHeight to 8 (since count[5] to count[7] is 0).
       • Compare 1 with 8: Mismatch, increment result to 3.
       • Decrement count[8] to 0.

5. Return Result:

   • The function returns result, which is 3.

Code

Complexity Analysis

Time Complexity

• Counting Heights: We iterate through the heights array once to populate the count array, which takes O(n) time.
• Comparison and Counting: We iterate through the heights array again to compare each height with the expected order, which also takes O(n) time. The inner while loop that increments currentHeight only iterates a constant number of times (at most 100 times, due to the constraints), which does not add significant complexity.
• Thus, the overall time complexity is O(n).

Space Complexity

• The space complexity is O(1) because the count array size is constant (fixed at 101), regardless of the input size due to given constraints. We do not use any additional space that scales with the input size.