Katkat
Back

Count Students Outside Their Height-Sorted Positions

Concentric AiSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to compare a given array with its sorted version to identify indices where values do not match, assessing your proficiency in sorting and array indexing.

Problem: Height Mismatch Counter

You are given an array of integers heights representing the heights of students in a single row. The teacher asks the students to stand in non-decreasing order of their heights. You need to return the number of indices i such that heights[i] does not match the value at the same index i in the sorted version of the array.

Function Signature

def count_height_mismatches(heights: List[int]) -> int:

Constraints

  • 1 <= heights.length <= 1000
  • 1 <= heights[i] <= 1000

Examples

Example 1: Input: heights = [1, 1, 4, 2, 1, 3] Output: 3 Explanation:

  • Original: [1, 1, 4, 2, 1, 3]
  • Sorted: [1, 1, 1, 2, 3, 4]
  • Mismatched indices: 2, 4, 5 (values are 4 vs 1, 1 vs 3, 3 vs 4).

Example 2: Input: heights = [5, 1, 2, 3, 4] Output: 5 Explanation:

  • Original: [5, 1, 2, 3, 4]
  • Sorted: [1, 2, 3, 4, 5]
  • Every index is a mismatch.

Edge Cases

  • An array with only one student (should return 0).
  • An array already sorted (should return 0).
  • An array with duplicate values.

Hints

Hint 1

Create a copy of the original array and sort it to represent the desired target configuration.

Hint 2

Iterate through both the original and the sorted arrays simultaneously using a single index.

Hint 3

Increment a counter variable every time the element at the current index in the original array differs from the element at the same index in the sorted array.

Follow-up questions

  • What is the time and space complexity of your solution, and can it be optimized?
  • If the heights were very large numbers (e.g., millions), would your sorting approach still be efficient?
  • How would the logic change if the students were asked to stand in non-increasing order instead?