Algorithm
Problem Name: 1051. Height Checker
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].
Example 1:
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:
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:
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 <= 1001 <= heights[i] <= 100
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int heightChecker(int[] heights) {
int[] frequencies = new int[101];
for (int height : heights) {
frequencies[height]++;
}
int currHeight = 1;
int mismatchCount = 0;
for (int height : heights) {
while (frequencies[currHeight] == 0) {
currHeight++;
}
if (currHeight != height) {
mismatchCount++;
}
frequencies[currHeight]--;
}
return mismatchCount;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const heightChecker = function(heights) {
const arr = heights.slice(0).sort((a, b) => a - b)
let res = 0
for(let i = 0, len = heights.length; i < len; i++) {
if(arr[i] !== heights[i]) res++
}
return res
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def heightChecker(self, heights: List[int]) -> int:
return sum(h1 != h2 for h1, h2 in zip(heights, sorted(heights)))
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _1051_HeightChecker
{
public int HeightChecker(int[] heights)
{
var sortedHeights = new int[heights.Length];
heights.CopyTo(sortedHeights, 0);
Array.Sort(sortedHeights);
var count = 0;
for (int i = 0; i < heights.Length; i++)
{
if (heights[i] != sortedHeights[i])
count++;
}
return count;
}
}
}
Input
Output