NGL - Nearest Greater Element to Left of every element

Problem Statement

Given an array of integers, find the nearest (not considering distance, but value) greater element to the left of every element.

The elements for which no greater element exists on the left side, print -1.

This problem is similar to - NGR - Nearest Greater Element to Right of every element

Examples

Input:  a = {9, 4, 15, 6, 2, 10} 
Output: {-1, 9, -1, 15, 6, 15} 

Explanation: The first element has nothing on the left side, so the answer for first is -1. Second element 4 has 9 on the left which is greater than 4, so the answer is 9. Third element 15 has nothing greater on the left side, so the answer is -1. Fourth element 6 has 15 as the nearest greater element on the left, so the answer is 15 Similarly, we get values for the fifth and sixth elements.

Solution

Method 1 - Brute Force

The Brute force approach is to iterate over the array and for each element at index i,

• Iterate from i-1 to 0 to find the nearest greater element on the left.

class NearestGreaterToLeft {
    private static int[] findNearestGreaterToLeft(int[] a) {
        int n = a.length;
        int[] NGL = new int[n];

        for(int i = 0; i < n; i++) {
            NGL[i] = -1;
            for(int j = i-1; j >= 0; j--) {
                if(a[j] > a[i]) {
                    NGL[i] = a[j];
                    break;
                }
            }
        }

        return NGL;
    }
}

Complexity

• ⏰ Time complexity: O(n^2)
• 🧺 Space complexity: O(1)

Method 2 - Using Stack

Code

Java

class NearestGreaterToLeft {
    private static int[] findNearestGreaterToLeftUsingStack(int[] a) {
        int n = a.length;
        int[] NGL = new int[n];

        Stack<Integer> s = new Stack<>();
        for(int i = 0; i < n; i++) {
            NGL[i] = -1;
            while(!s.empty()) {
                int top = s.peek();
                if(top > a[i]) {
                    NGL[i] = top;
                    break;
                } else {
                    s.pop();
                }
            }
            s.push(a[i]);
        }

        return NGL;
    }
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space 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.