Nearest greater element on the right side in an array | Problem-solving

In this problem, we have an array of numbers and we are required to find the nearest greater element on the right side for each of the elements in the array of length “n”.

Our input array of length “n” (n=6 in this example)

Expected output with the nearest greater elements for the input array

Let us understand the problem with different cases arising as below.

CASE 1:

If the next immediate element is greater than the current element then we store that greater element value in our output array as it’s our answer for that particular subscript. For example, In the above “input array” diagram, we have the values 7 and 8 in the indices 0 and 1 respectively so, for the element 7 we already found the nearest greater element which is 8 on the index 1 of input array.

CASE 2:

Now, let us consider the indices 1 and 2 whose respective values are 8 and -8 in our input array. In this case, notice that a[1] > a[2] and hence we don’t have a nearest greater element on the right side for a[1] at that point. We push the index of such elements(index 1 in example) into a stack in this case.

CASE 3:

Last subscript of the array has no greater element and hence it’s always -1. let us drive into code.

public class NextGreater {

 public static void main(String l[]) {
   int a[] = {7,8,-8,1,19,3};
   int ans[] = new int[a.length];
   java.util.Stack<Integer> stack = new java.util.Stack<>();    //stack to push indices if nearest greater element is unavailable
   for(int i=0; i<a.length-1; i++){
     if(a[i] < a[i+1]){
        ans[i] = a[i+1];            //found the greater element immediately
     } 
     else {
        stack.push(i);              // if not found immediately, push into a stack
     }
     while(!stack.empty() && a[stack.peek()] < a[i+1]){  // keep comparing to know if a nearest greater element is found on right side for those pushed into stack
        int topMost = stack.pop();                       // when a greater element is found, pop it
        ans[topMost] = a[i+1];
     }
   }   
   ans[ans.length-1]=-1;                                // last subscript is always -1
   while(!stack.empty()){                               // if the stack is still not empty, it means that there are no greater elements found on right side
      ans[stack.pop()] = -1;
   }
   for(int t : ans)
      System.out.print(t+" ");                          // printing our output
 }
 
 
}

When we are done traversing through the array and the stack is still not empty then it means that there are no greater elements found on the right side of array for those indices which are still available in the stack.

In this implementation, we have used a stack and in the worst-case, we keep pushing all the elements in the stack (when all the elements in the array are identical) and also there is an array creation involved to print our output. hence the auxiliary space used is O(n). We are traversing through the array only once but then there is a popping of the stack involved if a greater element is found. We might traverse through all the elements twice for solving the problem and then we are also traversing to print our output array. thus, making the time-complexity as O(n).

Rakesh
www.theorangecloud.in