Count of Smaller Elements — Asked in Ola and Facebook Interview

Problem Statement :

Sample Input:

N = 5arr = [5 4 3 2 -1]

Sample Output:

4 3 2 1 0

Explanation 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 :

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)

Code :

Thanks for Reading

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

Upskilling students for tech placements!