Efficiently Finding Previous Greater Elements in an Integer Array using Java

 Problem: Given an array of integers, the task is to find the closest previous greater element for every element of the given array.

Note: If there doesn't exist any previous greater element for any element, print -1. Previous greater for the first element of the array will always be -1.

Example: Input: arr[] = {15, 10, 18, 12, 4, 6, 2, 8} Output: -1, 15, -1, 18, 12, 12, 6, 12

Input: arr[] = {8, 10, 12} Output: -1, -1, -1

Solution:

This problem can be solved in linear time complexity, that is, in O(N) time complexity in the worst case. Let's see how.

We can store useful information needed to find the previous greater elements for an element at ith index while traversing the array. We can use a stack data structure to implement the above approach.

The idea is to push the first element onto the stack, and start traversing the array from the second element. For every new element, we compare it with the stack top(previous greater). We keep popping elements from the stack top until we find an element at stack top which is greater than the current element. This will be our previous greater element for the current element. Finally, we push the current element to the stack.

The time complexity of above solution is O(N) in the worst case, and the auxiliary space used will be O(N) as we are using a stack to store the elements.

Here is the Java implementation:

import java.util.*;

class GFG {

java
static void prevGreater(int arr[])
{
    Deque<Integer> stack = new ArrayDeque<Integer>();
    
    stack.push(arr[0]);
    int pg = -1;
    
    System.out.print(pg + " ");
    
    for(int i = 1; i < arr.length; i++)
    {
        while(stack.isEmpty()==false && 
                    stack.peek() <= arr[i])
        {
            stack.pop();
        }
            
        pg = (stack.isEmpty())? -1 :  stack.peek(); 
        System.out.print(pg + " ");
        
        stack.push(arr[i]);
    }
}

public static void main (String[] args) {
    int arr[] = {15, 10, 18, 12, 4, 6, 2, 8};
    
    prevGreater(arr);
    
}

}

Output: -1 15 -1 18 12 12 6 12

Note that the output is correct for the given input array.

Overall, this algorithm is much faster than the previous solution, as it has a time complexity of O(N) instead of O(N^2).