Next Greater Element in an Array

In this class, We discuss Next Greater Element in an Array.

The reader can take a complete competitive coding course. Click Here.

Before starting competitive coding, the readers suggested completing a placement training course for basic coding. Click here.

Question:

Given an array of N integers.

The task is to find the next greater element for each element in the array.

Suppose no greater element is on the right. Place -1.

Example:

Input: [5, 2, 3, 9, 6]

Output: [9, 3, 9, -1, -1]

Time complexity: O(N)

Space complexity: O(N)

Logic:

First Way:

Use nested loops to write the logic.

Take the first element and find the greater element on the right.

Take the second element and find the greater element on the right. So on.

We need a time complexity of O(N^2)

Second Way:

Using stack data structure.

By using a stack data structure, we can complete in time O(N).

We provide a step-by-step explanation in the video.

Code:

def isEmpty(stack):

    return len(stack) == 0

def push(stack, x):

    stack.append(x)

def pop(stack):

    if isEmpty(stack):

        print(“Error : stack underflow”)

    else:

        return stack.pop()

def printNGE(arr):

    s = []

    element = 0

    next = 0

    push(s, arr[0])

    for i in range(1, len(arr), 1):

        next = arr[i]

        if isEmpty(s) == False:

            element = pop(s)

            while element < next:

                print(str(element) + ” — ” + str(next))

                if isEmpty(s) == True:

                    break

                element = pop(s)

            if element > next:

                push(s, element)

        push(s, next)

    while isEmpty(s) == False:

        element = pop(s)

        next = -1

        print(str(element) + ” — ” + str(next))

arr = [8, 5, 3, 1,2,1, 6, 9, 14]

printNGE(arr)