'How many number are less than or equal than x in an array?

Given an integer n and array a, I need to find for each i, 1≤ i ≤ n, how many elements on the left are less than or equal to ai

Example:

    5 
    1 2 1 1 2

Output

    0 1 1 2 4

I can do it in O(N2) but I want to ask if there is any way to do it faster, since N is very large (N ≤ 106)?

c++algorithmtime-complexity


Solution 1:[1]

You can use a segment tree, you just need to use a modified version called a range tree. Range trees allow rectangle queries, so you can make the dimensions be index and value, and ask "What has value more than x, and index between 1 and n?" Queries can be accomplished in O(log n) assuming certain common optimizations.

Either way O(N^2) is completely fine with N < 10^6.

Solution 2:[2]

Yes, It can be done in better time complexity compared to O(N^2) i.e O(NlogN). We can use the Divide and Conquer Algorithm and Tree concept.

want to see the source code of above mentioned two algorithms??? Visit Here .

I think O(N^2) should be the worst case. In this situation, we will have to traverse the array at least two times. I have tried in O(N^2):

import java.io.*; import java.lang.*;

public class GFG {

public static void main (String[] args) {
    int a[]={1,2,1,1,2};
   
   
   int i=0;
   int count=0;
   int b[]=new int[a.length];
   for(i=0;i<a.length;i++)
   {
       for(int c=0;c<i;c++)
       {
       if(a[i]>=a[c])
       {
            count++;
       }
         }
       b[i]=count;
       count=0;
   }
   for(int j=0;j<b.length;j++)
        System.out.print(b[j]+" ");
}`

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Mostafa Wael
Solution 2 Raushan Kumar

Related Questions