Given an unsorted array , we have to find the next highest element of every element in the array that is at the higher index.
output -1 when there is no such number on right
Example:
Array: 2,4,15,1
output: 4,15,-1,-1
Edit: To all those who helped, thanks a lot.
Just take the first element array[0] you assume that is the highest element.
then go from left to right with index i and compere if the array[i+1] is greater than your assumption you change the value of your assumption to the new greater value and so on just take care with the last position because there are no more elements in the position i+1. so just make a validation where i is <= n where n is the size of your array
something like this in your for loop if array [i+1] > assumption and i < n then the array [i] is equal to the number in position array [ i + 1 ] and is not then array [ i ] is equal -1
=D
Well I got one way to solve this question : O(N logN)
We use the balance binary search trees or AVL trees.
If you don’t know what a AVL tree is just read a tutorial from the net.You don’t need to necessarily implement it …you can use the STL set in C++.(but do understand the properties as it may help you later)
The property of this data structure is that if the BST has n nodes then the max height it can have is log n.
The basic idea behind using this data structure is to reduce the time spent for looking the next highest element to log n.
We start from the last element and go to the first element .In the process we add each number to the AVL tree.’
When looking for the next highest number to the current number we just travel the BST and reach the closest number to the current number .
It takes at most log n time as the height of the tree is log n.
After the answer for the current answer is calculated just insert the current number in the AVL tree and move forward i.e towards the starting index.
This the best I can currently come up with…If i get a better solution I will update this answer.
*ANOTHER SOLUTION O(N LOG N LOG N)
IF NUMBERS ARE <=10^7
We keep a segment tree where for each number ‘i’ we can query no of array elements <=i.
How we do that??
Whenever we process an array element , starting from the last index, we (after processing the element) update the range [element,maximum possible element] by 1 in the segment tree.We can do this by Lazy propagation (If you don’t know what that means just look it up on the internet).
Max possible element (EM).
Now for an element in the original array (E) we binary search between E and EM.
For each mid element(M) in the search we query the segment tree for numbers <=M(S1).
Now let’s define CURR = S1 - S2 where S2=no of elemnts <=E
Now
if(curr==0)//No elements between E and M
search the right half;
else search the left half;//some elements between E and M
We get the answer when l==mid.
So we get log n for binary search and log n for each query.
After we found answer then add E into the segment tree by updating the range [E,EM] in the segment tree.
Could be done in O(n) with 5 line code.
@shivam9753 How ??
If I go by your code in the above answer then for
Input: 2 4 15 1 3
Your Answer: 4 15 -1 3 -1
Correct Answer: 3 15 -1 3 -1
Thats a fault of person who asked.
He should explain it properly.
Sorry to trouble you. No ofense 
Here is an O(n) soln -
Maintain a list storing the pair <value,index>
We will iterate from left to right and the list will store the pair of those positions for which an answer has not been obtained. Once you obtain an answer, you remove the pair from the list. So at max there will be N insertions and N removals.
Note : The values in the list will always be in the sorted order because while inserting an element on the list, we will remove all the elements lesser than it from the list and update the answer of those positions to the value of the element we are inserting.
Suppose the list is V.
Initialize ans[n] with values -1
for i=1 to n {
while(V.last.value <A[i] AND !V.empty()) {
ans[V.last.index] = A[i];
V.remove(last);
}
if(V.empty() OR V.last.value>A[i])
V.push_back(pair(A[i],i));
}
Example - 2,4,15,1. First initialize ans = -1,-1,-1,-1.
Initially, V is empty. As said V will be storing pairs of the form <value,index>
First pair is (2,1). It is pushed in V = {(2,1)}.
Next pair is (4,2). Now 4 > 2 so (2,1) will be removed and ans[1] = 4. V = {(4.2)}.
Next pair is (15,3). Now 15 > 4 so (4,2) is removed and ans[2] = 15. V = {(15,3)}.
Next pair is (1,4). Now 1 < 15 so (1,4) is added to V and V = {(15,3) , (1,4) }
So there you have it, ans = 4,15,-1,-1.
Please point out flaws in the approach, if any.
@thechamp103: your solution seems fine to me.
I will try coding it and then will definitely come back to you.
Thanks.
There’s very simple O(N) solution for this.
value[n+1]=INF;
for(int i=n;i>0;i--)
{
int x = i+1;
while(x<=n)
{
if( value[x] > value[i] )break;
x = ans[x];
}
ans[i]=x; // stores the least index which has higher value & lies to right
}
value[n+1]=-1;
for(int i=1;i<=n;i++)
ans[i]=value[i];
It is indeed O(N) because one element occurs at most twice as x.
so, the inside for loop runs at most 2N times.
How is your code correct??
Consider array 1 5 4 3 2
When i =1 x=2
You will break and put ans(1) = 2nd position
Or value array is something else ??
It’s so simple.
Just sort the array using sort() STL function or by any other method.
And then , just take out the second last element of the array;
#include<iostream>
#include<algorithm>
int main(){
int a[5]={1,4,5,3};
sort(&a[0],&a[5]);
cout<<"Second Largest Element : " <<a[2];
}I am sorry I forgot to consider your given input and output but with little tweaks that can be achieved too
By sorting the array we will lose the information about which number near to the current number and greater than it comes after it in the original array
Edited the answer to add one more approach
worst case complexity: O(Q*(R-L))…
can any one do in O(N) or O(NlogN) with simple approach…
worst case complexity: O(Q*(R-L))…
can any one do in O(N) or O(NlogN) with simple approach…
public class NextgraternumberinArray {
static void nextelement(int []ele,int len){
for(int i=0;i<len;i++){
int []k=new int[len];
for(int j=0;j<len;j++)
{
if(i==j)
{
k[j]=66666;
continue;
}
if(ele[j]-ele[i]<=0)
{
k[j]=5555555;
}
else
{
k[j]=ele[j]-ele[i];
}
}
int index = 0;
int min = k[index];
for (int w=1; w<len; w++)
{
if (k[w] < min )
{
min = k[w];
index = w;
}
}
if(ele[i]==ele[index]){
System.out.println("Sorry ther is no greater number for "+ele[i]);
}
else
System.out.println("Next greater number for"+ele[i]+" is :"+ele[index]);
}
}
public static void main(String[] args) throws Exception {
System.out.println("Enter the number of elemet in array:");
BufferedReader bufferRead = new BufferedReader(new InputStreamReader(System.in));
int number=Integer.parseInt(bufferRead.readLine());
int []elements=new int[number];
for(int i=0;i<number;i++){
elements[i]=Integer.parseInt(bufferRead.readLine());
}
nextelement(elements,number);
//System.out.println(Arrays.toString(elements));
}
}