LeetCode 1051. Height Checker Solution in Java, C++, Python & More | Explanation + Code

Description

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 <= 100
• 1 <= heights[i] <= 100

Solutions

Solution 1: Sorting

We can first sort the heights of the students, then compare the sorted heights with the original heights, and count the positions that are different.

The time complexity is O(n × log n), and the space complexity is O(n). Where n is the number of students.

PythonJavaC++GoTypeScript

class Solution: def heightChecker(self, heights: List[int]) -> int: expected = sorted(heights) return sum(a != b for a, b in zip(heights, expected))(code-box)

class Solution { public int heightChecker(int[] heights) { int[] expected = heights.clone(); Arrays.sort(expected); int ans = 0; for (int i = 0; i < heights.length; ++i) { if (heights[i] != expected[i]) { ++ans; } } return ans; } }(code-box)

class Solution { public: int heightChecker(vector<int>& heights) { vector<int> expected = heights; sort(expected.begin(), expected.end()); int ans = 0; for (int i = 0; i < heights.size(); ++i) { ans += heights[i] != expected[i]; } return ans; } };(code-box)

func heightChecker(heights []int) (ans int) { expected := slices.Clone(heights) sort.Ints(expected) for i, v := range heights { if v != expected[i] { ans++ } } return }(code-box)

function heightChecker(heights: number[]): number { const expected = [...heights].sort((a, b) => a - b); return heights.reduce((acc, cur, i) => acc + (cur !== expected[i] ? 1 : 0), 0); }(code-box)

Solution 2: Counting Sort

Since the height of the students in the problem does not exceed 100, we can use counting sort. Here we use an array cnt of length 101 to count the number of times each height h_i appears.

The time complexity is O(n + M), and the space complexity is O(M). Where n is the number of students, and M is the maximum height of the students. In this problem, M = 101.

PythonJavaC++GoTypeScript

class Solution: def heightChecker(self, heights: List[int]) -> int: cnt = [0] * 101 for h in heights: cnt[h] += 1 ans = i = 0 for j in range(1, 101): while cnt[j]: cnt[j] -= 1 if heights[i] != j: ans += 1 i += 1 return ans(code-box)

class Solution { public int heightChecker(int[] heights) { int[] cnt = new int[101]; for (int h : heights) { ++cnt[h]; } int ans = 0; for (int i = 0, j = 0; i < 101; ++i) { while (cnt[i] > 0) { --cnt[i]; if (heights[j++] != i) { ++ans; } } } return ans; } }(code-box)

class Solution { public: int heightChecker(vector<int>& heights) { vector<int> cnt(101); for (int& h : heights) ++cnt[h]; int ans = 0; for (int i = 0, j = 0; i < 101; ++i) { while (cnt[i]) { --cnt[i]; if (heights[j++] != i) ++ans; } } return ans; } };(code-box)

func heightChecker(heights []int) int { cnt := make([]int, 101) for _, h := range heights { cnt[h]++ } ans := 0 for i, j := 0, 0; i < 101; i++ { for cnt[i] > 0 { cnt[i]-- if heights[j] != i { ans++ } j++ } } return ans }(code-box)

function heightChecker(heights: number[]): number { const cnt = Array(101).fill(0); for (const i of heights) { cnt[i]++; } let ans = 0; for (let j = 1, i = 0; j < 101; j++) { while (cnt[j]--) { if (heights[i++] !== j) { ans++; } } } return ans; }(code-box)