Home » Algorithms

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 (n²) 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)