Next greater number

Given an array of integers, for each a[i] element print a[j] such that a[j] > a[i] and j>i. Also j should be as close to i as possible. For the rightmost element, value will be -1. If for any i if there is no such j, then result for that too will be -1. In simple terms, we need to print nearest greater number for each element in given array.

Simple brute force method would be to scan array in two loops. For each element in array, scan remaining right side elements and find out the greater number. Complexity of such code will be O(n2). How can we do better?
If we keep track of all the numbers for which we have yet not encountered a greater number, we keep improve. Idea is that whenever we examine a number, we check if there are elements which are already visited in array and yet there is no greater number assigned to them. If there are such elements, we check if current element is greater than them. If yes, then for all those numbers which are less than current element, next greater element will be current number.

Find next greater element in array

To keep track of the numbers which have yet not assigned greater number, we can use stack. Steps are simple.

1. If stack is empty, push the element on to stack.
2. If stack is not empty, pop all elements from the stack which less than current element.
3. Print these numbers paired with current number.
4. If top of the stack is not less than current element or stack is empty, push the current element.(All the elements present in stack will be greater than current element why?)
5. After scanning all elements in array, print all elements in stack paired with -1 as there is no greater element on right side of these elements.

Let’s workout an example:
A  = {5,6,3,35,23,6,8}
Output should be {(5,6), (6,35), (3,35), (6,8), (8, -1), (23, -1), (35, -1)}

Next greater number using stacks

#define STACK_SIZE 10

typedef struct stack{
int top;
int items[STACK_SIZE];
}stack;

void push(stack *ms, int element){
if(ms->top < STACK_SIZE-1){
ms->items[++(ms->top)] = element;
}
else {
printf("Stack is full\n");
}
}

int pop (stack *ms){
if(ms->top > 0){
return ms->items[(ms->top)--];
}
else{
printf("Stack is empty\n");
}
}

int peek(stack ms){
if(ms.top < 0){
printf("Stack empty\n");
return 0;
}
return ms.items[ms.top];
}

int isEmpty(stack ms){
if(ms.top < 0) return 1;
else return 0;
}

void print_next_greater(int a[], int size){
stack ms;
int i;

ms.top = -1;
for(i=0; i<size; i++){
if(is_empty(ms)){
push(&ms, a[i]);
}
else{
while(!is_empty(ms) && a[i] > peek(ms)){
printf("(%d, %d)\n ", peek(ms), a[i]);
pop(&ms);
}
push(&ms, a[i]);
}
}
while(!is_empty(ms)){
printf("(%d, %d)\n ", pop(&ms), -1);
}
}

int main(){
int a[] = {5,6,3,35,23,6,8};
int size = sizeof(a)/sizeof(a[0]);

print_next_greater(a, size);
return 0;
}

Please refer Stack data structure to under stand more how to implement operation on stack.

Complexity of algorithm to find next greater element in array is O(N) with extra space complexity of O(N) for stack.