write a c program to find next greater element in an array. For example if the given array is { 2, 3, 9, 6, 4, 8, 7 }.  The next greater of 2 is 3 , for 3 is 9 , for 6 is 8, for 4 is 8. There is no next greater element for 8 and 7. In case of no next greater element found ,print -1.

find next greater element in an array ( method 1)

The time complexity of above solution is O(N²). So this method is not an efficient solution. this problem can be solved by using stack with O(N) complexity.

C++ Solution using stack with O(N) complexity

How it works:

  1. Push the 0th element from array to the stack.
  2. Traverse array from 1st element to the end of array.
  3. During traversing , peek the top element of stack and compare with current element of array.
  4. if the current element of array is greater than the top element of the stack. then the next greater of top element of stack is current element of array. (pop the stack)
  5. Continue step 4 until the current element of array is greater than the top element of the stack.
  6. if the current element of array is lesser than the top element of the stack, push current element of array to the stack.
  7. When traversing ends and if the stack is not empty , it means all the elements in the stack are not having next greater.

Here are pictorial represents of above steps:

find next greater element

find next greater element c program

ref:

https://www.hackerrank.com/contests/second/challenges/next-greater-element




Related Contents to follow