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.
1using System;
2using System.Linq;
3
4class HeightChecker {
5 static int HeightCheckerFunc(int[] heights) {
6 int[] expected = (int[])heights.Clone();
7 Array.Sort(expected);
8 int count = 0;
9 for (int i = 0; i < heights.Length; i++) {
10 if (heights[i] != expected[i]) {
11 count++;
12 }
13 }
14 return count;
15 }
16
17 static void Main() {
18 int[] heights = { 1, 1, 4, 2, 1, 3 };
19 Console.WriteLine(HeightCheckerFunc(heights));
20 }
21}In C#, use 'Clone()' to duplicate 'heights' and 'Array.Sort()' to sort it. Iterate to find elements where 'heights' and 'expected' mismatch and count them.
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.
1#include
In C, maintain an array 'countHeights' to track frequency of each height from 1 to 100. Use this to simulate creating a sorted version of 'heights' without actually sorting, while counting mismatches directly.