## Problem Statement

Given an array, print the Next Greater Element (NGE) for every element. The Next greater element for an element x is the first greater element on the right side of x in the array.

The elements for which no greater element exist, print -1.

Example 1:

``````Input:  {1, 3, 2, 4}
Output: {3, 4, 4, -1}

Element     Next greater element on the right
1           3
3           4
2           4
4           -1          ``````

Example 2:

``````Input:  {6, 4, 12, 5, 2, 10}
Output: {12, 12, -1, 10, 10, -1}

Element     Next greater element on the right
6           12
4           12
12          -1
5           10
2           10
10          -1           ``````

## Solution

### Brute Force

The Brute force approach is to iterate over the array and for each element at index i,

• Iterate from i+1 to n to find the next greater element.
``````import java.util.Scanner;

class NearestGreaterToRight {
private static int[] nextGreaterElement(int[] a) {
int n = a.length;
int[] NGR = new int[n];

for (int i = 0; i < n; i++) {
NGR[i] = -1;
for(int j = i+1; j < n; j++) {
if(a[j] > a[i]) {
NGR[i] = a[j];
break;
}
}
}

return NGR;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++) {
a[i] = keyboard.nextInt();
}
keyboard.close();

int[] NGR = nextGreaterElement(a);
for(int i = 0; i < n; i++) {
System.out.print(NGR[i] + " ");
}
System.out.println();
}
}``````

Time Complexity: `O(n^2)` | Space Complexity: `O(1)`

### Using Stack

``````import java.util.Scanner;
import java.util.Stack;

class NearestGreaterToRight {
private static int[] nextGreaterElementUsingStack(int[] a) {
int n = a.length;
int[] NGR = new int[n];

Stack<Integer> s = new Stack<Integer>();
for(int i = n-1; i >= 0; i--) {
NGR[i] = -1;
while(!s.empty()) {
int top = s.peek();
if (top > a[i]) {
NGR[i] = top;
break;
} else {
s.pop();
}
}
s.push(a[i]);
}

return NGR;
}

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n = keyboard.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i ++) {
a[i] = keyboard.nextInt();
}
keyboard.close();

int[] NGR = nextGreaterElementUsingStack(a);
for(int i = 0; i < n; i++) {
System.out.print(NGR[i] + " ");
}
System.out.println();
}
}``````

Time Complexity: `O(n)`, The entire array (of size n) is scanned only once. Each of the stack’s n elements are pushed and popped exactly once.

Space Complexity: `O(n)`