703434. Count of smaller elements
Count of Smaller Elements
Slug: count-of-smaller-elements5947 Difficulty: Basic Id: 703434 Topic Tags: Arrays, Data Structures Company Tags: None
Summary
The problem involves counting the number of elements in a given array that are smaller than each element. This requires comparing each element with all other elements to count how many are less than it.
Detailed Explanation
The approach is straightforward: iterate through the array and for each element, compare it with all other elements to its right (or left). Count the number of elements that are less than the current element. This will give us the total count of smaller elements.
Here's a step-by-step breakdown:
- Initialize an empty vector
ansto store the counts. - Iterate through the array from left to right.
- For each element, iterate through the remaining elements (from right to left).
- Compare the current element with each remaining element. If it is smaller, increment the count in
ans. - Return
ans.
Time complexity: O(n^2), where n is the size of the array. This is because for each element, we are iterating through the rest of the array. Space complexity: O(n), as we need to store the counts in a vector.
Optimized Solutions
Java
public int[] countSmaller(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i]) {
ans[i]++;
}
}
}
return ans;
}