# Count Smaller Elements on the Right Side in Java

The Count Smaller Elements On The Right Side problem is to find the number of smaller elements on the right side of each element in an array.

Example 1:

Input:

{4, 3, 7, 2};

Output:

[2, 1, 1, 0]

Explanation:

For element 4 there are only 2 elements that are 3 and 2 are smaller on the right side hence it’s 2. For element 3 only one element 2 is smaller on the right side that’s why it’s 1 and for seven only 1 element 2 is smaller on the right side hence its 1 and for there is no element on the right side so it’s Zero.

## Approach: Merge Sort algorithm

The program uses the Merge Sort algorithm to count the number of smaller elements on the right side of each element in the input array. The Merge Sort algorithm is a divide-and-conquer sorting algorithm that divides the input array into two halves, sorts each half recursively, and then merges the two sorted halves. In this program, the merge operation has been modified to count the number of smaller elements on the right side of each element while merging the two sorted halves. The counts are accumulated in a list that is passed as an argument to the merge method. Finally, the program returns the list of counts.

FileName: CountSmallerElementsOnTheRightSide.java

```import java.util.*;
public class CountSmallerElementsOnTheRightSide {
public static void main(String[] args) {
int[] nums = {4, 3, 7, 2};
List<Integer> counts = countSmaller(nums);
System.out.println(counts); // output: [2, 1, 1, 0]
}
public static List<Integer> countSmaller(int[] nums) {
int n = nums.length;
// Initialize list of counts with zeros
List<Integer> counts = new ArrayList<Integer>(Collections.nCopies(n, 0));
// Initialize array of indices with values from 0 to n-1
int[] indices = new int[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
// Initialize temporary array for merging
int[] temp = new int[n];
// Call merge sort to sort the array and update the counts
mergeSort(nums, indices, temp, counts, 0, n-1);
// Return list of counts
return counts;
}
public static void mergeSort(int[] nums, int[] indices, int[] temp, List<Integer> counts, int start, int end) {
if (start >= end) {
// Base case: array has one or fewer elements, no need to sort
return;
}
// Divide array in two and sort each half recursively
int mid = (start + end) / 2;
mergeSort(nums, indices, temp, counts, start, mid);
mergeSort(nums, indices, temp, counts, mid+1, end);
// Merge two sorted subarrays and update counts
merge(nums, indices, temp, counts, start, end);
}
public static void merge(int[] nums, int[] indices, int[] temp, List<Integer> counts, int start, int end) {
int mid = (start + end) / 2;
int i = start, j = mid+1, k = start;
while (i <= mid && j <= end) {
if (nums[indices[i]] <= nums[indices[j]]) {
// If element in left subarray is smaller or equal to element in right subarray,
// it has j-mid-1 smaller elements to its right
counts.set(indices[i], counts.get(indices[i]) + j - mid - 1);
temp[k++] = indices[i++];
} else {
// If element in left subarray is larger than element in right subarray,
// no updates to counts are needed
temp[k++] = indices[j++];
}
}
// Copy remaining elements from left subarray
while (i <= mid) {
counts.set(indices[i], counts.get(indices[i]) + j - mid - 1);
temp[k++] = indices[i++];
}
// Copy remaining elements from right subarray
while (j <= end) {
temp[k++] = indices[j++];
}
// Copy merged subarray back to original array
for (int p = start; p <= end; p++) {
indices[p] = temp[p];
}
}
}
```

Output:

`[2, 1, 1, 0]`

Complexity

The time complexity of the program is O(n log n), where n is the length of the input array. This is because the program uses the Merge Sort algorithm, which has a time complexity of O(n log n).

The space complexity of the program is O(n), where n is the length of the input array. This is because the program creates several arrays and lists to store intermediate results during the sorting process, and the sizes of these arrays and lists are proportional to the size of the input array. However, the space complexity could be improved by using an in-place merge sort algorithm or a different data structure to store intermediate results.

## Approach: Binary Indexed Tree (BIT)

The code above is an implementation of the "Count of Smaller Numbers After Self" problem using a Binary Indexed Tree (BIT) approach. The code takes an integer array as input and returns a list of integers representing the number of elements smaller than the current element in the array.

The main method initializes the input array "nums", calls the countSmaller method passing "nums" as an argument, and prints the result. The countSmaller method creates a copy of the "nums" array and sorts it in ascending order. It also initializes a BIT array of size n+1, where n is the length of the input array. Finally, it initializes an empty ArrayList called "counts" that will store the final result.

The countSmaller method then iterates through the input array in reverse order, which means it starts from the last element and goes to the first. For each element in the input array, it finds its rank by performing a binary search on the sorted array and adding 1 to the result. The rank represents the number of elements smaller than the current element in the sorted array.

It then adds the count of smaller elements to the beginning of the "counts" ArrayList using the "add(0, count)" method, where "count" is the sum obtained by calling the "getSum" method on the BIT array with the rank-1 as the input. Finally, it updates the BIT array by calling the "update" method with the rank as the input.

The "update" method updates the BIT array by adding 1 to the value at the input index and moving to the next index by performing bitwise AND with the two's complement of the current index.

The "getSum" method calculates the sum of all the values in the BIT array from index 1 to the input index. It starts with a sum of 0 and iteratively adds the value at the current index to the sum while moving to the previous index by performing bitwise AND with the two's complement of the current index.

FileName: CountSmallerElementsOnTheRightSide.java

```import java.util.*;
public class CountSmallerElementsOnTheRightSide {
public static void main(String[] args) {
int[] nums = {4, 3, 7, 2};
List<Integer> counts = countSmaller(nums);
System.out.println(counts); // output: [2, 1, 1, 0]
}
public static List<Integer> countSmaller(int[] nums) {
int n = nums.length;
// create a copy of the input array and sort it
int[] sortedNums = nums.clone();
Arrays.sort(sortedNums);
// create a Binary Indexed Tree (BIT) to store the frequency of numbers
int[] bit = new int[n + 1];
// create a list to store the counts of smaller elements on the right side
List<Integer> counts = new ArrayList<>();
// iterate over the input array from right to left
for (int i = n - 1; i >= 0; i--) {
// find the rank of the current element in the sorted array
// by performing binary search and adding 1 to the result
int rank = Arrays.binarySearch(sortedNums, nums[i]) + 1;
// get the sum of frequencies of numbers with rank less than the current element
// and add it to the front of the counts list
// update the frequency of the current element in the BIT
update(bit, rank);
}
return counts;
}
// update the frequency of a number in the BIT
private static void update(int[] bit, int index) {
while (index < bit.length) {
bit[index]++;
index += (index & -index);
}
}
// get the sum of frequencies of numbers with rank less than a given rank from the BIT
private static int getSum(int[] bit, int index) {
int sum = 0;
while (index > 0) {
sum += bit[index];
index -= (index & -index);
}
return sum;
}
}
```

Output:

`[2, 1, 1, 0]`

Complexity:

The time complexity of this implementation is O(n log n), which is the time complexity of sorting the input array. The space complexity is O(n), which is the space required to store the input array, the sorted array, the BIT, and the result list.