Problem

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 ith 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 ith student in line (0-indexed).

Return the number of indices where heights[i] != expected[i].

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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

Method 1 - Using sorting

Intuition

  • Use a sorting algorithm to obtain the expected order of heights.
  • Compare each element of the sorted array with the original array.

Approach

  • Sort the original array, storing it in a new variable.
  • Iterate through both arrays (original and sorted) simultaneously, counting the indices where values differ.
  • This approach works efficiently due to the relatively small constraint on the range of heights.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int heightChecker(int[] heights) {
        int[] expected = heights.clone();
        Arrays.sort(expected);
        int count = 0;
        for(int i = 0; i < expected.length; i++){
            if(heights[i]!=expected[i]){
	            count++;
	        }
        }
        return count;
    }
}
1
2
3
4

class Solution:
  def heightChecker(self, heights: list[int]) -> int:
    expected = sorted(heights)
    return sum(h != e for h, e in zip(heights, expected))

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method 2 - Using Bucketsort

Look at the constraints, we have just 100 elements at max in array. So, we can use bucketsort, with only 100 buckets to sort the array. This will reduce our sorting time complexity to O(n).

Now, one way can be we create a new sorted array based on this, and do the comparisons as in method 1.

But, what we can also do is - we use 2 pointers on heights and buckets - say i and j.

We find the non-zero height in the bucket. If it is not equal to ith height. If they don’t match, then we found one non matching height, and increment i, and reduce the count in buckets.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int heightChecker(int[] heights) {
        int[] buckets = new int[101];
        
        for (int h : heights) {
            buckets[h]++;
        }
        
        int ans = 0, j = 1;
        
        for (int i = 0; i < heights.length; i++) {
	        
            while (buckets[j] == 0) {
	            ++j;
            }
            
            if (j != heights[i]) {
                ++ans;
            }
            
            buckets[j]--;
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
  def heightChecker(self, heights: list[int]) -> int:
    buckets = [0] * 101
    for h in heights:
      buckets[h] += 1
    ans = 0
    j = 1
    for i in range(len(heights)):
      while buckets[j] == 0:
        j += 1
      if heights[i] != j:
        ans += 1
      buckets[j] -= 1
    return ans

Dry Run

1. Fill the buckets
1
2
3

index   =  0  1  2  3  4  5  6  7 ... 100
heights = [1, 1, 4, 2, 1, 3]
buckets = [0, 3, 1, 1, 1, 0 ....        0]
Initiate the counters

i = 0 j = 0 ans = 0

i = 0
1
2
3
4

heights[i] = 1, j = 1

 j is 1, which matches heights[0], ans remains 0.
 Decrement bucket[j] -> bucket[1] = 2
i = 1
1
2
3
4

 i = 1 (heights[1] = 1), j (r still expecting 1)
 While bucket[j] is not zero, so continue.
 j is 1, which matches heights[1], ans remains 0.
 Decrement bucket[j] -> bucket[1] = 1
i = 2
1
2
3
4

 i = 2 (heights[2] = 4), j (still expecting 1)
 While bucket[j] is not zero, so continue.
 j is 1, which does not match heights[2], increment ans to 1.
 Decrement bucket[j] -> bucket[1] = 0
i = 3
1
2
3
4

 i = 3 (heights[3] = 2), j (expecting 2 now because bucket[1] is zero)
 While bucket[j] is zero, increment j to 2.
 j is 2, which matches heights[3], ans remains 1.
 Decrement bucket[j] -> bucket[2] = 0
i = 4
1
2
3
4

 i = 4 (heights[4] = 1), j (expecting 3 now because bucket[2] is zero)
 While bucket[j] is zero, increment j to 3.
 j is 3, which does not match heights[4], increment ans to 2.
 Decrement bucket[j] -> bucket[3] = 0
i = 5
1
2
3
4

 i = 5 (heights[5] = 3), j (expecting 4 now because bucket[3] is zero)
 While bucket[j] is zero, increment j to 4.
 j is 4, which does not match heights[5] (which is 3), increment ans to 3.
 Decrement bucket[j] -> bucket[4] = 0
Final Result

The loop has finished, and we found three instances where the current height did not match the expected height. So, ans = 3.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)