Count of Smaller Elements — Asked in Ola and Facebook Interview
Problem Statement :
Given an array of size ’N’ return the count array such that count[i] equals the number of element which are smaller than arr[i] on its the right side.
Sample Input:
N = 5arr = [5 4 3 2 -1]
Sample Output:
4 3 2 1 0Explanation of given Test Cases :
Number of elements smaller than 5 on its right side {4,3,2,-1}
which is 4
Number of elements smaller than 4 on its right side {3,2,-1}
which is 3
Number of elements smaller than 3 on its right side {2,-1}
which is 2
Number of elements smaller than 2 on its right side {-1} which
is 1
Thus answer is [4,3,2,1,0]Approach :
The key idea is similar to merge sort divide the array into two parts until the base case is reached that is when the size is less than or equal to 1.
Algorithm :
- Create a list ‘arr1’ such that ‘arr1[i]’ stores [arr[i],i].Create an ‘ans’ list of size of ’n’ with default value 0.
- Create a recursive function that divides the list ‘arr1’ into two sorted list by the value.
- Create a function merge similar to merge sort one that will merge two sorted list into one.
- In the merge function create two indices i and j, i is the index for the first half, and j is an index of the second half.Create a variable count with a value of 0.if arr1[i][0] greater than arr1[j][0] then do temp++.Else do ans[arr1[i][1] += temp.(Adding the values which are less than arr1[i][0] corresponding to its index) and then do i++.
- After this run a loop until i<mid and do ans[arr[i][1]]+=temp(To update the values for remaining elements.
- In the end, return ans list.
Time Complexity: O(n*log(n))
Space Complexity: O(n)
