How to find next greater element for every element in an array ?

  • In an array, to display 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 value in an array.
  • While the elements for which no greater element exist, consider the next greater element as 0.
NGE for every element in an array
  • For any array, rightmost element always has next greater element as 0.
  • Next greater element of an array element array[i], is an integer array[j], such that
    • array[i] < array[j]
    • i < j
    • j – i is minimum
  • i.e. array[j] is the first element on the right of array[i] which is greater than array[i].
  • For Example the Input array is 88, 13, 44, 2, 10, 5, 17

Output

Next greater element for 13     = 44
Next greater element for 2      = 10
Next greater element for 5      = 17
Next greater element for 10     = 17
Next greater element for 17     = 0
Next greater element for 44     = 0
Next greater element for 88     = 0

Steps for finding a next greater element

  • To find Next Great Element Using two loops.
  • All the elements one by one to picks in the outer loop.
  • The outer loop picked the first greater element from the inner loop.
  • If a greater element is found then that element is printed as next, otherwise 0 is printed.

Sample Code in Java

class Wikitechy
{ 
	/* prints element and NGE pair for 
	all elements of arr[] of size n */
	static void printNGE(int arr[], int n) 
	{ 
		int n1, i, j; 
		for (i=0; i<n; i++) 
		{ 
			n1 = 0; 
			for (j = i+1; j<n; j++) 
			{ 
				if (arr[i] < arr[j]) 
				{ 
					n1 = arr[j]; 
					break; 
				} 
			} 
			System.out.println(arr[i]+" -- "+n1); 
		} 
	} 
	
	public static void main(String args[]) 
	{ 
		int arr[]= {30, 35, 11, 17, 2}; 
		int n = arr.length; 
		printNGE(arr, n);
        
	} 
}

Output

30 -- 35
35 -- 0
11 -- 17
17 -- 0
2 -- 0

Categorized in:

Java

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,