# CHEFHEIGHT - Editorial

CDVB2022/CHEFHEIGHT
CDVE2022/CHEFHEIGHT

Author: aaryan_musk

DIFFICULTY

Easy-Medium

PREREQUISITES

Stack, Map

EXPLANATION

USING STACK

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

USING MAP
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.

SOLUTIONS

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