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)