Given an array arr containing positive integers. Count and return an array ans where ans[i] denotes the number of smaller elements on right side of arr[i].
Examples:
Input: arr[] = {12, 1, 2, 3, 0, 11, 4}
Output: 6 1 1 1 0 1 0
Explanation: There are 6 smaller elements right
after 12. There is 1 smaller element right after
1. And so on.
Input: arr[] = {1, 2, 3, 4, 5}
Output: 0 0 0 0 0
Explanation: There are 0 smaller elements right
after 1. There are 0 smaller elements right after
2. And so on.
Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ arr.size() ≤ 106
0 ≤ arr[i] ≤ 108
Approach 01:
-
C++
-
Python
class Solution {
public:
// Helper function to merge two halves and count smaller elements
void mergeAndCount(vector<int>& indices, int left, int mid, int right, vector<int>& smallerElementsCount, vector<int>& nums) {
vector<int> tempIndices(right - left + 1);
int i = left; // Pointer for the left subarray
int j = mid + 1; // Pointer for the right subarray
int k = 0; // Pointer for the merged array
int count = 0; // Counter for the smaller elements
// Merge the two subarrays while counting smaller elements
while (i <= mid && j <= right) {
if (nums[indices[i]] <= nums[indices[j]]) {
tempIndices[k] = indices[j];
j++;
} else {
smallerElementsCount[indices[i]] += right - j + 1; // Count the number of smaller elements
tempIndices[k] = indices[i];
i++;
}
k++;
}
// Copy the remaining elements of the left subarray
while (i <= mid) {
tempIndices[k++] = indices[i++];
}
// Copy the remaining elements of the right subarray
while (j <= right) {
tempIndices[k++] = indices[j++];
}
// Update the original indices array with the merged result
for (int i = left; i <= right; i++) {
indices[i] = tempIndices[i - left];
}
}
// Helper function to perform merge sort and count smaller elements
void mergeSortAndCount(vector<int>& indices, int left, int right, vector<int>& smallerElementsCount, vector<int>& nums) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSortAndCount(indices, left, mid, smallerElementsCount, nums);
mergeSortAndCount(indices, mid + 1, right, smallerElementsCount, nums);
mergeAndCount(indices, left, mid, right, smallerElementsCount, nums);
}
}
// Main function to construct the array of smaller elements count
vector<int> constructLowerArray(vector<int>& nums) {
int n = nums.size();
vector<int> smallerElementsCount(n, 0); // Initialize the result array with zeros
vector<int> indices(n); // Initialize the indices array
// Fill the indices array with values from 0 to n-1
for (int i = 0; i < n; i++) {
indices[i] = i;
}
// Perform merge sort and count the smaller elements
mergeSortAndCount(indices, 0, n - 1, smallerElementsCount, nums);
return smallerElementsCount;
}
};
class Solution:
# Helper function to merge two halves and count smaller elements
def mergeAndCount(self, indices, left, mid, right, smallerElementsCount, nums):
tempIndices = [0] * (right - left + 1)
i = left # Pointer for the left subarray
j = mid + 1 # Pointer for the right subarray
k = 0 # Pointer for the merged array
# Merge the two subarrays while counting smaller elements
while i <= mid and j <= right:
if nums[indices[i]] <= nums[indices[j]]:
tempIndices[k] = indices[j]
j += 1
else:
smallerElementsCount[indices[i]] += right - j + 1 # Count the number of smaller elements
tempIndices[k] = indices[i]
i += 1
k += 1
# Copy the remaining elements of the left subarray
while i <= mid:
tempIndices[k] = indices[i]
i += 1
k += 1
# Copy the remaining elements of the right subarray
while j <= right:
tempIndices[k] = indices[j]
j += 1
k += 1
# Update the original indices array with the merged result
for i in range(left, right + 1):
indices[i] = tempIndices[i - left]
# Helper function to perform merge sort and count smaller elements
def mergeSortAndCount(self, indices, left, right, smallerElementsCount, nums):
if left < right:
mid = left + (right - left) // 2
self.mergeSortAndCount(indices, left, mid, smallerElementsCount, nums)
self.mergeSortAndCount(indices, mid + 1, right, smallerElementsCount, nums)
self.mergeAndCount(indices, left, mid, right, smallerElementsCount, nums)
# Main function to construct the array of smaller elements count
def constructLowerArray(self, nums):
n = len(nums)
smallerElementsCount = [0] * n # Initialize the result array with zeros
indices = list(range(n)) # Initialize the indices array
# Perform merge sort and count the smaller elements
self.mergeSortAndCount(indices, 0, n - 1, smallerElementsCount, nums)
return smallerElementsCount
Time Complexity
- Merge Sort:
The
mergeSortAndCountfunction performs merge sort, which has a time complexity of \( O(n \log n) \). During the merge process, we count the smaller elements on the right side for each element, which takes \( O(n) \) time in each level of the merge process. Since there are \( \log n \) levels, the total time complexity for this part is \( O(n \log n) \). - Overall Time Complexity:
The overall time complexity is \( O(n \log n) \).
Space Complexity
- Auxiliary Space for Temporary Arrays:
The algorithm uses temporary arrays
tempIndicesin themergeAndCountfunction, which takes \( O(n) \) space. - Space for Indices and Count Arrays:
The
indicesandsmallerElementsCountarrays also use \( O(n) \) space. - Overall Space Complexity:
The overall space complexity is \( O(n) \) due to the temporary arrays and the additional arrays used in the algorithm.