Sponsored
Sponsored
This approach involves creating an 'expected' array by sorting the given 'heights' array. Once sorted, you compare each element of the original 'heights' array with the corresponding element in the 'expected' array. Count the number of mismatches, which will be your answer.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) to store the 'expected' array.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int heightChecker(vector<int>& heights) {
7 vector<int> expected = heights;
8 sort(expected.begin(), expected.end());
9 int count = 0;
10 for (int i = 0; i < heights.size(); ++i) {
11 if (heights[i] != expected[i]) {
12 count++;
13 }
14 }
15 return count;
16}
17
18int main() {
19 vector<int> heights = {1, 1, 4, 2, 1, 3};
20 cout << heightChecker(heights) << endl;
21 return 0;
22}In C++, the approach is similar to C. We copy 'heights' to 'expected' and sort 'expected'. We then iterate through the arrays to count mismatches.
Given the constraint that heights range between 1 and 100, we can use a counting sort based approach to find deviations from the expected array without explicitly sorting.
Time Complexity: O(n + k) where k is 100 (a constant, heights range). Space Complexity: O(k) for the count array.
1using System;
2
class HeightChecker {
static int HeightCheckerFunc(int[] heights) {
int[] countHeights = new int[101];
foreach (int height in heights) {
countHeights[height]++;
}
int count = 0, currHeight = 0;
foreach (int height in heights) {
while (countHeights[currHeight] == 0) {
currHeight++;
}
if (height != currHeight) {
count++;
}
countHeights[currHeight]--;
}
return count;
}
static void Main() {
int[] heights = { 1, 1, 4, 2, 1, 3 };
Console.WriteLine(HeightCheckerFunc(heights));
}
}In C#, maintain 'countHeights' for each potential height to simulate sorted array and directly check mismatches.