# Cracking the coding interview: Count Smaller elements — 3

1 min readJul 19, 2022

--

Given an array Arr of size N containing positive integers. Count number of smaller elements on right side of each array.

Example 1:

`Input:N = 7Arr[] = {12, 1, 2, 3, 0, 11, 4}Output: 6 1 1 1 0 1 0Explanation: There are 6 elements rightafter 12. There are 1 element right after1. And so on.`

Example 2:

`Input:N = 5Arr[] = {1, 2, 3, 4, 5}Output: 0 0 0 0 0Explanation: There are 0 elements rightafter 1. There are 0 elements right after2. And so on.`

Your Task:
You don’t need to read input or print anything. Your task is to complete the function constructLowerArray() which takes the array of integers arr and n as parameters and returns an array of integers denoting the answer.

Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)

Constraints:
1 ≤ N ≤ 106
0 ≤ Arri ≤ 108

Solution:

Time complexity: O(n * log n)

Space complexity: O(n)

The strategy of resolving this problem is to apply merge sort algorithm. By creating both add_index_values & count_smaller_value, it performs the separate function of while adding the values and counting it. By starting from the comparison of mid-point values, it satisfies the requirement of the question, which is to make use of time complexity O(n * log n) to resolve the problem.