# Find Nearest Greatest Neighbours of each element in an array

In this article, we are going to see how to find nearest greatest neighbours of each element in an array in minimum time complexity?
Submitted by Radib Kar, on November 16, 2018

Problem statement:

Given an array of elements, find the nearest (on the right) greatest element ofeach element in the array. (Nearest greatest means the immediate greatest one on the right side).

Solution:

Brute force approach:

One simple brute force approach is to scan the entire right part for each element and to find the nearest greatestone. Such approach has a computational complexity of O (n2) which is not linear.

A better solution exists which can be done using stack data structure.

### Better approach using stack

1. Create a stack.
2. Push the first element to the stack.
For rest of the elements
3. Set the variable nextNearestGreater to the current element.
4. If stack is not empty, pop an element from the stack and compare it to the variable nextNearestGreater.
5. If nextNearestGreateris greater than the popped element, then nextNearestGreateris the next greater element for the popped element. Print it. Keep popping up the stack till popping elementsare smaller than nextNearestGreater (till stack is not empty). nextNearestGreateris next greater element for all the popped elements.
6. Else push the popped element.

### C++ program to Find Nearest Greatest Neighbours of each element in an array

```#include<bits/stdc++.h>
using namespace std;

void print(int* a,int n){
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

void replace(int* a,int n){
int i=0;
stack<int> s;  //craeting a stack using stl
int e,nextNearestGreater; //create variable nextNearestGreater
s.push(a[0]); // push the first element

for(int i=1;i<n;i++){ // for the rest of the array
// set nextNearestGreater to the current element
nextNearestGreater=a[i];
//if stack is not empty
if(!s.empty()){
e=s.top();
// pop from stack
s.pop();
// if nextNearestGreater is greater than popped element
while(e<nextNearestGreater){
// replacing the current element with nextNearestGreater
//as it's the next greater element
cout<<"nearest greater element of "<<e<<" is "<<nextNearestGreater<<endl;
if(s.empty())
break;
e=s.top();
// continue popping till nextNearestGreater is greater
s.pop();
}
// if popped element is greater than nextNearestGreater then push to stack
if(e>nextNearestGreater)
s.push(e);
}
s.push(nextNearestGreater);
}
while(!s.empty()){
e=s.top();
s.pop();
cout<<"nearest greater element of "<<e<< " is "<<e<< " (no nearest greater number on the right side)"<<endl; //since no number is greater in right of e
}
}

int main(){
int n;

// enter array length
cout<<"enter no of elements\n";
cin>>n;
int* a=(int*)(malloc(sizeof(int)*n));
//fill the array
cout<<"enter elements................\n";
for(int i=0;i<n;i++)
scanf("%d",&a[i]);

cout<<"finding nearest greater numbers for each elements.............\n"<<endl;
replace(a,n);

//print(a,n);
return 0;
}
```

Output

```enter no of elements
8
enter elements................
12
10
8
15
17
16
20
2
finding nearest greater numbers for each elements.............
nearest greater element of 8 is 15
nearest greater element of 10 is 15
nearest greater element of 12 is 15
nearest greater element of 15 is 17
nearest greater element of 16 is 20
nearest greater element of 17 is 20
nearest greater element of 2 is 2 (no nearest greater number on the right side)
nearest greater element of 20 is 20 (no nearest greater number on the right side)
```