I don't understand how to do it with stacks

chetan_aggarwalbX1 · November 11, 2020, 9:22am

How to implement this question with stack? I don’t get it

mr.encoder · November 11, 2020, 9:27am

hey @chetan_aggarwalbX1
first try to solve it for linear array in O(N) after that it is easy.
u just have to run that peace of code again for circular array.
here is the complete approach->
stack stores the indices of the appropriate elements from nums array. The top of the stack refers to the index of the Next Greater Element found so far. We store the indices instead of the elements since there could be duplicates in the nums array. The description of the method will make the above statement clearer.

We start traversing the numsnums array from right towards the left. For an element nums[i] encountered, we pop all the elements stack[top] from the stack such that nums[stack[top]] ≤ nums[i]. We continue the popping till we encounter a stack[top] satisfying nums[stack[top]]>nums[i]. Now, it is obvious that the current stack[top] only can act as the Next Greater Element for nums[i](right now, considering only the elements lying to the right of nums[i]).

If no element remains on the top of the stack, it means no larger element than nums[i] exists to its right. Along with this, we also push the index of the element just encountered(nums[i]), i.e. ii over the top of the stack, so thatnums[i](or stack[topstack[top) now acts as the Next Greater Element for the elements lying to its left.

We go through two such passes over the complete nums array. This is done so as to complete a circular traversal over the nums array. The first pass could make some wrong entries in the res array since it considers only the elements lying to the right of nums[i], without a circular traversal. But, these entries are corrected in the second pass

mr.encoder · November 11, 2020, 9:33am

Source Code for the same is

github.com

DivonilLiquid/Data-Structure-Algorithm/blob/master/Stack/NextGreaterElementII.cpp

/*
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.
*/
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> s; // index stack
        int n = nums.size();
        vector<int> res(n,-1);
        for (int i = 0; i < n * 2; i++) {
            int num = nums[i % n]; 
            while (!s.empty() && nums[s.top()] < num) {
                res[s.top()] = num;

This file has been truncated. show original

chetan_aggarwalbX1 · November 11, 2020, 9:44am

I did it something like this: https://ide.codingblocks.com/s/371879 , can it be more optimised?

chetan_aggarwalbX1 · November 11, 2020, 9:46am

This explanation was really helpful! thankyou!

mr.encoder · November 11, 2020, 9:49am

It’s absolutely right, moreover this explanation was framed by @aman212yadav ,
Happy Coding

chetan_aggarwalbX1 · November 11, 2020, 9:50am

Thankyou @aman212yadav for such a good explanation.

mr.encoder · November 11, 2020, 9:51am

If this solved your doubt, please mark it as resolved

mr.encoder · November 12, 2020, 7:51am

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.