CC-12 : Find next greater element in the array.

Description:

Given an input array of integers, return an output array of integers which holds the next greater element at same index for each index in input array. If no greater element exists for a number in the input array at a particular index, add -1 at the same index in the output array.

Test cases and expected outputs:

Input Parameters	Expected outputs
Original array: 1,2,7,9,4,7,2,1	Next greater: 2,7,9,-1,7,-1,-1,-1
Original array: 8,3,2,3,16,1,0,4	Next greater: 16,16,3,16,-1,4,4,-1

Pseudocode:

Initialize a Deque based stack for processing purposes.

Initialize an output array with same size as input array to hold the next greater elements.

For each element in input array index idx:

While top element of stack is less than or equal to current element of array, remove the top element of the stack.

If stack size is not zero, set element of output array at index idx to top element of stack.

Else if stack size is zero, the array does not contain any greater element than current element of input array. Set element of output array at index idx to -1.

Return output array.

Code:

public int[] nextGreater(int[] arr) throws Exception{
	int n=arr.length;
	int[] greater=new int[n];
	Deque<Integer>stack=new LinkedList<Integer>();
	for (int idx=n-1; idx >=0; idx--) {
		while ((stack.size() !=0 )&&(stack.peekFirst() <= arr[idx])) {
			stack.pollFirst();
		}
		if (stack.size()!=0){
			greater[idx]=stack.peek();
		}else {
			greater[idx]=-1;
		}
		stack.offerFirst(arr[idx]);
	}
	return greater;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Deque;
import java.util.LinkedList;

public class StackNextGreaterElement {
	
public int[] nextGreater(int[] arr) throws Exception{
	int n=arr.length;
	int[] greater=new int[n];
	Deque<Integer>stack=new LinkedList<Integer>();
	for (int idx=n-1; idx >=0; idx--) {
		while ((stack.size() !=0 )&&(stack.peekFirst() <= arr[idx])) {
			stack.pollFirst();
		}
		if (stack.size()!=0){
			greater[idx]=stack.peek();
		}else {
			greater[idx]=-1;
		}
		stack.offerFirst(arr[idx]);
	}
	return greater;
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex < intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println(" ************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}
 	
public static void main(String[] args) {
	/***********************
 	Test cases given below
	 **********************/
	try {
	int[] retVal;
	StackNextGreaterElement stackNextGreaterElement=new StackNextGreaterElement();
	int[] arr= {1,2,7,9,4, 7, 2, 1};
	printArraySummary(arr, "Original array");
	retVal=stackNextGreaterElement.nextGreater(arr);
	printArraySummary(retVal, "Next  greater");
	
	int[] arr1= {8, 3, 2, 3, 16, 1, 0, 4};
	printArraySummary(arr1, "Original array");
	retVal=stackNextGreaterElement.nextGreater(arr1);
	printArraySummary(retVal, "Next  greater");	
	
	}catch (Exception exception) { 
	System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}