Nearest greater to left

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.

Example:

Input:  {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

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.
import java.util.Scanner;

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;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i ++) {
            a[i] = keyboard.nextInt();
        }
        keyboard.close();

        int[] NGL = findNearestGreaterToLeft(a);
        for(int i = 0; i < n; i++) {
            System.out.print(NGL[i] + " ");
        }
        System.out.println();

    }
}

Time Complexity: O(n^2) | Space Complexity: O(1)

Using Stack

import java.util.Scanner;
import java.util.Stack;

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;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i ++) {
            a[i] = keyboard.nextInt();
        }
        keyboard.close();

        int[] NGL = findNearestGreaterToLeftUsingStack(a);
        for(int i = 0; i < n; i++) {
            System.out.print(NGL[i] + " ");
        }
        System.out.println();

    }
}

Time 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.

Space Complexity: O(n)