# Cracking the coding interview: Count Smaller elements — 3

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 = 7

Arr[] = {12, 1, 2, 3, 0, 11, 4}

**Output: **6 1 1 1 0 1 0

**Explanation:** There are 6 elements right

after 12. There are 1 element right after

1. And so on.

**Example 2:**

**Input:**

N = 5

Arr[] = {1, 2, 3, 4, 5}

**Output:** 0 0 0 0 0

**Explanation:** There are 0 elements right

after 1. There are 0 elements right after

2. 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.**