Number of Smaller Elements on Right Side

Problem Statement

In the “Number of Smaller Elements on Right Side” problem, we have given an array a[]. Find the number of smaller elements that are on the right_side of each element.

Input Format

The first and only one line containing an integer N.

Second-line containing N space-separated integers.

Output Format

The first and only one line containing n space-separated integers where integer at ith position denotes the number of smaller_elements that are on the right_side of the index element.

Constraints

• 1<=N<=10^5
• 1<=a[i]<=10^5

Example

5
4 10 6 2 1

2 3 2 1 0

Explanation: In the above example, the output array contains the number of smaller_elements that are on their right side.

Approach

Use the idea of the merge sort at the time of merging two arrays. When higher index element is less than the lower index element, it represents that the higher index element is smaller than all the elements after that lower index because the left part is already sorted. Hence add up to all the elements after the lower index element for the required count.

Implementation

C++ Program for Number of Smaller Elements on Right Side

#include<bits/stdc++.h>
using namespace std;
vector<int> res;
    
void mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp, vector<int>& index) 
{
        if (l >= r) return;
        int m = l + (r - l) / 2; 
        mergeSort(nums, l, m, tmp, index); 
        mergeSort(nums, m + 1, r, tmp, index); 
        int i = l, j = m + 1, k = l; int count = 0; 
        while (i <= m) 
        {
            while (j <= r && nums[index[j]] < nums[index[i]]) 
            {
                count++;
                tmp[k++] = index[j++];
            } 
            res[index[i]] += count;
            tmp[k++] = index[i++];
        }
        while(j<=r) 
        {
            tmp[k++] = index[j++];
        }
        for(i=l;i<=r;i++) 
        {
            index[i] = tmp[i];
        }
}

vector<int> countSmaller(vector<int>& nums) 
{
    res.resize(nums.size()); 
    vector<int> tmp(nums.size(), 0);
    vector<int> index; 
    for(int i = 0; i < nums.size(); i++) 
    {
        index.push_back(i);
    }
    mergeSort(nums, 0, nums.size() - 1, tmp, index);
    return res;
}

int main()
{
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
    }
    vector<int> res = countSmaller(v);
    for(auto x: res)
    {
        cout<<x<<" ";
    }
}

Java Program for Number of Smaller Elements on Right Side

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static void update(int num, int fen[]) 
    {
        for(int i=num; i<=20001; i+=(i&-i)) 
            fen[i] += 1;
    }
    public static int find(int num, int fen[]) 
    {
        int ans = 0;
        for(int i=num; i>0; i-=(i&-i)) 
            ans += fen[i];
        return ans;
    }
    public  static void countSmaller(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        int fen[] = new int[20002];
        for(int i=n-1; i>=0; i--) 
        {
            ans[i] = find(10000 + nums[i] - 1, fen);
            update(10000 + nums[i], fen);
        }
        for(int i = 0; i < n; i++)
        {
            System.out.print(ans[i]+" ");
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        List<Integer> v = new ArrayList<Integer>() {};
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        countSmaller(a);
    }
}

9
1 4 2 7 2 4 221 54 23

0 2 0 2 0 0 2 1 0

Complexity Analysis

Time Complexity

O(nlogn) where n is the size of the given array. Here we apply the concept of merge sort which leads us to nlogn time complexity.

Space Complexity

O(n) because we declare an array to store the answer and update the result after each element.