CHEFHEIGHT - Editorial


Author: aaryan_musk




Stack, Map



  • The idea is to store the elements for which we have to find the next greater element in a stack and while traversing the array, if we find a greater element, we will pair it with the elements from the stack till the top element of the stack is less than the current element.

  • Follow the steps mentioned below to implement the idea:

    • Push the first element to stack.

    • Pick the rest of the elements one by one and follow the following steps in the loop.

      • Mark the current element as next.
      • If the stack is not empty, compare top most element of stack with next.
      • If next is greater than the top element, Pop element from the stack. next is the next greater element for the popped element.
      • Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
    • Finally, push the next in the stack.

    • After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.

In this particular approach we are using the map as our main stack

  • This is same as above method but the elements are pushed and popped only once into the stack. The array is changed in place.
  • The array elements are pushed into the stack until it finds a greatest element in the right of array.
  • In other words the elements are popped from stack when top of the stack value is smaller in the current array element.
  • Once all the elements are processed in the array but stack is not empty. The left out elements in the stack doesn’t encounter any greatest element . So pop the element from stack and change it’s index value as -1 in the array.


C++ Solution: CHEFHEIGHT C++ Solution
Python Solution: CHEFHEIGHT Python Solution