Find out how many values are smaller up to a value in an array-CodePudding

The problem is the following:

Let P be an array of positive integers. I need to create an array S according to this definition:

S[i] contains the number of elements that are smaller or equal to P[i].

This must be achieved in linear time - O(n).

Example: if P=[2,7,4,5,9,12], then S=[0,1,0,1,4,5].

That's because P[0] has zero elements smaller or equal to it (up to P[0]), so S[0]=0, and P[1] only has P[0] smaller than it (up to P[1]), so S[1]=1, and so on.

Here's my attempt (in Java):

My attempt is making a single pass on the array and utilizes a stack to store the previous indices in P. This, sadly, is a failed attempt, because for the input P=[17,4,2,0,15] the output is incorrect.

Here's the code I wrote:

public static int[] build_s(int[] p) {
    IntegerStack temp = new IntegerStack(p.length);
    temp.push(0);
    int[] s = new int[p.length];
    int max = p[0];
    for (int i = 0; i < p.length; i  ) {
        if (p[i] >= max) {
            s[i] = i 1;
            max = p[i];
        } else if (p[i-1] > p[i]) {
            if (p[i] > temp.peek())
                temp.push(i);
            s[i] = 1;
        } else {
            s[i] = (i - temp.peek());
        }
    }
    return s;
}

I would really appreciate any help in making my algorithm work properly. I can see that the problem arises when there's a sequence such as 4,2,0,15 that breaks the algorithm, but I couldn't figure out a solution in O(n) time.

Thank you!

CodePudding user response：

In linear time complexity i.e. O(n) it is not possible to find the count of elements that smaller or equal numbers to it present in the left side of current position.

Let's assume that such an algorithm exists with O(N) time complexity. Then by using the resultant from this "algorithm", once applying in the original given array and then once after reversing it, we can find the sorted array in O(N) time.

Now we know that, even in the best case scenario, sorting an array made up of random integers has a time complexity of O(N*logN).

Hence, our assumption is wrong and such algorithm doesn't exist.

CodePudding user response：

One way to solve this in O(nlog(n)) is by using a Fenwick/BIT. But the BIT construction space requires an array with size equal to maximum value in your array (provided all your elements in the array are positive). The construction of BIT array is O(size). for each element in your array, you need to insert 1 as the value inside your BIT array, Each query for a number of elements smaller than the current element will be of O(log(size)). So the total time complexity will be O(sizelog(size)). Here size is the length of your BIT array. you can learn more about BIT here