algoadvance

Leetcode 1051. Height Checker

Problem Statement

The problem “1051. Height Checker” from LeetCode asks us to determine the number of students that are not standing in the correct positions according to their height. We are given a list of integers where each integer represents the height of a student, and the students are standing in a line. The goal is to count how many students need to be moved to make the array sorted in non-decreasing order.

Clarifying Questions

  1. Input Type: Is the input always a list of integers (heights of students)?
    • Yes.
  2. Range and Constraints: What is the range of heights and the number of students?
    • The number of students (length of the input list) is between 1 and 100. The height of any student is between 1 and 100.
  3. Output: Should we return the number of indices at which the elements differ from a sorted version of the list?
    • Yes.
  4. Modifications: Do we need to sort the original list in place?
    • No, we just need to count the discrepancies.

Strategy

  1. Sort the Array: First, we will create a sorted copy of the input list of heights.
  2. Compare: We will compare this sorted array with the original array to count the number of positions where the heights differ.
  3. Count Differences: Iterate through both arrays and count the number of indices where the elements are different.

Code

#include <vector>
#include <algorithm>

int heightChecker(std::vector<int>& heights) {
    // Create a sorted copy of the heights array
    std::vector<int> sortedHeights = heights;
    std::sort(sortedHeights.begin(), sortedHeights.end());
    
    // Count the number of differing positions
    int count = 0;
    for (size_t i = 0; i < heights.size(); ++i) {
        if (heights[i] != sortedHeights[i]) {
            ++count;
        }
    }
    
    return count;
}

Time Complexity

  1. Sorting: Sorting the array will take (O(n \log n)), where (n) is the number of students.
  2. Comparing: Comparing the two arrays will take (O(n)).

Thus, the overall time complexity of the function is (O(n \log n)), which is efficient given the constraints.

Example

Input:

std::vector<int> heights = {1, 1, 4, 2, 1, 3};

Execution:

Output:

int result = heightChecker(heights); // result should be 4

This approach efficiently counts the number of mismatches to determine how many students are out of order.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI