Greatest element present on the right side of every element in an array

Question

I have been given an array (of n elements) and i have to find the smallest element on the right side of each element which is greater than itself(current element).

For example :
   Array =     {8,20,9,6,15,31}
Output Array = {9,31,15,15,31,-1} 

Is it possible to solve this in O(n).? I thought of traversing the array from the right side (starting from n-2) and building a balance binary search tree for the remaining elements, as searching in it for an element which is immediately greater than the current element would be O(logn) .

Hence time complexity would come out to be O(n*(log(n)).

Is there a better approach to this problem?

Answer 1

The problem you present is impossible to solve in O(n) time, since you can reduce sorting to it and thereby achieve sorting in O(n) time. Say there exists an algorithm which solves the problem in O(n). Let there be an element a.

The algorithm can also be used to find the smallest element to the left of and larger than a (by reversing the array before running the algorithm). It can also be used to find the largest element to the right (or left) of and smaller than a (by negating the elements before running the algorithm).

So, after running the algorithm four times (in linear time), you know which elements should be to the right and to the left of each element. In order to construct the sorted array in linear time, you'd need to keep the indices of the elements instead of the values. You first find the smallest element by following your "larger-than pointers" in linear time, and then make another pass in the other direction to actually build the array.

Answer 2

Others have proved that it is impossible in general to solve in O(n).

However, it is possible to do in O(m) where m is the size of your largest element.

This means that in certain cases (e.g. if if your input array is known to be a permutation of the integers 1 up to n) then it is possible to do in O(n).

The code below shows the approach, built upon a standard method for computing the next greater element. (There is a good explanation of this method on geeks for geeks)

def next_greater_element(A):
    """Return an array of indices to the next strictly greater element, -1 if none exists"""
    i=0
    NGE=[-1]*len(A)
    stack=[]
    while i<len(A)-1:
        stack.append(i)
        while stack and A[stack[-1]]<A[i+1]:
            x=stack.pop()
            NGE[x]=i+1
        i+=1
    return NGE

def smallest_greater_element(A):
    """Return an array of smallest element on right side of each element"""
    top = max(A) + 1
    M = [-1] * top # M will contain the index of each element sorted by rank
    for i,a in enumerate(A):
        M[a] = i
    N = next_greater_element(M) # N contains an index to the next element with higher value (-1 if none)
    return [N[a] for a in A]


A=[8,20,9,6,15,31]
print smallest_greater_element(A)

The idea is to find the next element in size order with greater index. This next element will therefore be the smallest one appearing to the right.

Answer 3

This cannot be done in O(n), since we can reduce Element Distinctness Problem (which is known to be sovleable in Omega(nlogn) when comparisons based) to it.

First, let's do a little expansion to the problem, that does not influence its hardness:

I have been given an array (of n elements) and i have to find the smallest element on the right side of each element which is greater/equals than itself(current element).

The addition is we allow the element to be equal to it (and to the right), and not only strictly greater than¹.

Now, Given an instance of element distinctness arr, run the algorithm for this problem, and look if there is any element i such that arr[i] == res[i], if there isn't answer "all distinct", otherwise: "not all distinct".

However, since Element Distinctness is Omega(nlogn) comparisons based, it makes this problem such as well.

---

(1) One possible justification why adding equality is not making the problem more difficult is - assuming elements are integers, we can just add i/(n+1) to each element in the array, now for each two elements if arr[i] < arr[j], also arr[i] + i/(n+1) < arr[j] + j/(n+1), but if arr[i] = arr[j], then if i<j arr[i] + i/(n+1) < arr[j] + j/(n+1), and we can have the same algorithm solve the problem for equalities as well.