Problem Description

You have a line of students who need to be arranged for a school photo. The students should stand in a single line ordered by their heights from shortest to tallest (or equal heights can be in any order among themselves). This is called non-decreasing order.

You're given an array heights that shows the current order of students in line, where heights[i] represents the height of the student at position i (using 0-based indexing).

Your task is to figure out how many students are standing in the wrong position. A student is in the wrong position if their current position differs from where they should be when the line is properly sorted by height.

For example:

• If heights = [1, 1, 4, 2, 1, 3]
• The properly sorted order would be [1, 1, 1, 2, 3, 4]
• Comparing position by position:
  • Position 0: 1 = 1 ✓ (correct)
  • Position 1: 1 = 1 ✓ (correct)
  • Position 2: 4 ≠ 1 ✗ (wrong)
  • Position 3: 2 = 2 ✓ (correct)
  • Position 4: 1 ≠ 3 ✗ (wrong)
  • Position 5: 3 ≠ 4 ✗ (wrong)
• Total students in wrong positions: 3

The solution approach is straightforward: create a sorted version of the heights array (this represents where students should be standing), then compare it with the original array and count how many positions have different values. The code uses sorted(heights) to get the expected arrangement and then counts mismatches using a generator expression with sum() and zip() to compare corresponding positions.

Intuition

The key insight is recognizing that we need to compare the current arrangement with the ideal arrangement. When students are asked to line up by height in non-decreasing order, there's only one correct arrangement possible - the sorted order.

Think of it this way: if we know what the line should look like (sorted by height) and what it currently looks like, we can simply compare these two arrangements position by position. Any position where the heights don't match means a student is standing in the wrong spot.

The problem essentially boils down to asking: "How different is the current arrangement from the sorted arrangement?" We don't need to actually move students or track which student goes where - we just need to count the differences.

Why does this work? Because when we sort the heights array, we get the "expected" positions for each height value. If a student at position i has a different height than what should be at position i in the sorted array, that student needs to move.

For instance, if we see a tall student at the beginning of the line where a short student should be, we know that position is wrong. By sorting the array and comparing it with the original, we identify all such misplaced positions.

The elegance of this approach lies in its simplicity - rather than trying to simulate the rearrangement process or track individual student movements, we just create the target state (sorted array) and count the mismatches. Each mismatch represents a student who isn't where they should be in the properly ordered line.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward sorting and comparison strategy:

Step 1: Create the Expected Arrangement

expected = sorted(heights)

We use Python's built-in sorted() function to create a new list containing all the heights in non-decreasing order. This represents where each student should be standing. The sorted() function returns a new list, leaving the original heights array unchanged.

Step 2: Compare and Count Differences

return sum(a != b for a, b in zip(heights, expected))

This line does several things efficiently:

1. zip(heights, expected) - Pairs up elements from both arrays at corresponding positions. For example, if heights = [1, 2, 3] and expected = [1, 3, 2], then zip() produces pairs: (1,1), (2,3), (3,2).

2. a != b for a, b in ... - This is a generator expression that compares each pair. For each position, it evaluates to True (which equals 1 in Python) if the heights are different, or False (which equals 0) if they're the same.

3. sum(...) - Adds up all the boolean values. Since True = 1 and False = 0, this effectively counts how many positions have mismatched heights.

Time Complexity: O(n log n) where n is the number of students. The sorting operation dominates the time complexity.

Space Complexity: O(n) for storing the sorted array expected.

The beauty of this solution is its conciseness - in just two lines, we create the target state and count the differences. The use of zip() and a generator expression makes the comparison elegant and memory-efficient, as it doesn't create an intermediate list of comparison results.

Example Walkthrough

Let's walk through a small example with heights = [2, 1, 3, 1, 2].

Step 1: Create the Expected Arrangement

First, we sort the heights to get the proper order:

• Original: [2, 1, 3, 1, 2]
• Sorted: [1, 1, 2, 2, 3]

This sorted array represents where students should be standing - shortest to tallest.

Step 2: Compare Position by Position

Now we compare each position using zip(heights, expected):

Step 3: Count the Mismatches

The comparison a != b produces:

• Position 0: 2 != 1 → True (counts as 1)
• Position 1: 1 != 1 → False (counts as 0)
• Position 2: 3 != 2 → True (counts as 1)
• Position 3: 1 != 2 → True (counts as 1)
• Position 4: 2 != 3 → True (counts as 1)

Using sum() on these boolean values: 1 + 0 + 1 + 1 + 1 = 4

Result: 4 students are standing in the wrong positions and need to move for the photo to be properly arranged by height.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorted() function, which uses Timsort algorithm with a time complexity of O(n × log n) where n is the number of elements in the heights list. The subsequent operations - zip() and sum() with comparison - both take O(n) time, but since O(n × log n) + O(n) = O(n × log n), the overall time complexity remains O(n × log n).

Space Complexity: O(n)

The space complexity is O(n) because the sorted() function creates a new list called expected that contains all n elements from the original heights list. The zip() operation creates an iterator that doesn't require additional space proportional to the input size, and the generator expression in sum() processes elements one at a time without storing them all in memory.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Attempting to Sort In-Place

A common mistake is trying to sort the original array in-place and then comparing it with itself, which would always result in 0 mismatches:

Incorrect Approach:

def heightChecker(self, heights: List[int]) -> int:
    original = heights  # This doesn't create a copy!
    heights.sort()      # Sorts in-place, modifying the original
    return sum(a != b for a, b in zip(original, heights))  # Always returns 0

Why it fails: In Python, original = heights creates a reference to the same list object, not a copy. When heights.sort() is called, both original and heights point to the same sorted list.

Solution: Always create a copy when you need to preserve the original order:

def heightChecker(self, heights: List[int]) -> int:
    original = heights.copy()  # Or heights[:] or list(heights)
    sorted_heights = sorted(heights)  # Or use this to create a new sorted list
    return sum(a != b for a, b in zip(original, sorted_heights))

Pitfall 2: Misunderstanding the Problem - Counting Unique Heights

Some might misinterpret the problem as counting how many distinct heights are out of order:

Incorrect Interpretation:

def heightChecker(self, heights: List[int]) -> int:
    # Wrong: Counting unique values that are misplaced
    return len(set(heights) - set(sorted(heights)))  # This is incorrect!

Why it fails: The problem asks for the number of positions (indices) where students are wrong, not the number of unique heights that are misplaced. If heights = [1, 1, 4, 2, 1, 3], we need to count 3 positions that are wrong, not unique values.

Solution: Stick to position-by-position comparison as shown in the correct implementation.

Pitfall 3: Off-by-One Errors When Manually Iterating

When implementing the comparison loop manually, indexing errors are common:

Error-Prone Approach:

def heightChecker(self, heights: List[int]) -> int:
    expected = sorted(heights)
    count = 0
    for i in range(len(heights) + 1):  # Wrong: goes beyond array bounds
        if heights[i] != expected[i]:
            count += 1
    return count

Solution: Use zip() to avoid index management entirely, or ensure proper range bounds:

# Better: Let zip handle the pairing
return sum(a != b for a, b in zip(heights, sorted(heights)))

# Or if using indices, ensure correct range
for i in range(len(heights)):  # Correct range
    if heights[i] != expected[i]:
        count += 1