Find the next greater element in an array [duplicate]

Question

Given an array , for every element I need to find the smallest element to the right of the given element which is greater than the current element.

Mathematically, For every index i in array A, I need to find index j such that

A[j] > A[i]
j > i
A[j] - A[i] is minimum

I need to find j for every index i

The brute force solution would be O(n^2) and I am hoping to do better. I am thinking that an O(n log n) solution is possible using self-balancing BST but that seems pretty complex. Moreover I need a O(n) solution.

Is there a O(n) solution to this problem? Is there a proof that the lower bound is O(n log n)?

Answer 1

Proof of O(nlogn) lower bound: (for comparison based algorithms)

Lets say we have a comparison-based algorithm that would accomplish this task in O(n). That is for each index, we have the immediate greater element to its right (say R[i]).

Similarly we can run this algorithm on the reversed input array and then reverse the result. For each index we have the immediate greater element to its left (say L[i]).

This means that in O(n) we have for each element, the immediate greater element in the array = min (R[i], L[i]).

We can now sort the array using this information.

Find the minimum element in the array. Find its successor (immediate greater element), then its successor's successor etc. Hence you would have got the entire array in sorted order.

Sorted the array in O(n) using only comparisons (a contradiction).

O(nlogn) Algorithm:
Start building the balanced BST from the right of the array. The nodes would contain the values and the respective indices.

Then for each new element encountered, inserting it in the BST would get corresponding nearest larger index/value.