Mark next greater element in an array.

This is an interesting problem I found on geeksforgeeks .

Problem Statement

You are given an array of integers. For each element in that array, you need to find the position of next element greater than it.

Analysis

The above problem can easily be solved in O(n*n) using the naive algorithm. The naive algorithm involves checking the greater element for each element in O(n). Thus , the complexity for the entire algorithm becomes O(n*n).

//============================================================================
// Name        : Greater_element_naive.cpp
// Author      : Prateek Agarwal
// Institution : NIT Jalandhar
//============================================================================

#include <iostream>
#include <string.h>
using namespace std;

#define MAX 5000

int n,a[MAX];

int solve(){
	for (int i=0;i<n;i++){
		int flag = 0;	// flag to check if there exist an element greater and to the right of i
		for(int j=i+1;j<n;j++){
			if (a[j]>a[i]){
				flag=1;
				cout << i << ":" << j << endl;
				break;
			}
		}
		if (flag==0) cout << i << ":" << -1 << endl;
	}
	return 0;
}

int input(){
	cin >> n;
	for(int i=0;i<n;i++) cin >> a[i];
	return 0;
}

int main() {
	input();
	solve();
	return 0;
}

 

However the above algorithm is too slow and requires optimization.

So,Here’s a O(n) approach using stacks.

Procedure

Start by traversing the array and maintaining a stack. Initially the stack is empty denoted by top = -1.

You will push an element and increment the array pointer into the stack if –

• The stack is empty
• The element in the array is lesser than the top element of the stack.

You will pop the element (but do not increment the array pointer) if –

•   The element in the array is greater than the top element of the stack.(This time you’ve found the element greater for the top element of the stack therefore you also mark the result).

//============================================================================
// Name        : Greater_element_optimised.cpp
// Author      : Prateek Agarwal
// Institution : NIT Jalandhar
//============================================================================

#include <iostream>
#include <string.h>
using namespace std;

#define MAX 5000

int n,a[MAX];
int mark[MAX];

struct stack{
	int value;
	int index; //for storing the index of the element in array 'a' pushed into the stack
};
stack s[MAX];
int top = -1;

//O(n) approach using stack

int solve(){
	int i=0;
	while(i<n){
		if (top==-1 || s[top].value >= a[i]){
			top++;
			s[top].value = a[i];	//pushing the element into the stack
			s[top].index = i;
			i++;
		}
		else{
			mark[s[top].index] = i;
			top--;	//deleting an element from the top
		}
	}

	//displaying the result

	for (int i=0;i<n;i++){
		cout << i << ":" << mark[i] << endl;
	}

	return 0;
}

int input(){
	memset(mark,-1,sizeof(mark));
	cin >> n;
	for(int i=0;i<n;i++) cin >> a[i];
	return 0;
}

int main() {
	input();
	solve();
	return 0;
}

 

Example

Consider the following input – n = 4 , a = [3,2,4,1]

1. Initially the stack is empty. So , top = -1.Also i(array pointer) = 0.
2. Since the stack is empty,push the first element and increment the i. The top element in the stack becomes 3.
3. The next element i.e 2 is lesser than the top element of the stack i.e 3. So,push it as well and increment i.The top element in the stack becomes 2.
4. The next element i.e 4 is greater than the top element of the stack. We’ve got the greater element for top element of the stack.Therefore mark the result and pop out the top element.(Do not increment array pointer).The top element is now 3.
5. the array element 4 is greater than the top element of the stack i.e 3.Therefore mark the result pop the top element and continue.
6. Since the stack is empty now,push the array element 4.increment array pointer.
7. the next element is 1 (smaller than top element of stack).So,push it and increment i.
8. i=n , End of loop.
9. Since the last two elements in the array aren’t marked in the loop,it means that there exists no such result for these values.(The default  values are set as -1).

The above code produces the following output for the sample example-

0:2
1:2
2:-1
3:-1

Analysis of Complexity – O(n)

Consider any case, the above code involves pushing and popping each element into the stack exactly once.

Thus, the complexity is O(n) which is a big improvement over the previously discussed naive algorithm.

For any query , drop a comment below.