### zahidhasanmozumder's blog

By zahidhasanmozumder, history, 6 weeks ago,

Suppose I have an array of 1 to n elements (Basically they are permutation) and I want to store the next bigger element of the i th element. How is it possible in O(N) or O(NlogN) time?

For example, The given array is : [5, 6, 7, 1, 2, 4, 3] of 7 length. Now I want to store all the element's next bigger element (according to indexing order) in O(N) or O(NlogN) time.

The resultant array should look like this : [6, 7, 7, 2, 4, 4, 3].

Here, the next bigger element of 5 is 6, for 6 is 7, for 7 (there is no bigger element than 7 in the next indices) is 7, for 1 is 2, for 2 is 4, for 4 (there is no bigger element than 4 in the next indices) is 4 and for 3 (as last element so it won't have any next bigger element) is 3.

How it can be done? Hope you guys will help me with your ideas :)

• +8

 » 6 weeks ago, # |   0 Yes, this can be done in n*log(n) time, and I have a straightforward solution. Please share where you got this problem first so that I know I'm not helping you cheat on an assessment or ongoing contest, and I will respond with the solution idea after.
•  » » 6 weeks ago, # ^ |   0 Agree on not helping before they share the source, in one case I've seen someone even ask for solutions during a company's code challenge. Well, I think I know your solution by now anyways :D
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 UPD: I found a problem of which this seems to be a near-dupe, there seems to be an O(n) solution of it. I shall leave finding the solution to the reader. (SecondThread, I can discuss about the solution with you in DM if you wish)
•  » » 6 weeks ago, # ^ |   0 Thank you for your response. And I truly appreciate your thoughts of not sharing the solution or idea before knowing the source or context. Basically I'm asking the idea for my recent unsuccessful submissions of a problem from past contest. I have already given two days behind the problem and now I'm asking for the idea for a particular part of the problem. Source: Fighting Tournament Hope you will help me by let me know your ideas......
 » 6 weeks ago, # |   0 It's easy to do it in O(NlogN).We traverse the array in reverse order, and put the numbers into a set.Than query in the set,done!
•  » » 6 weeks ago, # ^ |   0 It would be more helpful for me if you can explain the "query in the set" more clearly....
•  » » » 6 weeks ago, # ^ |   0 Basically, you can binary search on STL sets! Other than that you can fill the array from the back and thats it.
•  » » » » 6 weeks ago, # ^ |   0 Ummm I'm a little bit confused. I have tried both of these approach but none of them gave me the desired result :(
•  » » » » » 6 weeks ago, # ^ |   -8 Use a stack, and start traversing from the back of the array.Here a small pseudocode stack st; vector res=arr; // arr is the given array for(int i=n-1;i>=0;i--){ if(!st.empty() && st.top()
•  » » » » » » 6 weeks ago, # ^ |   0 Thanks a lot man. This was very helpful