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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void* a, const void* b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int heightChecker(int* heights, int heightsSize) {
9 int expected[heightsSize];
10 for (int i = 0; i < heightsSize; ++i) {
11 expected[i] = heights[i];
12 }
13 qsort(expected, heightsSize, sizeof(int), compare);
14 int count = 0;
15 for (int i = 0; i < heightsSize; ++i) {
16 if (heights[i] != expected[i]) {
17 count++;
18 }
19 }
20 return count;
21}
22
23int main() {
24 int heights[] = {1, 1, 4, 2, 1, 3};
25 int result = heightChecker(heights, sizeof(heights) / sizeof(heights[0]));
26 printf("%d\n", result);
27 return 0;
28}In C, we first copy the original 'heights' array into an 'expected' array. We then sort the 'expected' array using quicksort, provided by the standard library. We iterate over both arrays, counting indices where 'heights[i]' differs from 'expected[i]'.
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.
1function heightChecker
In JavaScript, array 'countHeights' is used to count occurrences of each height, simulating sorting for mismatch counting directly.