Problem Description
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i]. Return the answer in an array.
Key Insights
- For each element in the array, we need to compare it with every other element.
- The problem can be efficiently solved using sorting techniques or counting sort due to the bounded range of values.
- A direct approach would involve nested loops, leading to O(n^2) time complexity.
Space and Time Complexity
Time Complexity: O(n^2) (brute-force approach) or O(n log n) (using sorting)
Space Complexity: O(n) (for the output array)
Solution
To solve this problem, we can utilize sorting to determine the ranks of each number in the original array. We can create a sorted version of the array and then use a hash map or an array to store the count of how many numbers are smaller than each unique number. Finally, we can construct the result array based on this information.