algoadvance

Leetcode 1051. Height Checker

Problem Statement

A school is trying to take an annual photo of all the students. The students are asked to stand in a single line in non-decreasing order by height. Let’s assume that heights are represented by an integer array. You need to return the number of indices where the heights do not match the expected heights.

Clarifying Questions

1. Input Constraints:
   • What is the range of the heights that can be provided? Usually, heights fall between a certain range, such as 1 to 100.
   • Can the height array be empty?
2. Expected Output:
   • Should I return the number of positions that do not match or the positions themselves?

Strategy

1. Initial Approach:
   • Clone the original array.
   • Sort the cloned array.
   • Compare each element of the original array with the sorted array and count the indices where the elements differ.

Code

public class HeightChecker {
    public int heightChecker(int[] heights) {
        // Create a copy of the original array
        int[] expected = heights.clone();
        // Sort the copied array
        Arrays.sort(expected);
        
        int mismatchCount = 0;
        // Compare the original array to the sorted array
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != expected[i]) {
                mismatchCount++;
            }
        }
        
        return mismatchCount;
    }

    public static void main(String[] args) {
        HeightChecker hc = new HeightChecker();
        int[] heights = {1,1,4,2,1,3};
        System.out.println(hc.heightChecker(heights)); // Output: 3
    }
}

Strategy Explanation

1. Clone and Sort:
   • Cloning the original array helps to retain the original sequence before sorting.
   • Sorting the clone provides the expected sequence if the students were standing in non-decreasing order by height.
2. Comparison:
   • By comparing each student’s height in the original array to the sorted array, we can determine the exact number of mismatches.

Time Complexity

• Cloning and Sorting:
  • Cloning the array takes O(n), where n is the number of students.
  • Sorting the array takes O(n log n).
• Comparison:
  • Comparing the original array to the sorted array takes O(n).

Thus, the overall time complexity is dominated by the sorting step, which is O(n log n).

Considerations

• Edge cases:
  • If the array is empty, the script should handle that properly, but generally, no mismatches would occur.
  • Ensure that the function handles different array lengths efficiently.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?