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
 counts.add(0, getSum(bit, rank - 1));
 // 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.