Https://ide.codingblocks.com/s/345118

#1

Sir whats wrong with my code its showing wrong for the first test case

#2

hello @sauravzt7
u cannot use upper bound because data is not sorted

#3

sir can you give me a little hint ,im kinda stuck here

#4

@sauravzt7
first try to solve a problem assuming that array is not circular.

#5
#6

sir i solved it but i don think its optimized since its under the queue challenges there must be a solution using those concepts ,it will be very helpful if you guide me to use any of those concepts in this problem

#7

yeah ur approach is brute force
here is the optimised approach->
This approach makes use of a stack. This 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

#8

sir i tried solving but failed ,it will be very helpful if share a clear and stepwise approach to follow

#9
#10

Sir i solved using stack ,can you plaese take a look over my solution and suggest me if any better changes

#11

@sauravzt7
this approach is most optimised.

#12

thank you for your help sir:-)))