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 :)
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.
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
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)
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!
It would be more helpful for me if you can explain the "query in the set" more clearly....
Basically, you can binary search on STL sets! Other than that you can fill the array from the back and thats it.
You can do this question in O(n) using stack, let me explain:
You traverse the array in reverse order, i.e., back to front. Then for each element in the original array, while the element at the top of the stack is smaller than the element we are at, pop the top element out of the stack. Do this until the stack is empty or the element on top of the stack is bigger than the element we are at. Then if the stack is empty, then the answer for this element will simply be the element. Otherwise, it will be the element on the top of the stack. Lastly, we just have to add the element we are at to the top of the stack. Let me simulate this for the above input.
Answer array: 0, 0, 0, 0, 0, 0, 0 Stack: Empty
Element we are at: 3
Stack after removing elements from stack: empty
Answer array: 0, 0, 0, 0, 0, 0, 3. (since stack is empty, the last element will just be 3)
Stack after adding 3: 3
Element we are at: 4
Stack after removing elements: empty
Answer array: 0, 0, 0, 0, 0, 4, 3 (since stack is empty, the last element will just be 4)
Stack after adding 4: 4
Element we are at: 2
Stack after removing elements: 4 (2 is not bigger than 4)
Answer array: 0, 0, 0, 0, 4, 4, 3 (answer is the number at the top of the stack
Stack after adding 2: 2, 4.
Element we are at: 1
Stack after removing elements: 2, 4 (1 is not bigger than 2)
Answer array: 0, 0, 0, 2, 4, 4, 3 (answer is the number at the top of the stack)
Stack after adding 1: 1, 2, 4.
Element we are at: 7
Stack after removing element: Empty (we removed all the elements since none of the numbers in the stack were bigger than 7
Answer array: 0, 0, 7, 2, 4, 4, 3. (Since stack is empty, answer is just 7)
Stack after adding 7: 7
Element we are at: 6
Stack after removing elements: 7 (7 bigger than 6)
Answer array: 0, 7, 7, 2, 4, 4, 3
Stack after adding 6: 6, 7
Element we are at 5:
Stack after removing elements: 6, 7 (6 is bigger than 5)
Answer array: 6, 7, 7, 2, 4, 4, 3
Stack after adding 5: 5, 6, 7.
So now you have the answer. It is clear that this is O(n) because you will only add and remove each element from the stack at most once. Also I hope that the simulation will intuitively make you understand why this works.
Btw I did the question in the last contest and implemented this idea. Here is the submission: https://codeforces.com/contest/1719/submission/168584747
Thank you so so much. I was really looking for such kind of explanation. My doubts are clear now. It was really worthy and helpful for me. Thanks a lot for your response and such explanation :)
No problem, but this is a fairly standard and well known algorithm. You should probably try to research a little more bfore asking here. Also, ignore the code that i shared. It doesnt use this algorithm. However it shows that you dont really need this algorithm for this question