Find count of numbers that are smaller than the current number

Given an array of integers, return a new array containing the count of numbers that are less than the current number.

Assumptions

- array.length >= 1

- Array is unsorted

- Array can contain duplicate numbers

Example

Input: [2,1,9,4,10]

Output: [1,0,3,2,4]

Explanation: Output array is derived as [1 number in array is less than 2, 0 numbers in array are less than 1, 3 numbers in array are less than 9, ...]

Solution 1

1. Maintain a new array - countArray - to store the count of numbers less than the current number.

2. Traverse Array.

3. For each element - traverse array and count the number of elements less than the current element.

4. Add count to countArray.

5. Return countArray.

Code

Complexity

Time Complexity O(N^2) - Since we are travering the array for each element of the array (loop within loop) the time complexity is O(n^2).

Space Complexity O(N) - Since we are maintaing a new array of length N to store the count at each index, the space complexity is O(N).