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

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;
    }
}

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;
    }
}

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

Complexity

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