
Problem Statement
In an attempt to organize an annual school photograph, students are instructed to line up in a single file where their heights are ordered in a non-decreasing sequence. The desired order of students by height is conveyed through an integer array expected
, where expected[i]
refers to the height expected for the i-th
student in the lineup.
However, there remains a complication. Students are initially standing in an order represented by another integer array, heights
, where heights[i]
corresponds to the actual height of the i-th
student as they currently stand.
The task at hand is to determine how many students are standing out of the expected order. Specifically, the challenge is to return the number of indices i
for which the height of the student at heights[i]
does not match the height at expected[i]
.
This problem entails a direct comparison between the given ordering of heights and a sorted version of the same array to identify mismatches, thereby pinpointing students who are out of the desired sequential order.
Examples
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
Approach and Intuition
To solve the problem effectively:
- Begin by sorting the
heights
array to generate theexpected
array which is the correct non-decreasing order of student heights. - Initialize a counter to zero. This will be used to keep track of indices where discrepancies occur.
- Compare the sorted
heights
array (now equivalent toexpected
) with the originalheights
array using a loop:- For each index, check if the value in the sorted array differs from the value in the original array.
- If they do differ, increment the counter by one.
- Return the total count of these discrepancies, which represents the number of students out of place.
The essence of this approach is leveraging the ability to sort and directly compare arrays to find element-wise mismatches. The constraints are manageable, allowing efficient execution of sorting operations and comparisons within the given limits. This method ensures each misplacement is counted accurately, culminating in the total number of students who need to adjust their position in line to fulfill the expected order.
Solutions
- C++
- Java
- Python
class Solution {
// Function to sort using a specific digit
void sortOnDigit(vector<int>& nums, int digitFactor) {
vector<vector<int>> storage(10, vector<int>());
for (int& number : nums) {
int digit = abs(number) / digitFactor % 10;
storage[digit].push_back(number);
}
int position = 0;
for (int index = 0; index < 10; ++index) {
for (int& item : storage[index]) {
nums[position++] = item;
}
}
}
// Function to perform radix sort
void performRadixSort(vector<int>& nums) {
int maxVal = nums[0];
for (int& number : nums) {
maxVal = max(abs(number), maxVal);
}
int totalDigits = 0;
while (maxVal > 0) {
totalDigits++;
maxVal /= 10;
}
int currentPlace = 1;
for (int digit = 0; digit < totalDigits; ++digit) {
sortOnDigit(nums, currentPlace);
currentPlace *= 10;
}
}
public:
int heightChecker(vector<int>& heights) {
vector<int> expected = heights;
performRadixSort(expected);
int mismatches = 0;
for (size_t i = 0; i < expected.size(); ++i) {
if (heights[i] != expected[i]) {
mismatches++;
}
}
return mismatches;
}
};
The provided C++ code defines a solution to the problem of counting how many elements in an array differ from their position in a sorted version of the array. The class Solution
features two main functionalities:
Radix Sort Implementation:
sortOnDigit
method handles sorting based on individual digitsperformRadixSort
method manages the full process of radix sorting through multiple passes, determined by the number of digits in the largest number.
Height Checking:
heightChecker
method first copies theheights
vector to a new vectorexpected
, then sortsexpected
using theperformRadixSort
method. It then compares elements in the originalheights
vector with the sortedexpected
vector, counts discrepancies, and returns this count.
By decomposing the task into sorting the array independently and then comparing it with the original order, the solution provides a clean and efficient way to determine the number of out-of-order height placements, leveraging the efficiency and stability of the radix sort algorithm.
class Solution {
// Helper function to sort numbers by individual digits
private void digitSort(int[] array, int exp) {
List<List<Integer>> bucket = new ArrayList<>(10);
for (int j = 0; j < 10; j++) {
bucket.add(new ArrayList<>());
}
// Distribute numbers based on current digit
for (int number : array) {
int digit = (Math.abs(number) / exp) % 10;
bucket.get(digit).add(number);
}
// Collect back to original array
int position = 0;
for (int k = 0; k < 10; k++) {
for (int value : bucket.get(k)) {
array[position] = value;
position++;
}
}
}
// Sorting function using digit-by-digit sorting
private void sortDigits(int[] data) {
// Determine the number of digits in the largest number
int maximum = Arrays.stream(data).map(Math::abs).max().getAsInt();
int maxDigits = 0;
for (; maximum > 0; maxDigits++, maximum /= 10);
// Sort for each digit
for (int pos = 1, digit = 0; digit < maxDigits; digit++, pos *= 10) {
digitSort(data, pos);
}
}
public int heightChecker(int[] heights) {
// Clone and sort the array heights
int[] expected = heights.clone();
sortDigits(expected);
// Count mismatches between original and sorted arrays
int mismatchCount = 0;
for (int i = 0; i < expected.length; i++) {
if (heights[i] != expected[i]) mismatchCount++;
}
// Return the count of heights that are out of order
return mismatchCount;
}
}
The provided Java solution defines a method to determine how many heights are out of order from their original positions after sorting. Here's a breakdown of the approach and components of the code:
- A
digitSort
function sorts numbers based on individual digits from least significant to most significant. This function uses a bucket sort algorithm, where numbers are distributed into buckets based on their current significant digit and then collected back in order. - The
sortDigits
function leverages thedigitSort
to sort an entire array by iterating through each digit of the maximum value in the array. This ensures a complete and correct sort using digit-wise comparison. - Inside the
heightChecker
method:- The original
heights
array is cloned toexpected
. - The
expected
array is sorted using thesortDigits
method. - The number of positions where the sorted array (
expected
) doesn't match the originalheights
array is counted. - This count is then returned, representing the number of heights in the wrong positions relative to a sorted list.
- The original
The result from heightChecker
shows the degree of mismatch, offering a clear metric of how many elements (heights) are out of order. This solution smartly applies a non-comparison-based sort, bucket sort, adapted for numerical sorting via digit manipulation, which is both efficient and appropriate for the problem context.
class Solution:
# Organize numbers in buckets based on their digits.
def digit_bucket_sort(self, nums, digit_place):
container = [[] for _ in range(10)]
# Distribute the numbers based on the current digit.
for value in nums:
index = abs(value) // digit_place % 10
container[index].append(value)
# Consolidate elements back to the list in sorted manner.
position = 0
for bucket_index in range(10):
for item in container[bucket_index]:
nums[position] = item
position += 1
# Main method for sorting using Radix sort by digit.
def digit_radix_sort(self, nums):
# Determine the maximum number of digits.
maximum, num_digits = max(abs(x) for x in nums), 0
while maximum:
num_digits += 1
maximum //= 10
# Sort from least significant to most significant digit.
base_place = 1
for _ in range(num_digits):
self.digit_bucket_sort(nums, base_place)
base_place *= 10
def heightChecker(self, heights: List[int]) -> int:
# Sort heights using radix sort.
expected_order = list(heights)
self.digit_radix_sort(expected_order)
# Count mismatches between the sorted and the original list.
mismatch_count = 0
for i in range(len(expected_order)):
if heights[i] != expected_order[i]:
mismatch_count += 1
# Return the number of students not in the expected positions.
return mismatch_count
This Python solution employs a sophisticated digit-based Radix sort algorithm to address the problem of determining how many students are not in their expected height order. Follow the detailed breakdown below to understand the implementation:
Radix Sort Mechanism:
- Initialize a
digit_radix_sort
method that sorts an array of integers. This method uses thedigit_bucket_sort
repeatedly, each time sorting the numbers based on an increasing significant digit (from least to most significant). - Digit-Wise Distribution:
- In the
digit_bucket_sort
method, numbers are distributed into buckets based on their current digit value. This distribution utilizes the modulus operation and integer division to isolate digit values.
- In the
- Collection From Buckets:
- After distribution, numbers are collected back from the buckets in order maintaining their sorted condition with respect to the current digit.
- Initialize a
Height Checker Function:
- This function uses the
digit_radix_sort
to sort theheights
list and then assigns it toexpected_order
. - It iterates over the sorted
expected_order
and the originalheights
list simultaneously to count the mismatches, hence identifying students standing out of the expected ascending height order.
- This function uses the
Count Mismatches:
- The method finally returns the total number of positions where the original list of heights does not match the sorted
expected_order
list, indicating the number of students out of place.
- The method finally returns the total number of positions where the original list of heights does not match the sorted
By using Radix sort, the solution effectively handles the sorting process without relying on comparison-based sorting methods, which often have higher time complexities for larger input sizes. This approach is efficient, especially when dealing with non-negative integers in the list.
No comments yet.