PROBLEM LINK:
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